Publications
10 results found
Talluri K, Angelos T, 2023, Revenue management of a professional services firm with quality-revelation, Operations Research, Vol: 71, Pages: 1021-1439, ISSN: 0030-364X
Professional service firms (PSFs) such as management consulting, law, accounting, investment banking, architecture, advertising and home-repair companies provide services forcomplicated turnkey projects. The firm bids for a project and, if successful in the bid, assignsemployees to work on the project. We formulate this as a revenue management problem under two assumptions: a quality-revelation setup where the employees that would be assignedto the project are committed ex ante, as part of the bid, and a quality-reputation setup wherethe bid’s win probability depends on past performance, say an average of the quality of pastjobs. We first model a stylized Markov-Chain model of the problem amenable to analysis andshow that upfront revelation of the assigned employees has subtle advantages. Subsequentto this analysis, we develop an operational stochastic dynamic programming framework under the revelation model to aid the firm in this bidding and assignment process. We showthat the problem is computationally challenging and provide a series of bounds and solution methods to approximate the stochastic dynamic program. Based on our model andcomputational methods we are able to address a number of interesting business questionsfor a PSF, such as the optimal utilization levels and the value of each employee type. Ourmethodology provides management a toolkit for bidding on projects as well as to performworkforce analytics and to make staffing decisions.
Talluri K, Markakis M, Tikhonenko D, 2023, Sequential bidding for merging in algorithmic traffic, Manufacturing and Service Operations Management, Vol: 25, Pages: 168-181, ISSN: 1523-4614
Problem Definition: We consider the problem of resolving ad-hoc unpredictable congestion inenvironments where customers have private time valuations. We investigate the design of fair, efficient, budget-balanced and implementable bidding mechanisms for observable queues. Our primary motivation comes from merging in algorithmic traffic, i.e., a driver wishing to merge in a relatively dense platoon of vehicles in a coordinated and efficient way, using inter-vehicle communication and micro-payments, akin to an arriving customer trading for position in a single-server observable queue.Methodology/Results: We analyze the performance of a mechanism where the queue-joiner makessequential, take-it-or-leave-it bids from tail to head of a platoon (T2H), with the condition that thevehicle can advance to the next position only if it wins the bid. This mechanism is designed so it isimplementable, balances the budget, and imposes no negative externalities. We compare this withhead-to-tail bidding (H2T), which favors the merging driver but potentially causes uncompensatedexternalities. Assuming i.i.d. time valuations, we obtain the optimal bids, value functions, and expected social welfare in closed form in both mechanisms. Moreover, if the time valuation of the merging driver is not high, we show that the expected social welfare of T2H is close to a partial-informationsocial optimum, and that the expected social welfare of H2T is lower than that of T2H as long as theplatoon is not too short.Managerial Implications: Our findings suggest that mechanisms based on sequential, take-it-orleave-it bids from tail to head of an observable queue have good social welfare performance, even ifthe corresponding bids are not chosen optimally, as long as the time valuation of the arriving customer is not high. Nevertheless, the tension between individual incentives and social welfare seemshard to resolve, highlighting the role of platforms to enforce the cooperation of involved parties.
Markakis MG, Talluri K, Tikhonenko D, 2022, Managing lane-changing of algorithm-assisted drivers, Transportation Research Part C: Emerging Technologies, Vol: 138, ISSN: 0968-090X
Theoretical models of vehicular traffic ascribe the fundamental cause of velocity oscillations and stop-and-go waves to suboptimal or unpredictable human driving behavior. In this paper we ask: if vehicles were controlled or assisted by algorithms, and hence driven “optimally,” would these phenomena simply go away? If they do not, how should a regulator manage algorithm-assisted vehicular traffic for a smooth flow? We study these questions in the context of a mandatory lane-changing scenario from the perspective of an algorithm-assisted driver on a curtailed lane that has to merge to an adjacent free lane with a relatively dense platoon. In a stylized model of algorithm-assisted driving, we liken the blocked-lane driver to a rational self-interested agent, whose objective is to minimize her expected travel time through the blockage, deciding (a) at what velocity to move, and (b) whether to merge to the free lane if an adequate gap arises. Moving at higher velocities reduces travel time, but also reduces the probability of finding a large enough gap to merge. We analyze the problem via dynamic programming, and we show that the optimal policy has a surprising structure: in the presence of uncertainty on adequate-sized gaps in the target lane, it may be optimal for the blocked-lane driver, in certain parameter regimes, to oscillate between high and low velocities while attempting to merge. Hence, traffic oscillations can arise not just due to suboptimal or unpredictable human driving behavior, but also endogenously, as the outcome of a driver’s rational, optimizing behavior. We provide theoretical support for this finding by drawing similarities to bang–bang control. As velocity oscillations are known to be detrimental to a smooth traffic flow, we provide sufficient conditions such that traffic oscillations, due to such optimizing behavior, do not arise. Finally, we investigate the fundamental flow-density and travel time-density diagrams throug
Markakis M, Talluri K, Tikhonenko D, 2022, Managing lane changing of algorithm-assisted drivers, Publisher: Elsevier
Theoretical models of vehicular traffic ascribe the fundamental cause of velocity oscillations andstop-and-go waves to suboptimal or unpredictable human driving behavior. In this paper we ask: ifvehicles were controlled or assisted by algorithms, and hence driven "optimally," would these phenomena simply go away? If not, how should a regulator manage algorithm-assisted vehicular traffic for a smooth flow? We study these questions in the context of a mandatory lane-changing scenario with "mixed traffic," i.e., an algorithm-assisted driver on a curtailed lane that has to merge to an adjacent free lane with a relatively dense platoon of human drivers. In a stylized model of algorithm-assisted driving, we liken the blocked-lane driver to a rational self-interested agent, whose objective is to minimize her expected travel time through the blockage, deciding (a) at what velocity to move, and (b) whether to merge to the free lane, if given the opportunity (adequate gap). Moving at higher velocities reduces travel time, but also reduces the probability of finding a large enough gap to merge. We analyze the problem via dynamic programming, and we show that the optimal policy has a surprising structure: in the presence of uncertainty on adequate-sized gaps in the target lane, it may be optimal for the blocked-lane driver, in certain parameter regimes, to oscillate between high and low velocities while attempting to merge. Hence, traffic oscillations can arise not just due to suboptimal or unpredictable human driving behavior, but also endogenously, as the outcome of a driver’s rational, optimizing behavior. We draw out structural similarities to bang-bang control. As velocity oscillations are known to be detrimental to a smooth traffic flow, we provide sufficient conditions on the velocity limits so that traffic oscillations while merging, due to such optimizing behavior, do not arise at optimality. Finally, we investigate the fundamental flow-densit
Chen N, Li A, Talluri K, 2021, Reviews and self-selection bias with operational implications, Management Science, Vol: 67, Pages: 7472-7492, ISSN: 0025-1909
Reviews for products and services written by previous consumers have become an influential input to the purchase decision of customers. Many service businesses monitor the reviews closely for feedback as well as detecting service flaws, and they have become part of the performance review for service managers with rewards tied to improvement in the aggregate rating. Many empirical papers have documented a bias in the aggregate ratings, arising because of customers’ inherent self-selection in their choices and bounded rationality in evaluating previous reviews. Although there is a vast empirical literature analyzing reviews, theoretical models that try to isolate and explain the bias in ratings are relatively few. Assuming consumers simply substitute the average rating that they see as a proxy for quality, we give a precise characterization of the self-selection bias on ratings of an assortment of products when consumers confound ex ante innate preferences for a product or service with ex post experience and service quality and do not separate the two. We develop a parsimonious choice model for consumer purchase decisions and show that the mechanism leads to an upward bias, which is more pronounced for niche products. Based on our theoretical characterization, we study the effect on pricing and assortment decisions of the firm when potential customers purchase based on the biased ratings. Our results give insights into how quality, prices, and customer feedback are intricately tied together for service firms.
Kunnumkal S, Talluri K, 2019, A strong lagrangian relaxation for general discrete-choice network revenue management, Computational Optimization and Applications, Vol: 73, Pages: 275-310, ISSN: 0926-6003
Discrete-choice network revenue management (DC-NRM) captures both customer behaviorand the resource-usage interaction of products, and is appropriate for airline and hotel revenuemanagement, dynamic sales of bundles in advertising, and dynamic assortment optimizationin retail. The state-space of the DC-NRM stochastic dynamic program explodes and approxi-mation methods such as the choice deterministic linear program (CDLP), the affine, and thepiecewise-linear approximations have been proposed to approximate it in practice. The affinerelaxation (and thereby, its generalization, the piecewise-linear approximation) is intractableeven for the simplest choice models such as the multinomial logit (MNL) choice model with asingle segment. In this paper we propose a new Lagrangian relaxation method for DC-NRMbased on an extended set of multipliers. An attractive feature of our method is that the numberof constraints in our formulation scales linearly with the resource capacities. While the num-ber of constraints in our formulation is an order of magnitude smaller that the piecewise-linearapproximation (polynomial vs exponential), it obtains a bound that is as tight as the piecewise-linear bound. If we assume that the consideration sets of the different customer segments aresmall in size—a reasonable modeling tradeoff in many practical applications—our method is anindirect way to obtain the piecewise-linear approximation on large problems effectively. Ourresults are not specific to a particular functional form (such as MNL), but hold for any discrete-choice model of demand. We show by numerical experiments that our Lagrangian relaxationmethod can provide substantial improvements over existing benchmark methods, both in termsof tighter upper bounds, as well as revenues from policies based on the relaxation.
Kunnumkal S, Talluri KT, 2018, Choice network revenue management based on new tractable approximations, Transportation Science, Vol: 53, Pages: 1501-1799, ISSN: 0041-1655
The choice network revenue management model incorporates customer purchase behavioras probability of purchase as a function of the offered products, and is appropriate for air-line and hotel network revenue management, dynamic sales of bundles, and dynamic assort-ment optimization. The optimization problem is a stochastic dynamic program and is in-tractable. Consequently, a linear programming approximation called choice deterministic linearprogram (CDLP) is usually used to generate controls. Tighter approximations such as affineand piecewise-linear relaxations have been proposed, but it was not known if they can be solvedefficiently even for simple models such as the multinomial logit (MNL) model with a singlesegment. We first show that the affine relaxation (and hence the piecewise-linear relaxation) isNP-hard even for a single-segment MNL choice model. By analyzing the affine relaxation wederive a new linear programming approximation that admits a compact representation, implyingtractability, and prove that its value falls between theCDLPvalueandtheaffinerelaxationvalue. This is the firsttractablerelaxation for the choice network revenue management problemthat is provably tighter thanCDLP. This approximation in turn leads to new policies that,in our numerical experiments, show very good promise: a 2% increase in revenue on averageoverCDLP; and the values typically coming very close to the affine relaxation. We extendour analysis to obtain other tractable approximations that yield even tighter bounds. We alsogive extensions to the case with multiple customer segments with overlapping consideration setswhere choice by each segment is according to the MNL model.
Strauss AK, Talluri K, 2017, Tractable consideration set structures for assortment optimization and network revenue management, Production and Operations Management, Vol: 26, Pages: 1359-1368, ISSN: 1059-1478
Discrete-choice models are widely used to model consumer purchase behavior in assortment optimization and revenue management. In many applications, each customer segment is associated with a consideration set that represents the set of products that customers in this segment consider for purchase. The firm has to make a decision on what assortment to offer at each point in time without the ability to identify the customer's segment. A linear program called the Choice-based Deterministic Linear Program (CDLP) has been proposed to determine these offer sets. Unfortunately, its size grows exponentially in the number of products and it is NP-hard to solve when the consideration sets of the segments overlap. The Segment-based Deterministic Concave Program with some additional consistency equalities (SDCP+) is an approximation of CDLP that provides an upper bound on CDLP's optimal objective value. SDCP+ can be solved in a fraction of the time required to solve CDLP and often achieves the same optimal objective value. This raises the question under what conditions can one guarantee equivalence of CDLP and SDCP+. In this study, we obtain a structural result to this end, namely that if the segment consideration sets overlap with a certain tree structure or if they are fully nested, CDLP can be equivalently replaced with SDCP+. We give a number of examples from the literature where this tree structure arises naturally in modeling customer behavior.
Kunnumkal S, Talluri KT, 2016, On a piecewise-linear approximation for network revenue management, Mathematics of Operations Research, Vol: 41, Pages: 72-91, ISSN: 0364-765X
The network revenue management (RM) problem arises in airline, hotel, media, and other industries where the sale productsuse multiple resources. It can be formulated as a stochastic dynamic program, but the dynamic program is computationallyintractable because of an exponentially large state space, and a number of heuristics have been proposed to approximateits value function. In this paper we show that the piecewise-linear approximation to the network RM dynamic program istractable; specifically we show that the separation problem of the approximation can be solved as a relatively compact linearprogram. Moreover, the resulting compact formulation of the approximate dynamic program turns out to be exactly equivalentto the Lagrangian relaxation of the dynamic program, an earlier heuristic method proposed for the same problem. We performa numerical comparison of solving the problem by generating separating cuts or as our compact linear program. We discussextensions to versions of the network RM problem with overbooking as well as the difficulties of extending it to the choicemodel of network revenue RM.
Talluri KT, Kunnumkal S, 2016, A note on relaxations of the choice network revenue management dynamic program, Operations Research, Vol: 64, Pages: 158-166, ISSN: 1526-5463
In recent years, several approximation methods have been proposed for the choice network revenue management problem. These approximation methods are proposed because the dynamic programming formulation of the choice network revenue management problem is intractable even for moderately sized instances. In this paper, we consider three approximation methods that obtain upper bounds on the value function, namely, the choice deterministic linear program (CDLP), the affine approximation (AF), and the piecewise-linear approximation (PL). It is known that the piecewise-linear approximation bound is tighter than the affine bound, which in turn is tighter than CDLP. In this paper, we prove bounds on how much the affine and piecewise-linear approximations can tighten CDLP. We show (i) the gap between the AF and CDLP bounds is at most a factor of 1+1/(mini{r1i}), where r1i>0 are the resource capacities, and (ii) the gap between the piecewise-linear and CDLP bounds is within a factor of 2. Moreover, we show that these gaps are essentially tight. Our results hold for any discrete-choice model and do not involve any asymptotic scaling. Our results are surprising because calculating the AF bound is NP-hard and CDLP is tractable for a single-segment multinomial logit model; our result implies that if a firm has all resource capacities of 100, the gap between the two bounds, however, is at most 1.01.
This data is extracted from the Web of Science and reproduced under a licence from Thomson Reuters. You may not copy or re-distribute this data in whole or in part without the written consent of the Science business of Thomson Reuters.