Search

Dynamic resource allocation problems arise under a variety of settings. In "Survey of Dynamic Resource-Constrained Reward Collection Problems: Unified Model and Analysis," Balseiro, Besbes, and Pizarro introduce a unifying model for a large class of dynamic optimization problems dubbed dynamic resource-constrained reward collection (DRC2) problems. Surveying the literature, they show that this class encompasses a variety of disparate and classical problems typically studied separately, such as dynamic pricing with capacity constraints, dynamic bidding with budgets, network revenue management, online matching, or order fulfillment. Furthermore, they establish that the DRC2 class is amenable to analysis by characterizing the performance of a central, certainty-equivalent heuristic. Notably, they provide a novel unifying analysis that isolates the drivers of performance, recovers as corollaries some existing specialized results, generalizes other existing results by weakening the assumptions required, and yields new results in specialized settings for which no such characterization was available. Dynamic resource allocation problems arise under a variety of settings and have been studied across disciplines such as operations research and computer science. The present paper introduces a unifying model for a very large class of dynamic optimization problems that we call dynamic resource-constrained reward collection (DRC2) problems. We show that this class encompasses a variety of disparate and classical dynamic optimization problems such as dynamic pricing with capacity constraints, dynamic bidding with budgets, network revenue management, online matching, and order fulfillment, to name a few. Furthermore, we establish that the class of DRC2 problems, although highly general, is amenable to analysis. In particular, we characterize the performance of the fluid certainty-equivalent control heuristic for this class. Notably, this very general result recovers as corollaries some existing specialized results, generalizes other existing results by weakening the assumptions required, and also yields new results in specialized settings for which no such characterization was available. As such, the DRC2 class isolates some common features of a broad class of problems and offers a new object of analysis. Funding: The work of D. Pizarro was supported by the Artificial and Natural Intelligence Toulouse Institute, which is funded by the French "Investing for the Future—PIA3" program [Grant ANR-19-P3IA-0004]. Supplemental Material: The online appendix is available at https://doi.org/10.1287/opre.2023.2441. [ABSTRACT FROM AUTHOR]

Hiring the right person for the job is crucial for the success of any organization. In "Selection and Ordering Policies for Hiring Pipelines via Linear Programming," Epstein and Ma study several problems motivated by a firm that is carrying out a recruitment process. Restricted to a finite time budget, the firm must decide who will be interviewed out of a pool of applicants and who will receive offers among the interviewed applicants. They develop approximation algorithms with constant factor guarantees that approach optimality when the number of vacant positions grows large. The algorithms they develop are nonadaptive: they fix a subset of candidates and an order to conduct the interviews and the order remains unchanged, independent of the outcomes of other interviews. Thus, they establish bounds on the adaptivity gap: a worst-case measure of how poorly non-adaptive algorithms can perform with respect to their adaptive counterparts. Motivated by hiring pipelines, we study three selection and ordering problems in which applicants for a finite set of positions are interviewed or sent offers. There is a finite time budget for interviewing/sending offers, and every interview/offer is followed by a stochastic realization of discovering the applicant's quality or acceptance decision, leading to computationally challenging problems. In the first problem, we study sequential interviewing and show that a computationally tractable, nonadaptive policy that must make offers immediately after interviewing is near optimal, assuming offers are always accepted. We further show how to use this policy as a subroutine for obtaining a polynomial-time approximation scheme. In the second problem, we assume that applicants have already been interviewed but only accept offers with some probability; we develop a computationally tractable policy that makes offers for the different positions in parallel, which can be used even if positions are heterogeneous, and is near optimal relative to a policy that can make the same total number of offers one by one. In the third problem, we introduce a parsimonious model of overbooking where all offers are sent simultaneously, and a linear penalty is incurred for each acceptance beyond the number of positions; we provide nearly tight bounds on the performance of practically motivated value-ordered policies. All in all, our paper takes a unified approach to three different hiring problems based on linear programming. Our results in the first two problems generalize and improve the existing guarantees in the literature that were between 1/8 and 1/2 to new guarantees that are at least 1 − 1 / e ≈ 63.2 %. We also numerically compare three different settings of making offers to candidates (sequentially, in parallel, or simultaneously), providing insight into when a firm should favor each one. Supplemental Material: The online appendices are available at https://doi.org/10.1287/opre.2023.0061. [ABSTRACT FROM AUTHOR]

Optimizing Revenue in Two-Sided Online Markets through Strategic Quality Selection and Information Disclosure Ensuring profitable operations in two-sided online marketplaces demands an astute analysis of seller quality and strategic information sharing with buyers. A recent paper, titled "Quality Selection in Two-Sided Markets: A Constrained Price Discrimination Approach" by B. Light, R. Johari, and G. Weintraub delves into the nuances of this operation. The authors explore the challenge that platforms encounter in deciding which sellers to allow and how much quality information to share with buyers in order to enhance platform revenue. Utilizing two distinct two-sided market models, the paper unveils conditions under which adopting straightforward information structures, such as excluding certain sellers or not differentiating among participating sellers, proves to be a revenue-maximizing strategy. This study utilizes a constrained price discrimination problem to reveal specific strategies platforms can use to adjust information structures in diverse market scenarios, providing insights for digital platforms aiming to navigate the marketplace more effectively. Online platforms collect rich information about participants and then share some of this information back with them to improve market outcomes. In this paper, we study the following information disclosure problem in two-sided markets: if a platform wants to maximize revenue, which sellers should the platform allow to participate, and how much of its available information about participating sellers' quality should the platform share with buyers? We study this information disclosure problem in the context of two distinct two-sided market models: one in which the platform chooses prices and the sellers choose quantities (similar to ride sharing), and one in which the sellers choose prices (similar to e-commerce). Our main results provide conditions under which simple information structures commonly observed in practice, such as banning certain sellers from the platform and not distinguishing between participating sellers, maximize the platform's revenue. The platform's information disclosure problem naturally transforms into a constrained price discrimination problem in which the constraints are determined by the equilibrium outcomes of the specific two-sided market model being studied. We analyze this constrained price discrimination problem to obtain our structural results. Funding: This work was supported by the National Science Foundation [Grants 1839229 and 1931696]. [ABSTRACT FROM AUTHOR]

A Simple Monotonic Dynamic Pricing Policy We consider a canonical revenue management setting in which a monopolist seeks to maximize expected total revenues by selling a fixed inventory of product to customers who arrive sequentially over time. It is known in the literature that a simple dynamic pricing policy can perform reasonably well in such setting. However, the literature typically assumes that price can move freely over time (i.e., it can either go up or down). In practice, firms often impose certain restrictions on price movement. In this paper, we consider the setting in which price can only move monotonically over time (either only decreasing or only increasing). We devise a simple provably near-optimal dynamic pricing policy. Aside from markdown applications, our policy can also be applied to the setting with strategic customers. We consider a canonical revenue management problem wherein a monopolist seller seeks to maximize expected total revenues from selling a fixed inventory of a product to customers who arrive sequentially over time, and the seller is restricted to implement a pricing policy that is monotonic (either nonincreasing or nondecreasing) over time. Gallego and Van Ryzin [Gallego G, Van Ryzin G (1994) Optimal dynamic pricing of inventories with stochastic demand over finite horizons. Management Sci. 40(8):999–1020] show that the simplest monotonic price policy, the fixed price policy, is asymptotically optimal in the high-volume regime in which both the seller's initial inventory and the length of the selling horizon are proportionally scaled. Specifically, the revenue loss of the fixed price policy is O (k 1 / 2) , where k is the system's scaling parameter. Following the publication of Gallego and Van Ryzin [Gallego G, Van Ryzin G (1994) Optimal dynamic pricing of inventories with stochastic demand over finite horizons. Management Sci. 40(8):999–1020], several papers have attempted to improve the performance of the fixed price policy. Among them, Jasin [Jasin S (2014) Reoptimization and self-adjusting price control for network revenue management. Oper. Res. 62(5):1168–1178] develops a simple modification of the fixed price policy (that allows prices to move either up or down) with a guaranteed revenue loss of order O (ln k). In this paper, we propose a novel family of monotonic readjustment policy, which restricts the prices to only move in one direction (i.e., either up or down). We show that, if the seller updates the price for only a single time, then the revenue loss of our policy is O (k 1 / 3 (ln k) 2 α) for some α > 1 / 2. If, however, the seller updates the prices with a frequency O (ln k / ln ln k) , then the revenue loss of our policy is O ((ln k) 7 α) for some α > 1 / 2. These results show the power of dynamic pricing even in the presence of monotonic price restriction. We discuss two applications of our policy: markdown pricing and pricing in the presence of strategic customers. Supplemental Material: The online appendix is available at https://doi.org/10.1287/opre.2020.0774. [ABSTRACT FROM AUTHOR]

Characterizing the Efficiency of Static Pricing Schemes as a Function of the Supply The problem of selling a supply of k units to a stream of customers constitutes one of the cornerstones in revenue management. Static pricing schemes (that output the same price to all customers) are commonly used because of their simplicity and their many desirable properties; they are anonymous, nonadaptive, and order oblivious. Although the efficiency of those schemes should improve as the supply k increases, prior work has only focused either on algorithms that aim for a constant approximation that is independent of k or on the setting where k becomes really large. In contrast, this paper characterizes the efficiency of static pricing schemes as a function of the supply. Our approach stems from identifying a "sweet spot" between selling enough items and obtaining enough utility from customers with high valuations. Subsequent work shows that our pricing scheme is the optimal static pricing for every value of k. We study a pricing problem where a seller has k identical copies of a product, buyers arrive sequentially, and the seller prices the items aiming to maximize social welfare. When k = 1, this is the so-called prophet inequality problem for which there is a simple pricing scheme achieving a competitive ratio of 1/2. On the other end of the spectrum, as k goes to infinity, the asymptotic performance of both static and adaptive pricing is well understood. We provide a static pricing scheme for the small-supply regime: where k is small but larger than one. Prior to our work, the best competitive ratio known for this setting was the 1/2 that follows from the single-unit prophet inequality. Our pricing scheme is easy to describe as well as practical; it is anonymous, nonadaptive, and order oblivious. We pick a single price that equalizes the expected fraction of items sold and the probability that the supply does not sell out before all customers are served; this price is then offered to each customer while supply lasts. This extends an approach introduced by Samuel-Cahn for the case of k = 1. This pricing scheme achieves a competitive ratio that increases gradually with the supply. Subsequent work shows that our pricing scheme is the optimal static pricing for every value of k. Funding: This work was supported by the National Science Foundation [Grants CCF-2008006 and SHF-1704117]. T. Lykouris would like to acknowledge funding from Google Research. [ABSTRACT FROM AUTHOR]

Revenue Management of Service Systems under Incomplete Information Revenue management with reusable resources finds many important applications in today's economy, such as cloud computing services, car/bicycle rental services, ride-hailing services, hotel management, project team management, and call center services. The existing literature predominantly assumes that the stochastic demand and service processes are given as an input to the models, and the pricing decisions are made with full knowledge of the distributional information. However, in practice, the decision maker may not know how demand or service rates react to price changes. Thus, the decision maker needs to learn the underlying mapping between prices and rates from past observations, while maximizing the total expected revenue on the fly. In "Online Learning and Pricing for Service Systems with Reusable Resources", H. Jia, C. Shi, and S. Shen developed a series of online learning algorithms for revenue management problems with reusable resources and showed that they admit an optimal regret bound. We consider a price-based revenue management problem with finite reusable resources over a finite time horizon T. Customers arrive following a price-dependent Poisson process, and each customer requests one unit of c homogeneous reusable resources. If there is an available unit, the customer gets served within a price-dependent exponentially distributed service time; otherwise, the customer waits in a queue until the next available unit. In this paper, we assume that the firm does not know how the arrival and service rates depend on posted prices, and thus it makes adaptive pricing decisions in each period based only on past observations to maximize the cumulative revenue. Given a discrete price set with cardinality P, we propose two online learning algorithms, termed batch upper confidence bound (BUCB) and batch Thompson sampling (BTS), and prove that the cumulative regret upper bound is O ˜ (P T) , which matches the regret lower bound. In establishing the regret, we bound the transient system performance upon price changes via a novel coupling argument, and also generalize bandits to accommodate subexponential rewards. We also extend our approach to models with balking and reneging customers and discuss a continuous price setting. Our numerical experiments demonstrate the efficacy of the proposed BUCB and BTS algorithms. Funding: This research was partially supported by an Amazon research award and the Department of Energy [Award DE-SC0018018]. [ABSTRACT FROM AUTHOR]

A Unified View of Online Matching and Resource Allocation Problems Whereas small regret online algorithms for applications as diverse as network revenue management (NRM), assemble-to-order (ATO) systems, and online stochastic bin packing (SBP) are known in the literature, the design of the existing algorithms are tailored to the specific application and often use the strategy of resolving a planning linear program. In the paper "Greedy Algorithm for Multiway Matching with Bounded Regret," Gupta proposes a unified model for studying such online matching/allocation problems. In the unified model, resources of three types—off-line (e.g., inventory in NRM), online-queueable (e.g., orders or resources in ATO systems), or online-nonqueueable (e.g., requests in NRM, items in SBP)—must be combined to create feasible configurations. Leveraging the unified framework, the author gives one simple greedy algorithm that gives small regret (bounded or logarithmic in time horizon) for these diverse applications under a mild nondegeneracy condition on the off-line planning problem. In this paper, we prove the efficacy of a simple greedy algorithm for a finite horizon online resource allocation/matching problem when the corresponding static planning linear program (SPP) exhibits a nondegeneracy condition called the general position gap (GPG). The key intuition that we formalize is that the solution of the reward-maximizing SPP is the same as a feasibility linear program restricted to the optimal basic activities, and under GPG, this solution can be tracked with bounded regret by a greedy algorithm, that is, without the commonly used technique of periodically resolving the SPP. The goal of the decision maker is to combine resources (from a finite set of resource types) into configurations (from a finite set of feasible configurations) in which each configuration is specified by the number of resources consumed of each type and a reward. The resources are further subdivided into three types—off-line (whose quantity is known and available at time 0), online-queueable (which arrive online and can be stored in a buffer), and online-nonqueueable (which arrive online and must be matched on arrival or lost). Under GPG, we prove that (i) our greedy algorithm gets bounded anytime regret of O (1 / ϵ 0) for matching reward (ϵ0 is a measure of the GPG) when no configuration contains both an online-queueable and an online-nonqueueable resource and (ii) O (log t) expected anytime regret otherwise (we also prove a matching lower bound). By considering the three types of resources, our matching framework encompasses several well-studied problems, such as dynamic multisided matching, network revenue management, online stochastic packing, and multiclass queueing systems. Supplemental Material: The online appendix is available at https://doi.org/10.1287/opre.2022.2400. [ABSTRACT FROM AUTHOR]

Bounded Regret for LP-Based Revenue-Management Problems In "An Improved Analysis of LP-Based Control for Revenue Management," Chen, Li, and Ye study a class of quantity-based network revenue-management problems. The authors consider a stochastic setting where all the orders are i.i.d. sampled and the customers are of finite type. They focus on the classic LP-based adaptive algorithm and consider regret as the performance measure. They found that when the underlying LP is nondegenerate, the algorithm achieves a problem-dependent regret upper bound that is independent of the horizon/number of time periods T; when the underlying LP is degenerate, the algorithm achieves a tight regret upper bound that scales on the order of T log(T) and matches the lower bound up to a logarithmic order. In this paper, we study a class of revenue-management problems, where the decision maker aims to maximize the total revenue subject to budget constraints on multiple types of resources over a finite horizon. At each time, a new order/customer/bid is revealed with a request of some resource(s) and a reward, and the decision maker needs to either accept or reject the order. Upon the acceptance of the order, the resource request must be satisfied, and the associated revenue (reward) can be collected. We consider a stochastic setting where all the orders are independent and identically distributed-sampled—that is, the reward-request pair at each time is drawn from an unknown distribution with finite support. The formulation contains many classic applications, such as the quantity-based network revenue-management problem and the Adwords problem. We focus on the classic linear program (LP)-based adaptive algorithm and consider regret as the performance measure defined by the gap between the optimal objective value of the certainty-equivalent LP and the expected revenue obtained by the online algorithm. Our contribution is twofold: (i) When the underlying LP is nondegenerate, the algorithm achieves a problem-dependent regret upper bound that is independent of the horizon/number of time periods T; and (ii) when the underlying LP is degenerate, the algorithm achieves a tight regret upper bound that scales on the order of T log (T) and matches the lower bound up to a logarithmic order. To our knowledge, both results are new and improve the best existing bounds for the LP-based adaptive algorithm in the corresponding setting. We conclude with numerical experiments to further demonstrate our findings. Supplemental Material: The online appendix is available at https://doi.org/10.1287/opre.2022.2358. [ABSTRACT FROM AUTHOR]

Latent Agents in Networks: Estimation and Targeting In "Latent Agents in Networks: Estimation and Targeting," Baris Ata, Alexandre Belloni, and Ozan Candogan address the problem of estimating network effects in a setting in which data only on a subset of agents is available. In this setting, the observable agents influence each other's outcomes both directly and indirectly through their influence on the latent agents. Even in sparse networks, the combination of direct and indirect network effects yields a nonsparse influence structure that makes estimation challenging. The authors overcome this challenge and provide an estimation algorithm that performs well in high-dimensional settings. They also establish convergence rates for their proposed estimator and show that their performance guarantees are valid for a large class of networks. Finally, the authors demonstrate the application of their algorithm to a targeted advertising problem, in which it can be used to obtain asymptotically optimal advertising decisions despite the presence of latent agents. We consider a platform that serves (observable) agents, who belong to a larger network that also includes additional agents who are not served by the platform. We refer to the latter group of agents as latent agents. Associated with each agent are the agent's covariate and outcome. The platform has access to past covariates and outcomes of the observable agents, but no data for the latent agents is available to the platform. Crucially, the agents influence each other's outcome through a certain influence structure. In particular, observable agents influence each other both directly and indirectly through the influence they exert on the latent agents. The platform doesn't know the inference structure of either the observable or the latent parts of the network. We investigate how the platform can estimate the dependence of the observable agents' outcomes on their covariates, taking the presence of the latent agents into account. First, we show that a certain matrix succinctly captures the relationship between the outcomes and the covariates. We provide an algorithm that estimates this matrix using historical data of covariates and outcomes for the observable agents under a suitable approximate sparsity condition. We also establish convergence rates for the proposed estimator despite the high dimensionality that allows more agents than observations. Second, we show that the approximate sparsity condition holds under the standard conditions used in the literature. Hence, our results apply to a large class of networks. Finally, we illustrate the applications to a targeted advertising problem. We show that, by using the available historical data with our estimator, it is possible to obtain asymptotically optimal advertising decisions despite the presence of latent agents. Funding: O. Candogan acknowledges NSF award 2216912 for "Institute for Data, Econometrics, Algorithms and Learning". Supplemental Material: The online appendix is available at https://doi.org/10.1287/opre.2023.2485. [ABSTRACT FROM AUTHOR]

There is an error in one of the results of our paper [Huettner F, Boyacı T, Akçay Y (2019) Consumer choice under limited attention when alternatives have different information costs. Oper. Res. 67(3):671–699]. In this erratum, we point out the error and provide a correction based on Walker-Jones [(2023) Rational inattention with multiple attributes. J. Econom. Theory 212:105688]. Our key characterizations, insights, and numerical examples do not depend on this error and, hence, remain valid. The main implication is on the stopping condition used in the algorithm. We propose a fix based on the new sufficient condition and, if needed, standard convex optimization techniques. [ABSTRACT FROM AUTHOR]

An assumption that is pervasive in revenue management and economics is that buyers are perfect optimizers. However, in practice, buyers may be limited by their computational capabilities or lack of information and may not be able to perfectly optimize their response to a selling mechanism. This has motivated the introduction of approximate incentive compatibility as a solution concept for practical mechanisms. In "Mechanism Design under Approximate Incentive Compatibility," Balseiro, Besbes, and Castro study, for the first time, the problem of designing optimal selling mechanisms when buyers are imperfect optimizers. Their work characterizes structural properties of approximate incentive compatible mechanisms and establishes fundamental bounds on how much revenue can be garnered by moving from exact to approximate incentive constraints. Their work brings a new perspective to the theory of mechanism design by shedding light on a novel class of optimization problems, techniques, and challenges that emerge when relaxing incentive constraints. A fundamental assumption in classical mechanism design is that buyers are perfect optimizers. However, in practice, buyers may be limited by their computational capabilities or a lack of information and may not be able to perfectly optimize their response to a mechanism. This has motivated the introduction of approximate incentive compatibility (IC) as an appealing solution concept for practical mechanism design. Although most of the literature has focused on the analysis of particular approximate IC mechanisms, this paper is the first to study the design of optimal mechanisms in the space of approximate IC mechanisms and to explore how much revenue can be garnered by moving from exact to approximate incentive constraints. In particular, we study the problem of a seller facing one buyer with private values and analyze optimal selling mechanisms under ε-incentive compatibility. We establish that the gains that can be garnered depend on the local curvature of the seller's revenue function around the optimal posted price when the buyer is a perfect optimizer. If the revenue function behaves locally like an α-power for α ∈ (1 , ∞) , then no mechanism can garner gains higher than order ε α / (2 α − 1) . This improves on state-of-the-art results that imply maximum gains of ε 1 / 2 by providing the first parametric bounds that capture the impact of revenue function's curvature on revenue gains. Furthermore, we establish that an optimal mechanism needs to randomize as soon as ε > 0 and construct a randomized mechanism that is guaranteed to achieve order ε α / (2 α − 1) additional revenues, leading to a tight characterization of the revenue implications of approximate IC constraints. Our study sheds light on a novel class of optimization problems and the challenges that emerge when relaxing IC constraints. In particular, it brings forward the need to optimize not only over allocations and payments but also over best responses, and we develop a new framework to address this challenge. Supplemental Material: The online appendix is available at https://doi.org/10.1287/opre.2022.2359. [ABSTRACT FROM AUTHOR]

For a variety of practical reasons, including ease of understanding and familiarity for customers, firms use static-pricing algorithms in which product prices remain unchanged over time. In a multiproduct setting with no demand substitutability or complementarity between products, prior work has shown that static-pricing algorithms can offer excellent performance. In "A Note on State-Independent Policies in Network Revenue Management," Manchiraju, Dawande, and Janakiraman extend that work and show that static-pricing algorithms offer a near-optimal performance even in the presence of demand substitutability and complementarity. We revisit two classical price-based and choice-based network revenue management problems studied in the literature. The setting for the problems is as follows: A firm sells multiple products over a finite horizon using a limited supply of resources. Product demands are stochastic. The demand rate for each product depends on the current price-vector (respectively, assortment displayed). The firm's goal is to obtain a pricing (respectively, assortment) policy that maximizes its expected revenue. The main result for the price-based problem is that the optimality gaps incurred by two state-independent policies scale proportionally to k , where k is the scale of demand and supply. The analysis in the literature implicitly assumes that the demand-price relationship is separable among the products. In this paper, we derive these results for the more general setting where the demand-price relationship need not be separable. We also consider an important practical variant of the price-based problem in which the price of each product is restricted to a discrete and finite set and show the k result for this problem. For the choice-based problem, to our knowledge, there is no result in the literature on the asymptotic convergence rate of any policy. We show that this problem is mathematically equivalent to the discrete-price variant of the price-based problem and use this equivalence to show that the choice-based deterministic linear program policy in the literature for the choice-based problem also inherits the k bound on the optimality gap. Supplemental Material: The online appendix is available at https://doi.org/10.1287/opre.2023.2471. [ABSTRACT FROM AUTHOR]

In Dynamic Pricing with Customer State Dependence, Wen Chen, Ying He, and Saurabh Bansal discuss optimal prices that a firm should offer to customers who develop a habit or satiation from consumption. At a high discount (or equivalently a lower price), a habit-prone customer will purchase a large amount in a current period. The firm will earn a low revenue per unit on the amount bought by the customer in this period. However, this large purchase will also create a stronger habit in the customer that the firm can exploit in the future periods. At a low discount, the firm will earn a higher per unit revenue in this period. However, the lower purchase quantity will also result in a weaker habit in the customer for the future periods. This tradeoff exists in every period. These effects are reversed for a satiation-prone customer. Using an analytical model, the authors determine the optimal profit-maximizing dynamic prices that a firm should offer to such habit- or satiation-prone customers. The results are robust for various specifications for habit formation, and yet in each specification they are obtainable tractably. We study a dynamic pricing problem in which a firm chooses prices over multiple periods when consumers are state dependent; that is, they develop a habit or satiation from their past consumption. We first derive an intertemporal demand function to capture how demand in one period depends on the price in that period and consumption in previous periods through habit or satiation. Subsequently, we formulate the optimal price setting problem for a firm over a multiperiod horizon. We establish that this problem is jointly concave in prices and then characterize the temporal trends in the optimal prices. These trends in optimal prices are a net outcome of two opposite effects: (i) the progressive buildup of habit or satiation from consumption, and (ii) the progressive deterioration of the habit or satiation developed in prior periods. Based on the relative strengths of these two effects, the optimal prices follow a penetration policy (prices increase over time), a skimming policy (prices decrease over time), a skimming-penetration policy (U-shaped prices), or a penetration-skimming policy (inverse U-shaped prices). Subsequently, we provide several extensions including bounds on prices and optimal profit and nonstationary state dependence. Numerical studies show that ignoring habit and satiation effects in customers can be significantly costly for a firm. Supplemental Material: The online appendices are available at https://doi.org/10.1287/opre.2022.2412. [ABSTRACT FROM AUTHOR]

Alaei et al. consider the problem of a streaming platform that offers different set of contents with different subscription fees with the goal of maximizing revenue. They characterize the necessary and sufficient condition for the consumer preferences under which a single-tier subscription is optimal. In particular, they show the preferences of the consumers for different contents must be aligned for a single-tier subscription to be optimal. This condition is often violated in practice, establishing the suboptimality of a single-tier offering. They further show that a subscription fee proportional to the number of contents is near-optimal. We consider a media service provider that gives users access to digital goods through subscription. In our model, different types of users with heterogeneous usage rates repeatedly use a platform over a period of time. There are multiple item types on the platform, and the value of an item to a user is random and depends on both the user type and the item type. The design of the platform's subscription planning comprises selecting a subscription fee for each set of item types. Before the beginning of the subscription period, given the subscription planning, users decide which set of item types to subscribe to (if any). During the subscription period, a user pays zero price to use an item if it has subscribed to a set that includes it and pays its rental price otherwise. For an exogenously given rental price, we establish the sufficient and necessary condition for the optimality of grand subscription—offering a single subscription set that includes all items. We then consider a setting in which the platform chooses both the subscription fee for each set of item types and the rental price of each item type and establish that there exist subscription fees proportional to the cardinality of each set of item types (with no rental offers) that achieve a logarithmic approximation (in the number of item types) of the optimal revenue. Finally, we demonstrate that our performance guarantee is tight for a class of problem instances. Supplemental Material: The online appendix is available at https://doi.org/10.1287/opre.2023.2468. [ABSTRACT FROM AUTHOR]

Similar to individual investors, firms balance revenue or profit risk with the expected return on investment. A stable cash flow is required to satisfy private and public shareholders or to maintain solvency. Product prices impact both the expected demand for the products and the volatility of the demand, and consequently a firm's revenue or profit risk. This paper presents models and results that demonstrate how risk sensitivity can inform pricing strategy. The authors show that a firm's distaste for risk not only causes the firm to discount its products in exchange for lower profit volatility, but also reduces the firm's incentive to price differentiate among the products. The findings also provide insight into how firms with varying degrees of risk aversion may price products of different quality and how this pricing strategy affects product market share. We examine a firm's pricing decision when managing a broad product line with the goal of optimally balancing the expected return on product investment with the revenue or profit risk associated with uncertain customer choices. We consider the multinomial logit (MNL) model and the mean-variance objective function and illustrate how the level of risk tolerance influences the firm's optimal markups. We show that the solution approach and results generalize to the nested logit (NL) choice model and alternative risk-adjusted objectives. This paper is the first in the literature addressing risk-sensitive pricing under discrete choice models. Our analysis presents how the firm's optimal pricing decision evolves with increasing risk sensitivity. The optimal risk-balancing solution stands in contrast to the profit-maximizing solution: for example, (i) the firm's distaste for risk not only causes the firm to discount its products in exchange for lower profit volatility but also reduces the firm's incentive to price differentiate among the products; (ii) although risk drives the firm to attain a higher total market share through lower prices at the cost of lower profit, certain products may gain, whereas others may lose in market share; and (iii) the optimal risk-balancing markups follow the sequence of product quality, whereas the optimal adjusted markups (i.e., markups adjusted for product-specific price sensitivity) follow the reverse sequence of quality. Supplemental Material: The online appendices are available at https://doi.org/10.1287/opre.2023.2465. [ABSTRACT FROM AUTHOR]

Scheduling Advertising on Cable Television Advertisement scheduling is a daily essential operational process in the television business. Efficient distribution of viewers among advertisers allows the television network to satisfy contracts and increase ad sale revenues. Ad scheduling is a challenging multiperiod, mixed-integer programming problem in which the network must create schedules to meet advertisers' campaign goals and maximize ad revenues. Each campaign must meet a specific target group of viewers and a unique set of constraints. Moreover, the number of viewers is uncertain. To solve this problem, S. Souyris, S. Seshadri, and S. Subramanian develop and implement a practical approach that combines mathematical programming and machine learning to create daily schedules. According to standard business metrics and the small integer programming gap, these schedules are of high quality. Using their methods, leading networks in the United States and India experience a 3% to 5% revenue increase, which translates to about $60 million annually for one prominent user. Advertisement scheduling is a daily essential operational process in the television business. Efficient distribution of viewers among advertisers allows the television network to satisfy contracts and increase ad sale revenues. Ad scheduling is a challenging multiperiod, mixed-integer programming problem in which the network must create schedules to meet advertisers' campaign goals and maximize ad revenues. Each campaign must meet a specific target group of viewers and a unique set of constraints. Moreover, the number of viewers is uncertain. To solve this problem, we develop and implement a practical approach that combines mathematical programming and machine learning to create daily schedules. These schedules are of high quality according to standard business metrics and the small integer programming gap. Leading networks in the United States and India using our methods experience a 3%–5% revenue increase. Supplemental Material: The e-companion is available at https://doi.org/10.1287/opre.2022.2430. [ABSTRACT FROM AUTHOR]

There are a variety of revenue management systems that require making pricing or availability decisions for unique resources. For example, lodging marketplaces, boutique hotels, and bed-and-breakfasts offer unique rooms, apartments, or houses. Matching platforms for freelancers recommend differentiated workers with unique characteristics. When managing unique resources, one has to keep track of the availability of each resource at each time point in the future. Moreover, if the customers substitute between different resources, then the pricing and availability decisions for all resources become interdependent. Thus, it can be challenging to find good policies to make pricing or availability decisions. In "Revenue Management with Heterogeneous Resources: Unit Resource Capacities, Advance Bookings, and Itineraries over Time Intervals," Rusmevichientong, Sumida, Topaloglu, and Bai consider revenue management problems when unique resources are requested for use over intervals of time under advance reservations. Using the interval structure of resource requests, they give policies with performance guarantees. We study revenue management problems with heterogeneous resources, each with unit capacity. An arriving customer makes a booking request for a particular interval of days in the future. We offer an assortment of resources in response to each booking request. The customer makes a choice within the assortment to use the chosen resource for her desired interval of days. The goal is to find a policy that determines an assortment of resources to offer to each customer to maximize the total expected revenue over a finite selling horizon. The problem has two useful features. First, each resource is unique with unit capacity. Second, each customer uses the chosen resource for a number of consecutive days. We consider static policies that offer each assortment of resources with a fixed probability. We show that we can efficiently perform rollout on any static policy, allowing us to build on any static policy and construct an even better policy. Next, we develop two static policies, each of which is derived from linear and polynomial approximations of the value functions. We give performance guarantees for both policies, so the rollout policies based on these static policies inherit the same guarantee. Last, we develop an approach for computing an upper bound on the optimal total expected revenue. Our results for efficient rollout, static policies, and upper bounds all exploit the aforementioned two useful features of our problem. We use our model to manage hotel bookings based on a data set from a real-world boutique hotel, demonstrating that our rollout approach can provide remarkably good policies and our upper bounds can significantly improve those provided by existing techniques. Funding: This work was supported by the National Science Foundation [Grants CMMI-1824860 and CMMI-1825406]. Supplemental Material: The online appendices are available at https://doi.org/10.1287/opre.2022.2427. [ABSTRACT FROM AUTHOR]

Many sequential decision problems have a weakly coupled structure in that a set of linking constraints couples an otherwise independent collection of subproblems. This structure arises in a wide variety of applications, such as network revenue management, online advertising, assortment planning, interactive marketing, optimization of power systems, and multilocation inventory management to name only a few. Such problems can be modeled as dynamic programs but are quite difficult to solve. Two widely studied approximation methods are approximate linear programs, which involve finding a best approximation of total value that is additive across the subsystems, and Lagrangian relaxations, which involve relaxing the linking constraints. It is well known that both of these approaches provide upper bounds to the optimal value, and the approximate linear programming approach is a better bound but also, more difficult to compute. In this paper, we provide a detailed theoretical analysis of these two approximations and show that, under fairly broad conditions, these two approximations lead to upper bounds that are very close and often identical. Our theory suggests that, between these two approximations, Lagrangian relaxations should usually be the preferred choice for researchers studying applications involving weakly coupled dynamic programs. Many stochastic dynamic programs (DPs) have a weakly coupled structure in that a set of linking constraints in each period couples an otherwise independent collection of subproblems. Two widely studied approximations of such problems are approximate linear programs (ALPs), which involve optimizing value function approximations that additively separate across subproblems, and Lagrangian relaxations, which involve relaxing the linking constraints. It is well known that both of these approximations provide upper bounds on the optimal value function in all states and that the ALP provides a tighter upper bound in the initial state. The purpose of this short paper is to provide theoretical justification for the fact that these upper bounds are often close if not identical. We show that (i) for any weakly coupled DP, the difference between these two upper bounds—the relaxation gap—is bounded from above in terms of the integrality gap of the separation problems associated with the ALP. (ii) If subproblem rewards are uniformly bounded and some broadly applicable conditions on the linking constraints hold, the relaxation gap is bounded from above by a constant that is independent of the number of subproblems. (iii) When the linking constraints are independent of subproblem states and have a unimodular structure, the relaxation gap equals zero. The conditions for (iii) hold in several widely studied problems: generalizations of restless bandit problems, online stochastic matching problems, network revenue management problems, and price-directed control of relocating resources. These findings generalize and unify existing results. Supplemental Material: The online appendix is available at https://doi.org/10.1287/opre.2022.2287. [ABSTRACT FROM AUTHOR]

When the number of tasks is large, how should a firm design reward and penalty schemes to incentivize its employees? In "Dynamic Mechanism Design with Capacity Constraint," He studies the role of capacity constraint in a project assignment problem, where a principal needs to assign multiple tasks to an agent. The author fully characterizes the optimal mechanism via a sequence of deadlines. This characterization is used to show that the presence of the capacity constraint reduces the principal's payoff and delays the completion of projects. It further illustrates that the widely adopted no-capacity constraint framework may provide inaccurate results in various dynamic problems. We study a project assignment problem, where a principal needs to assign multiple projects to an agent. The agent is privately informed about the cost, which could be high or low. The agent's type evolves stochastically over time. We fully characterize the optimal mechanism via a sequence of deadlines and show that the presence of the capacity constraint reduces the principal's payoff and delays the assignment of projects. In particular, as the number of projects increases, the limit optimal contract may be strictly bounded away from the optimal contract when there are infinitely many projects, and the principal's payoff may be strictly below that in the setting without the capacity constraint. Funding: This work was supported by the National Natural Science Foundation of China [Grant 72122023]. Supplemental Material: The online appendix is available at https://doi.org/10.1287/opre.2023.2449. [ABSTRACT FROM AUTHOR]

Professional service firms (PSFs) such as management consulting, law, accounting, investment banking, architecture, advertising, and home-repair companies provide services for complicated turnkey projects. A firm bids for a project and, if successful in the bid, assigns employees 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 assigned to the project are committed ex ante, as part of the bid, and a qualityreputation setup, where the bid'swin probability depends on past performance, say, an average of the quality of past jobs. We firstmodel a stylizedMarkov chainmodel of the problem amenable to analysis and showthat up-front revelation of the assigned employees has subtle advantages. Subsequent to this analysis, we develop an operational stochastic dynamic programming framework under the revelationmodel to aid the firmin this bidding and assignment process. We show that the problem is computationally challenging and provide a series of bounds and solution methods to approximate the stochastic dynamic program. Based on our model and computational methods, we are able to address a number of interesting business questions for a PSF, such as the optimal utilization levels and the value of each employee type. Our methodology provides management with a tool kit for bidding on projects aswell as to performworkforce analytics and tomake staffing decisions. [ABSTRACT FROM AUTHOR]

Online multiproduct sellers increasingly use interactive selling strategies to customize their offers to individual buyers. For example, a seller may adjust the prices of products dynamically based on user interaction and offer discounts for buying bundles of products. What selling strategy should such a seller use to maximize profit? In "Sequential Mechanisms with ex Post Individual Rationality," I. Ashlagi, C. Daskalakis, and N. Haghpanah provide a recursive characterization of the optimal selling strategy. This characterization is used to identify conditions under which the ability to bundle products is less profitable for the seller than the ability to adjust prices dynamically. We study optimal mechanisms for selling multiple products to a buyer who learns her values for those products sequentially. A mechanism may use static prices or adjust them over time, and it may sell the products separately or as bundles. We study mechanisms that provide the buyer a nonnegative ex post utility. We show that there exists an optimal mechanism that determines the allocation of each product as soon as the buyer learns her value for that product. This observation allows us to solve for optimal mechanisms recursively. We use this recursive characterization to show that static mechanisms are suboptimal if the buyer first learns her values for products that are ex ante less valuable. Under this condition, the ability to bundle products is less profitable than the ability to adjust prices dynamically. Funding: This work was supported by ONR [Grant N00014-12-1-0999] and NSF Awards CCF-0953960 (CAREER), CCF-1551875 and SES-1254768. Part of this work was done while the authors were visiting the Simons Institute for Theory of Computing. Supplemental Material: The e-companion is available at https://doi.org/10.1287/opre.2022.2332. [ABSTRACT FROM AUTHOR]

A Novel Class of Robust and Fast Algorithms for Online Allocation Problems A central problem in operations research is allocating limited resources sequentially to maximize cumulative rewards. Applications abound and include network revenue management and internet advertising among many others. Existing data-driven algorithms are tailored for convex settings with either adversarial or stochastic inputs. Many modern applications of online allocations problems, however, are nonconvex. Furthermore, algorithms for adversarial inputs may be too conservative in practice, whereas algorithms for stochastic inputs can perform poorly when the model is misspecified. In the paper "The Best of Many Worlds: Dual Mirror Descent for Online Allocation Problems," Balseiro, Lu, and Mirrokni present a novel class of algorithms for nonconvex online allocation problems that attain good performance simultaneously in stochastic and adversarial input models and also in various nonstationary settings. The resulting algorithms are simple, fast, and robust to noise and corruption in the observations, in contrast to existing methods from the literature. Online allocation problems with resource constraints are central problems in revenue management and online advertising. In these problems, requests arrive sequentially during a finite horizon and, for each request, a decision maker needs to choose an action that consumes a certain amount of resources and generates reward. The objective is to maximize cumulative rewards subject to a constraint on the total consumption of resources. In this paper, we consider a data-driven setting in which the reward and resource consumption of each request are generated using an input model that is unknown to the decision maker. We design a general class of algorithms that attain good performance in various input models without knowing which type of input they are facing. In particular, our algorithms are asymptotically optimal under independent and identically distributed inputs as well as various nonstationary stochastic input models, and they attain an asymptotically optimal fixed competitive ratio when the input is adversarial. Our algorithms operate in the Lagrangian dual space: they maintain a dual multiplier for each resource that is updated using online mirror descent. By choosing the reference function accordingly, we recover the dual subgradient descent and dual multiplicative weights update algorithm. The resulting algorithms are simple, fast, and do not require convexity in the revenue function, consumption function, and action space, in contrast to existing methods for online allocation problems. We discuss applications to network revenue management, online bidding in repeated auctions with budget constraints, online proportional matching with high entropy, and personalized assortment optimization with limited inventory. Supplemental Material: The online appendices are available at https://doi.org/10.1287/opre.2021.2242. [ABSTRACT FROM AUTHOR]

Dynamic Personalized Decision Making Beyond the Super-Extrapolatable and Super-Local Cases Contextual bandit problems model the inherent trade-off between exploration and exploitation in personalized decision making in marketing, healthcare, revenue management, and more. Specifically, the trade-off is characterized by the optimal growth rate of the regret. Intuitively, the optimal rate should depend on how complex the underlying supervised learning problem is, namely, how much can observing reward in one context tell us about mean rewards in another. To formalize this intuitive relationship, Hu, Kallus, and Mao study in "Smooth Contextual Bandits: Bridging the Parametric and Nondifferentiable Regimes" a nonparametric contextual bandit problem in which mean reward functions are β-times differentiable (more generally, Hölder β-smooth). This interpolates between two extremes previously studied in isolation: nondifferentiable bandits (β ≤ 1), with which running separated noncontextual bandits in different context regions achieves rate-optimal regret, and parametric-response bandits (β = ∞), with which rate-optimal regret can be achieved with minimal or no exploration because of infinite extrapolatability across contexts. The authors develop a rate-optimal algorithm that operates neither fully locally nor fully globally, revealing the optimal regret rate in this in-between smooth setting and shedding light on the crucial interplay of functional complexity and regret in dynamic personalized decision making. We study a nonparametric contextual bandit problem in which the expected reward functions belong to a Hölder class with smoothness parameter β. We show how this interpolates between two extremes that were previously studied in isolation: nondifferentiable bandits (β at most 1), with which rate-optimal regret is achieved by running separate noncontextual bandits in different context regions, and parametric-response bandits (infinite β), with which rate-optimal regret can be achieved with minimal or no exploration because of infinite extrapolatability. We develop a novel algorithm that carefully adjusts to all smoothness settings, and we prove its regret is rate-optimal by establishing matching upper and lower bounds, recovering the existing results at the two extremes. In this sense, our work bridges the gap between the existing literature on parametric and nondifferentiable contextual bandit problems and between bandit algorithms that exclusively use global or local information, shedding light on the crucial interplay of complexity and regret in contextual bandits. Funding: N. Kallus acknowledges support from the National Science Foundation [Grant 1846210]. X. Mao acknowledges support from the National Science Foundation of China [Grant 72201150, Grant 72293561]. Supplemental Material: The online appendix is available at https://doi.org/10.1287/opre.2021.2237. [ABSTRACT FROM AUTHOR]

Title: Constant Regret Resolving Heuristics for Price-Based Revenue Management Network revenue management (NRM) and its corresponding pricing question is one of the most fundamental problems in operations management. To alleviate the curse of dimensionality and the prohibitive cost of computing an exact solution using dynamic programming, computationally efficient resolving algorithms are proposed. The state-of-the-art analysis of the resolving heuristic establishes a logarithmic additive regret for price-based NRM problems. In "Constant Regret Resolving Heuristics for Price-Based Revenue Management," Y. Wang and H. Wang from the University of Florida and Georgia Institute of Technology, respectively, significantly advance the state-of-the-art analysis by showing a constant regret for resolving heuristics. Their theoretical advance is made possible by a novel, direct analysis of the exact DP solution. Price-based revenue management is an important problem in operations management with many practical applications. The problem considers a seller who sells one or multiple products over T consecutive periods and is subject to constraints on the initial inventory levels of resources. Whereas, in theory, the optimal pricing policy could be obtained via dynamic programming, computing the exact dynamic programming solution is often intractable. Approximate policies, such as the resolving heuristics, are often applied as computationally tractable alternatives. In this paper, we show the following two results for price-based network revenue management under a continuous price set. First, we prove that a natural resolving heuristic attains O(1) regret compared with the value of the optimal policy. This improves the O (ln T) regret upper bound established in the prior work by Jasin in 2014. Second, we prove that there is an Ω (ln T) gap between the value of the optimal policy and that of the fluid model. This complements our upper bound result by showing that the fluid is not an adequate information-relaxed benchmark when analyzing price-based revenue management algorithms. Funding: This work was supported in part by the National Science Foundation [Grant CMMI-2145661]. [ABSTRACT FROM AUTHOR]

A Novel and Promising Approximation for Network Revenue Management In "Product-Based Approximate Linear Programs for Network Revenue Management," Zhang, Samiedaluie, and Zhang propose a novel separable piecewise linear (SPL) approximation for the network revenue management problem. The coefficients of the proposed SPL approximation can be interpreted as each product's revenue contribution to the value of each resource in a given period, which provides more granular information compared with the existing resource-based SPL approximation in the literature. The new approximation provides more flexibility for policy construction. Furthermore, the new approximation opens the opportunity to derive a set of valid inequalities to further improve the computational performance and achieve additional gains in the expected revenue. Computational experiments with instances of various network structures and parameters demonstrate its efficacy: the new approximation leads to bid-price policies generating higher expected revenues and demonstrates better performance in terms of both computational efficiency and numerical stability. The approximate linear programming approach has received significant attention in the network revenue management literature. A popular approximation in the existing literature is separable piecewise linear (SPL) approximation, which estimates the value of each unit of each resource over time. SPL approximation can be used to construct resource-based bid-price policies. In this paper, we propose a product-based SPL approximation. The coefficients of the product-based SPL approximation can be interpreted as each product's revenue contribution to the value of each unit of each resource in a given period. We show that the resulting approximate linear program admits compact reformulations, such as its resource-based counterpart. Furthermore, the new approximation allows us to derive a set of valid inequalities to (i) speed up the computation and (ii) select optimal solutions to construct more effective policies. We conduct an extensive numerical study to illustrate our results. In a set of 192 problem instances, bid-price policies based on the new approximation generate higher expected revenues than resource-based bid-price policies with an average revenue lift of 0.72% and a maximum revenue lift of 5.3%. In addition, the new approximation can be solved 1.42 times faster than the resource-based approximation and shows better numerical stability. The valid inequalities derived from the new approximation further improve the computational performance and are critical for achieving additional gains in the expected revenue. The policy performance is competitive compared with the dynamic programming decomposition method, which is the strongest heuristic known in the literature. [ABSTRACT FROM AUTHOR]

Allocating scarce resources with (weak) priority and complex constraints has many applications ranging from course allocation, and healthcare rationing to refugee resettlement. Its generality, however, mostly leads to impossibility results. We offer a positive result with a mechanism based on a new concept called competitive stable equilibrium. This is a natural extension of competitive equilibrium with endowed budgets that accommodates weak priorities. Specifically, an agent only needs to pay for a resource if it belongs to the last tier among the agents currently consuming the resource. This concept applies to both frameworks of one-sided and two-sided markets in a unifying way and allows for a more flexible tie-breaking rule by giving agents different budgets. We empirically apply our mechanism to reassign season tickets to families in the presence of social distancing. Our simulation results show that our method outperforms existing ones in both efficiency and fairness measures. We consider a resource allocation problem that combines three general features: complex resource constraints, weak priority rankings over the agents, and ordinal preferences over bundles of resources. We develop a mechanism based on a new concept called competitive stable equilibrium. It has several attractive properties, commonly captures two different frameworks of one-sided and two-sided markets, and extends them to richer environments. Our framework also allows for an alternative and more flexible tie-breaking rule by giving agents different budgets. We empirically apply our mechanism to reassign season tickets to families in the presence of social distancing. Our simulation results show that our method outperforms existing ones in both efficiency and fairness measures. [ABSTRACT FROM AUTHOR]

In "Bifurcating Constraints to Improve Approximation Ratios for Network Revenue Management with Reusable Resources," Baek and Ma provide a unified framework for dynamically allocating reusable resources over time in the general network revenue management setting. That is, each incoming query is allowed to request an arbitrary combination of resources for different unknown durations, capturing applications like cloud computing and the dispatching of human resources. Through this framework, they derive simple algorithms that achieve the same approximation ratios as existing algorithms, which only allow queries to request one resource. Their framework also suggests a meta-algorithm for "bifurcating" the resources depending on the network structure and then using two different algorithms for controlling the capacities of two different groups of resources. This contrasts existing "one-size-fits-all" approaches to network revenue management and is demonstrated to improve both theoretical guarantees and empirical performance over a wide variety of instances. Network revenue management (NRM) describes a general online allocation problem in which combinations of capacity-constrained resources are sold to a stream of arriving customers. Existing papers propose one-size-fits-all methods for controlling the resource capacities over time. In this paper, we study how different methods can be used to control different resource constraints based on the network structure of each instance. Specifically, we propose a heuristic that "bifurcates" the resources of a given NRM instance into a structured part resembling a matroid and an unstructured part. We then derive an NRM policy with an approximation ratio of 1 / (2 (1 + L ′)) , where L ′ denotes the maximum number of distinct unstructured resources required by a customer. Our approach improves theoretical and empirical performance both in applications where the structured constraints arise naturally and in randomly generated NRM instances where the structured constraints must be found by our heuristic. Along the way, our paper also provides a unified framework for analyzing NRM problems, which simplifies existing results and allows for the resources to be reusable. [ABSTRACT FROM AUTHOR]

Customers are sensitive to price when they shop from a group of substitutable products. Specifically, they are often attracted to the cheapest product in the group, even when the price difference to the next cheapest product is small. Such a phenomenon has been long noticed by the airline industry when customers purchase airline tickets. In "Network Revenue Management under a Spiked Multinomial Logit Choice Model," Cao, Kleywegt, and Wang consider a new choice model to incorporate customers' preference toward the cheapest product, which extends the popular multinomial logit choice model. They find that using this new choice model may improve airlines' revenue. Moreover, (near) optimal revenue management policies under this choice model can be computed in an efficient manner. Airline booking data have shown that the fraction of customers who choose the cheapest available fare class often is much greater than that predicted by the multinomial logit choice model calibrated with the data. For example, the fraction of customers who choose the cheapest available fare class is much greater than the fraction of customers who choose the next cheapest available one, even if the price difference is small. To model this spike in demand for the cheapest available fare class, a choice model called the spiked multinomial logit (spiked-MNL) model was proposed. We study a network revenue management problem under the spiked-MNL choice model. We show that efficient sets, that is, assortments that offer a Pareto-optimal tradeoff between revenue and resource use, are nested-by-revenue when the spike effect is nonnegative. We use this result to show how a deterministic approximation of the stochastic dynamic program can be solved efficiently by solving a small linear program. The solution of the small linear program is used to construct a booking limit policy, and we prove that the policy is asymptotically optimal. This is the first such result for a booking limit policy under a choice model, and our proof uses an approach that is different from those used for previous asymptotic optimality results. Finally, we evaluate different revenue management policies in numerical experiments using both synthetic and airline data. [ABSTRACT FROM AUTHOR]

Efficient and Profit-Maximizing Dynamic Double Auctions for Two-Sided Markets Two-sided markets that enable sellers and buyers to trade have received considerable attention in the past decade. Prominent examples include online advertising, freelancing, and ride-hailing. In these markets, trade is coordinated by an intermediating platform that determines which parties should trade, collects payments from buyers, and transfers payments to sellers. How should trading mechanisms be designed when agents repeatedly trade over time? In the paper "Dynamic Double Auctions: Toward First Best," Balseiro, Mirrokni, Paes Leme, and Zuo design dynamic double auctions that satisfy the following practical requirements: no positive transfers, that is, the platform never asks sellers to make payments nor are buyers ever paid; and periodic individual rationality, that is, agents should derive a nonnegative utility from every trade opportunity. This work provides mechanisms satisfying these requirements that, as the number of trading opportunities grows, are asymptotically efficient, budget balanced, and allow to extract the welfare generated by the market as profit. We study the problem of designing dynamic double auctions for two-sided markets in which a platform intermediates the trade between one seller offering independent items to multiple buyers, repeatedly over a finite horizon, when agents have private values. Motivated by online platforms for advertising, ride-sharing, and freelancing markets, we seek to design mechanisms satisfying the following properties: no positive transfers, that is, the platform never asks the seller to make payments nor are buyers ever paid, and periodic individual rationality, that is, every agent derives a nonnegative utility from every trade opportunity. We provide mechanisms satisfying these requirements that are asymptotically efficient and budget balanced with high probability as the number of trading opportunities grows. Our mechanisms thus overcome well-known impossibility results preventing efficient bilateral trade without subsidies in static environments. Moreover, we show that the average expected profit obtained by the platform under these mechanisms asymptotically approaches "first best" (the maximum possible welfare generated by the market). We also extend our approach to general environments with complex, combinatorial preferences. [ABSTRACT FROM AUTHOR]

Dynamic pricing is a well-known revenue management technique used by firms to maximize their revenues. In industries such as fashion retail and airlines, it is observed in practice that firms vary the prices of their products, through time, only among certain pre-fixed discrete price points; for example, in fashion retail, products are first sold at a base price and then later at, say, 10%, 20%, 30% discounted prices. In such discrete-price practices, when the number of products offered by a firm is large, it is mathematically challenging to determine the optimal pricing decisions. In "Multiproduct Pricing with Discrete Price Sets," Manchiraju, Dawande, and Janakiraman design pricing algorithms that are fast and result in near-optimal revenues. We study a multiproduct pricing problem in which the prices of the products are restricted to discrete and finite sets. The demand for a product is a function of the prices of all the products. The prices of the products can be changed through time, subject to the aggregate consumption of each resource not exceeding its availability over the planning horizon. The focus of our work is the deterministic variant of this problem (wherein customer-arrival rates are deterministic), which is a key subproblem whose solution can be used to build effective policies for the stochastic variant (as in Gallego and Van Ryzin 1997). When the demand rate of each product is a concave function of the prices, we obtain an efficient and effective solution to the deterministic problem; the worst-case optimality gap of our solution depends on the curvature of the objective function. We obtain a similar performance guarantee for our solution under the linear attraction demand model and a special case of the multinomial logit (MNL) demand model. For a general demand function, the worst-case optimality gap of our solution depends on the curvature of both the objective function and the demand function. For the special case where the demand rate of a product depends only on its own price and not on the prices of the other products, we show that the deterministic problem can be efficiently solved via a linear program. [ABSTRACT FROM AUTHOR]

In the paper "The Multinomial Logit Model with Sequential Offerings: Algorithmic Frameworks for Product Recommendation Displays," we consider a sequential assortment problem that has applications ranging from appointment scheduling in hospitals, restaurants, and fitness centers to product recommendation in e-commerce settings. Our main contribution comes in the form of a strongly polynomial-time approximation scheme for the most general form of the problem. We also conduct an extensive case study in which we fit our sequential model to historical search data from Expedia's hotel booking platform. We observe substantial gains in fitting accuracy when our model is benchmarked against other well-known choice models designed for the setting at hand. In this paper, we consider the assortment problem under the multinomial logit (MNL) model with sequential offerings recently proposed by Liu et al. [INFORMS J. Comput., 2020] to capture a multitude of applications, ranging from appointment scheduling in hospitals, restaurants, and fitness centers to product recommendations in e-commerce settings. In this problem, the purchasing dynamics of customers sequentially unfold over T stages. Within each stage, the retailer selects an assortment of products to make available for purchase with the intent of maximizing expected revenue. However, motivated by practical applications, the caveat is that each product can be offered in at most one stage. Moving from one stage to the next, the customer either purchases one of the currently offered products according to MNL preferences and leaves the system or decides not to make any purchase at that time. In the former scenario, the retailer gains a product-associated revenue; in the latter scenario, the customer progresses to the next stage or eventually leaves the system once all T stages have been traversed. We focus our attention on the most general formulation of this problem, in which purchasing decisions are governed by a stage-dependent MNL choice model, reflecting the notion that customers' preferences may change from stage to stage because of updated perceptions, patience waning over time, etc. Concurrently, we consider a more structured formulation in which purchasing decisions are stage-invariant, utilizing a single MNL model across all stages. Our main contribution comes in the form of a strongly polynomial-time approximation scheme for both formulations of the sequential assortment problem in their utmost generality. We provide evidence for the practical relevance of these theoretical findings through extensive numerical experiments. Finally, we fit our sequential model to historical search data from Expedia's hotel booking platform. We observe substantial gains in fitting accuracy when our model is benchmarked against other well-known choice models designed for the setting at hand. [ABSTRACT FROM AUTHOR]

The optimal management of shared vehicle systems, such as bike-, scooter-, car-, or ride-sharing, is more challenging compared with traditional resource allocation settings because of the presence of spatial externalities—changes in the demand/supply at any location affect future supply throughout the system within short timescales. These externalities are well captured by steady-state Markovian models, which are therefore widely used to analyze such systems. However, using Markovian models to design pricing and other control policies is computationally difficult because the resulting optimization problems are high dimensional and nonconvex. In our work, we design a framework that provides near-optimal policies, for a range of possible controls, that are based on applying the possible controls to achieve spatial balance on average. The optimality gap of these policies improves as the ratio between supply and the number of locations increases and asymptotically goes to zero. Optimizing shared vehicle systems (bike-/scooter-/car-/ride-sharing) are more challenging compared with traditional resource allocation settings because of the presence of complex network externalities—changes in the demand/supply at any location affect future supply throughout the system within short timescales. These externalities are well captured by steady-state Markovian models, which are therefore widely used to analyze such systems. However, using such models to design pricing and other control policies is computationally difficult because the resulting optimization problems are high dimensional and nonconvex. To this end, we develop a rigorous approximation framework for shared vehicle systems, providing a unified approach for a wide range of controls (pricing, matching, rebalancing), objective functions (throughput, revenue, welfare), and system constraints (travel times, welfare benchmarks, posted-price constraints). Our approach is based on the analysis of natural convex relaxations and obtains as special cases existing approximate optimal policies for limited settings, asymptotic optimality results, and heuristic policies. The resulting guarantees are nonasymptotic and parametric and provide operational insights into the design of real-world systems. In particular, for any shared vehicle system with n stations and m vehicles, our framework obtains an approximation ratio of 1 + (n − 1) / m , which is particularly meaningful when m/n, the average number of vehicles per station, is large, as is often the case in practice. [ABSTRACT FROM AUTHOR]

How to Assess the Benefits of Coordination in Managing Hospital Resources In providing patient care, hospitals rely on multiple types of resources, such as operating rooms, recovery beds, labs, and diagnostic equipment, that are often controlled and managed as separate entities and by different decision makers. In "Surgical Case-Mix and Discharge Decisions: Does Within-Hospital Coordination Matter?" Hessam Bavafa, Lerzan Örmeci, Sergei Savin, and Vanitha Virudachalam focus on the interaction between "front-end" resources, such as operating rooms, and "backroom" resources, such as recovery beds, and compare hospital profitability under the fully coordinated, optimal approach to hospital resource management and under alternative decentralized approaches often encountered in practice. The paper identifies settings in which the benefits of coordination are likely to be high as well as settings in which those benefits are at best moderate. In a given hospital, only hospital managers are in a position to estimate with any degree of certainty potential costs of coordinated management of hospital resources, and the paper's analysis of the benefits of coordination empowers hospital managers to make informed decisions on the desirability of replacing the often decentralized "status quo" by centralized resource management. We study the problem faced by a profit-maximizing, resource-constrained hospital that controls patient inflows by designing a case-mix of its elective procedures and patient outflows via patient discharges. At the center of our analysis is the model that evaluates hospital profit for any combination of elective portfolio and patient discharge policies. Our model analyzes the impact of patient flow management decisions on the utilization of two main classes of hospital resources: "front end" (e.g., operating rooms) and "backroom" (e.g., recovery beds). We introduce a new approach for modeling the patient recovery process and use it to characterize the relationship between patient length of stay and probability of readmission. Using this modeling approach, we develop a two-moment approximation for the utilization of front-end and backroom resources. We focus on assessing the benefits associated with the hospital employing a coordinated decision-making process in which both portfolio and discharge decisions are made in tandem. Specifically, we compare the hospital's profits in the coordinated setting to those under two decentralized approaches: a front-end approach, under which both decisions are made based exclusively on the front-end costs, and a "siloed" approach, in which discharge decisions are made based on backroom costs and the case-mix is determined as the optimal match for the discharge policy. We show that hospitals operating under the front-end policy can significantly benefit from coordination when backroom costs are sufficiently high even if they do not exceed surgical costs. On the other hand, for hospitals operating under the siloed policy, coordination brings significant benefits only when surgical costs are high and significantly dominate the cost structure. [ABSTRACT FROM AUTHOR]

We present a formal study of first-look and preferred deals that are a recently introduced generation of contracts for selling online advertisements, which generalize traditional reservation contracts and are suitable for advertisers with advanced targeting capabilities. Under these deals, one or more advertisers gain priority access to an inventory of impressions before others and can choose to purchase in real time. In particular, we propose constant-factor approximation algorithms for maximizing the revenue that can be obtained from these deals when offered to all or a subset of the advertisers, whose valuation distributions can be independent or correlated through a common value component. We evaluate our algorithms using data from Google's ad exchange platform and show they perform better than the approximation guarantees and obtain significantly higher revenue than auctions; in certain cases, the observed revenue is 85%–96% of the optimal revenue achievable. We also prove the NP-hardness of designing deals when advertisers' valuations are arbitrarily correlated and the optimality of menus of deals among a certain class of selling mechanisms in an incomplete distributional information setting. [ABSTRACT FROM AUTHOR]

We develop a framework for designing simple and efficient policies for a family of online allocation and pricing problems that includes online packing, budget-constrained probing, dynamic pricing, and online contextual bandits with knapsacks. In each case, we evaluate the performance of our policies in terms of their regret (i.e., additive gap) relative to an offline controller that is endowed with more information than the online controller. Our framework is based on Bellman inequalities, which decompose the loss of an algorithm into two distinct sources of error: (1) arising from computational tractability issues, and (2) arising from estimation/prediction of random trajectories. Balancing these errors guides the choice of benchmarks, and leads to policies that are both tractable and have strong performance guarantees. In particular, in all our examples, we demonstrate constant-regret policies that only require resolving a linear program in each period, followed by a simple greedy action-selection rule; thus, our policies are practical as well as provably near optimal. [ABSTRACT FROM AUTHOR]

Many procurement agencies around the world construct assortments of differentiated products from which consumers can buy from. A leading example is framework agreements, a type of procurement mechanism commonly used by governments. This type of practice is studied head on. The authors introduce a mechanism design formulation of the procurement agency's problem and solves it under progressively more realistic implementation constraints. The results show how restricting entry of close-substitute products into the assortment can increase price competition, reducing spending significantly, without much damage to the variety offered to consumers. Furthermore, the results have practical implications that can be used by procurement agencies to increase consumer surplus and have already been used to redesign FAs in the Chilean government. We consider the problem faced by a procurement agency that runs a mechanism for constructing an assortment of differentiated products with posted prices, from which heterogeneous consumers buy their most preferred alternative. Procurement mechanisms used by large organizations, including framework agreements (FAs), which are widely used in the public sector, often take this form. When choosing the assortment, the procurement agency must optimize the tradeoff between offering a richer menu of products for consumers and offering less variety, hoping to engage the suppliers in more aggressive price competition. We formulate the problem faced by the procurement agency as a mechanism design problem, and we progressively incorporate more complex and often more realistic implementation constraints, including that the allocations should be decentralized (that is, consumers choose what to buy) and that payments must be implemented through linear pricing (in particular, no up-front payments are allowed). We characterize the optimal buying mechanisms that highlight the importance of restricting the entry of close-substitute products to the assortment as a way to increase price competition without much damage to variety. Motivated by the implementation of the Chilean FAs, which are being used to acquire around US$3 billion in goods and services per year, we leverage our characterization of the optimal mechanism to study the design of first-price-auction-type mechanisms that are commonly used in public settings. Our results shed light on simple ways to improve their performance. [ABSTRACT FROM AUTHOR]

Dynamic Pricing with Limited Resource and Unknown Demand Parameters When the underlying demand model's parameters are unknown, how should a seller adjust prices of multiple products which are subject to finite resource constraints? In "Technical Note – Joint Learning and Optimization of Multi-Product Pricing with Finite Resource Capacity and Unknown Demand Parameters," Chen, Jasin, and Duenyas revisit the classic learning and earning problem in the context of network revenue management with a continuum of feasible prices and develop two computationally efficient pricing heuristics. For the general parametric demand models, their first heuristic attains an asymptotic regret bound which exactly matches the known theoretical lower bound under any feasible pricing control. If the underlying demand model family also satisfies a separable structure, their second heuristic leverages this structural property to attain a much better regret. The key design features underpinning the two heuristics could be powerful ideas for developing effective pricing policies in other applications. We consider joint learning and pricing in network revenue management (NRM) with multiple products, multiple resources with finite capacity, parametric demand model, and a continuum set of feasible price vectors. We study the setting with a general parametric demand model and the setting with a well-separated demand model. For the general parametric demand model, we propose a heuristic that is rate-optimal (i.e., its regret bound exactly matches the known theoretical lower bound under any feasible pricing control for our setting). This heuristic is the first rate-optimal heuristic for an NRM with a general parametric demand model and a continuum of feasible price vectors. For the well-separated demand model, we propose a heuristic that is close to rate-optimal (up to a multiplicative logarithmic term). Our second heuristic is the first in the literature that deals with the setting of an NRM with a well-separated parametric demand model and a continuum set of feasible price vectors. [ABSTRACT FROM AUTHOR]

It has been realized for a long time that network effects play an important role in how market participants compete with each other. Arguably, companies like Facebook and Google are able to gain immense market power by leveraging the network effects of their consumers, despite potential competitors. This paper investigates how the dynamics play out in duopoly competition. We find that when the network effects per unit of consumption are weak, the competitors can co-exist and gain even market shares. As network effects become stronger, it is unstable, and even impossible, for the firms to coexist, and one firm emerges victorious, taking the majority of the market. The study provides a theoretical analysis for commonly observed market phenomena. It may also have implications for antitrust legislation: Special policies need to be created to maintain a competitive market structure for products and services with strong network effects. We consider two firms selling products to a market of network-connected customers. Each firm is selling one product, and the two products are substitutable. The customers make purchases based on the multinomial logit model, and the firms compete for their purchasing probabilities. We characterize possible Nash equilibria for homogeneous network interactions and identical firms: When the network effects are weak, there is a symmetric equilibrium that the two firms evenly split the market; when the network effects are strong, there exist two asymmetric equilibria additionally, in which one firm dominates the market; interestingly, when the product quality is low and the network effects are neither too weak nor too strong, the resulting market equilibrium is never symmetric, although the firms are ex ante symmetric. We extend these results along multiple directions. First, when the products have heterogeneous qualities, the firm selling inferior product can still retain market dominance in equilibrium due to the strong network effects. Second, when the network effects are heterogeneous, customers with higher social influences or larger price sensitivities are more likely to purchase either product in the symmetric equilibrium. Third, when the network consists of two communities, market segmentation may arise. Fourth, we extend to the dynamic game when the network effects build up over time to explain the first-mover advantage. [ABSTRACT FROM AUTHOR]

The discrete moment problem aims to find a worst-case discrete distribution that satisfies a given set of moments. This paper studies the discrete moment problems with additional shape constraints that guarantee the worst-case distribution is either log-concave (LC) or has an increasing failure rate (IFR) or increasing generalized failure rate (IGFR). These classes are useful in practice, with applications in revenue management, reliability, and inventory control. The authors characterize the structure of optimal extreme point distributions and show, for example, that an optimal extreme point solution to a moment problem with m moments and LC shape constraints is piecewise geometric with at most m pieces. Using this optimality structure, they design an exact algorithm for computing optimal solutions in a low-dimensional space of parameters. The authors leverage this structure to study a robust newsvendor problem with shape constraints and compute optimal solutions. The discrete moment problem is a foundational problem in distribution-free robust optimization, where the goal is to find a worst-case distribution that satisfies a given set of moments. This paper studies the discrete moment problems with additional shape constraints that guarantee the worst-case distribution is either log-concave (LC), has an increasing failure rate (IFR), or increasing generalized failure rate (IGFR). These classes of shape constraints have not previously been studied in the literature, in part due to their inherent nonconvexities. Nonetheless, these classes are useful in practice, with applications in revenue management, reliability, and inventory control. We characterize the structure of optimal extreme point distributions under these constraints. We show, for example, that an optimal extreme point solution to a moment problem with m moments and LC shape constraints is piecewise geometric with at most m pieces. This optimality structure allows us to design an exact algorithm for computing optimal solutions in a low-dimensional space of parameters. We also leverage this structure to study a robust newsvendor problem with shape constraints and compute optimal solutions. [ABSTRACT FROM AUTHOR]

Recent literature on approximately optimal revenue maximization has shown that in settings where agent valuations for items are complement free, the better of selling the items separately and bundling them together guarantees a constant fraction of the optimal revenue. However, most real-world settings involve some degree of complementarity among items. The role that complementarity plays in the trade-off of simplicity versus optimality has been an obvious missing piece of the puzzle. In "A Simple and Approximately Optimal Mechanism for a Buyer with Complements," the authors show that the same simple selling mechanism—the better of selling separately and as a grand bundle—guarantees a $\Theta(d)$ fraction of the optimal revenue, where $d$ is a measure of the degree of complementarity. One key modeling contribution is a tractable notion of "degree of complementarity" that admits meaningful results and insights—they demonstrate that previous definitions fall short in this regard. We consider a revenue-maximizing seller with m heterogeneous items and a single buyer whose valuation for the items may exhibit both substitutes and complements. We show that the better of selling the items separately and bundling them together— guarantees a Θ (d) -fraction of the optimal revenue, where d is a measure of the degree of complementarity; it extends prior work showing that the same simple mechanism achieves a constant-factor approximation when buyer valuations are subadditive (the most general class of complement-free valuations). Our proof is enabled by a recent duality framework, which we use to obtain a bound on the optimal revenue in the generalized setting. Our technical contributions are domain specific to handle the intricacies of settings with complements. One key modeling contribution is a tractable notion of "degree of complementarity" that admits meaningful results and insights—we demonstrate that previous definitions fall short in this regard. [ABSTRACT FROM AUTHOR]

Dynamic Pricing with Limited Demand Information In "On Policies for Single-Leg Revenue Management with Limited Demand Information," Ma, Simchi-Levi, and Teo revisit the foundational revenue management problem of dynamically pricing the limited seats on a single flight leg. They propose a new "Valuation Tracking" policy, which dynamically raises the price within a feasible range as seats get sold but, importantly, does not rely on any information about the remaining demand expected to occur before the flight takes off. This new policy can be seen as an adaptation of historically used "booking limits" policies, designed for flight fare classes that captured independent segments of demand, to modern times, where airlines are frequently adding sophisticated fare classes that capture overlapping demand segments. The new policy achieves the best-possible theoretical competitive ratio and also performs robustly in a comprehensive numerical comparison with all the different policies that have been proposed for single-leg revenue management under limited demand information. In this paper, we study the single-item revenue management problem, with no information given about the demand trajectory over time. When the item is sold through accepting/rejecting different fare classes, the tight competitive ratio for this problem has been established by Ball and Queyranne through booking limit policies, which raise the acceptance threshold as the remaining inventory dwindles. However, when the item is sold through dynamic pricing instead, there is the additional challenge that offering a low price may entice high-paying customers to substitute down. We show that despite this challenge, the same competitive ratio can still be achieved using a randomized dynamic pricing policy. Our policy incorporates the price-skimming technique originated by Eren and Maglaras, but importantly we show how the randomized price distribution should be stochastically increased as the remaining inventory dwindles. A key technical ingredient in our policy is a new "Valuation Tracking" subroutine, which tracks the possible values for the optimum, and follows the most "inventory-conservative" control, which maintains the desired competitive ratio. Finally, we demonstrate the empirical effectiveness of our policy in simulations, where its average-case performance surpasses all naive modifications of the existing policies. [ABSTRACT FROM AUTHOR]

In practice, when thinking about their purchasing decisions, customers usually strategize along two dimensions: (1) when to buy and (2) what to buy. That is, they might delay a purchase in anticipation of future price reductions, and/or they might purchase cheaper substitutes. Despite this, the literature has thus far dealt exclusively with either one of the two extremes whereby one of the two strategic dimension is missing. For example, a large body of work has studied forward-looking customers strategizing on when to buy but has done so merely within models in which customers have no alternatives to choose from. Conversely, another large body of work on assortment optimization and choice modeling has studied customers who choose what to buy from multiple product offerings but acting myopically. This paper takes a first step toward analyzing dynamic pricing when customers are fully strategic and choose both when and what to buy. Using a novel decomposition approach for the underlying multidimensional mechanism design problem, the paper presents theoretical and numerical performance analyses of static pricing policies. Consider a network revenue management model in which a seller offers multiple products, which consume capacitated resources. The seller uses an anonymous posted-price policy, and arriving customers strategize on (a) when and (b) which product to purchase to maximize their utility, based on heterogeneous product valuations. Such models, whereby customers are both forward looking and choose what to buy, have not yet been amenable to analysis, mainly because their associated dynamic mechanism design counterparts are multidimensional; that is, they involve constraints with multivariate private information (the product valuations). Within the context of the aforementioned model, we present a novel decomposition approach that enables us to deal with the underlying multidimensional mechanism design problem. Using this approach, we derive for all nonanticipating dynamic pricing policies an upper bound to expected revenues. We use our bound to conduct theoretical and numerical performance analyses of static pricing policies. In our theoretical analysis, we derive guarantees for the performance of static pricing, for the classical fluid-type regime where inventory and demand grow large. Our numerical analysis shows static pricing to be able capture at least 75%–90% of maximum possible expected revenue under a wide range of realistic problem parameters. [ABSTRACT FROM AUTHOR]

Resource Allocation and Pricing in the Absence of a Demand Forecast Motivated by collaborations with airline carriers and hotel chains, Ma and Simchi-Levi analyze in "Algorithms for Online Matching, Assortment, and Pricing with Tight Weight-Dependent Competitive Ratios" a general online resource-allocation problem using competitive analysis, where the sequence of demands is completely unknown. They allow for resources to be sold at multiple feasible prices, and establish tight competitive ratios that are dependent on the given feasible prices, generalizing the well-known online matching and Adwords settings. The algorithms derived are simple and intuitive, based on a class of universal value functions that integrate the resource selection and pricing decisions. Finally, the authors run simulations on publicly available data, and consider how a hotel could have managed its room resources through controlling the room packages offered on its website. The authors find that revenues are maximized when their algorithms (which do not assume anything about the sequence of visitors) are applied as a hybrid with existing algorithms that attempt to forecast and learn the sequence of visitors. Motivated by the dynamic assortment offerings and item pricings occurring in e-commerce, we study a general problem of allocating finite inventories to heterogeneous customers arriving sequentially. We analyze this problem under the framework of competitive analysis, where the sequence of customers is unknown and does not necessarily follow any pattern. Previous work in this area, studying online matching, advertising, and assortment problems, has focused on the case where each item can only be sold at a single price, resulting in algorithms which achieve the best-possible competitive ratio of 1 − 1/ e. In this paper, we extend all of these results to allow for items having multiple feasible prices. Our algorithms achieve the best-possible weight-dependent competitive ratios, which depend on the sets of feasible prices given in advance. Our algorithms are also simple and intuitive; they are based on constructing a class of universal value functions that integrate the selection of items and prices offered. Finally, we test our algorithms on the publicly available hotel data set of Bodea et al. [Bodea T, Ferguson M, Garrow L (2009) Data set—Choice-based revenue management: Data from a major hotel chain. Manufacturing Service Oper. Management 11(2):356–361.], where there are multiple items (hotel rooms), each with multiple prices (fares at which the room could be sold). We find that applying our algorithms, as a hybrid with algorithms that attempt to forecast and learn the future transactions, results in the best performance. [ABSTRACT FROM AUTHOR]

Learning and Earning in High Dimensions: Assortment Personalization Using Low-Rank Preferences The proliferation of products and users in modern e-commerce presents a substantial challenge. How can a retailer learn each consumer's preference for so many products—and, more importantly, maximize revenue—from sparse transactional data? In "Dynamic Assortment Personalization in High Dimensions," Kallus and Udell show how to use the low rank structure of the matrix of preferences to dynamically choose individualized assortments to offer each consumer. This approach can increase revenue by orders of magnitude by learning across users to avoid excessive exploration. Their new method relies on convex optimization to recover hidden low-dimensional structure from sparse, high-dimensional data. We study the problem of dynamic assortment personalization with large, heterogeneous populations and wide arrays of products, and demonstrate the importance of structural priors for effective, efficient large-scale personalization. Assortment personalization is the problem of choosing, for each individual (type), a best assortment of products, ads, or other offerings (items) so as to maximize revenue. This problem is central to revenue management in e-commerce and online advertising where both items and types can number in the millions. We formulate the dynamic assortment personalization problem as a discrete-contextual bandit with m contexts (types) and exponentially many arms (assortments of the n items). We assume that each type's preferences follow a simple parametric model with n parameters. In all, there are mn parameters, and existing literature suggests that order optimal regret scales as mn. However, the data required to estimate so many parameters is orders of magnitude larger than the data available in most revenue management applications; and the optimal regret under these models is unacceptably high. In this paper, we impose a natural structure on the problem – a small latent dimension, or low rank. In the static setting, we show that this model can be efficiently learned from surprisingly few interactions, using a time- and memory-efficient optimization algorithm that converges globally whenever the model is learnable. In the dynamic setting, we show that structure-aware dynamic assortment personalization can have regret that is an order of magnitude smaller than structure-ignorant approaches. We validate our theoretical results empirically. [ABSTRACT FROM AUTHOR]

Should Consumers Be Strategic? Strategic consumer behavior under multiperiod pricing—when consumers anticipate future price changes and, potentially, delay a purchase to get a product at a lower price—is a phenomenon that has received significant recent research attention in the operations and revenue management literatures. In "Becoming Strategic: Endogenous Consumer Time Preferences and Multiperiod Pricing," Aflaki, Feldman, and Swinney examine this problem from a different angle: They ask whether being strategic actually benefits consumers, whether consumers are willing to exert costly effort to become strategic, and how the answers to these questions impact the optimal decisions of firms pricing over multiple periods. They find that much of the conventional wisdom regarding strategic consumer behavior is upended when the decision of consumers to become strategic in the first place is considered, including qualitative features of the firm's optimal pricing policy and, possibly, the firm's preference between dynamic and committed pricing strategies. Pricing over multiple periods under forward-looking, strategic consumer purchasing behavior has received significant recent research attention; however, whether consumers actually benefit from this behavior and would voluntarily choose to be strategic has not been previously considered. We explore this question by developing a model of endogenous time preferences, consistent with microeconomic theories of boundedly rational intertemporal decision making, in which consumers choose to become strategic by exerting costly effort. We show three key implications of this choice. First, considering the consumer choice to be strategic can have a significant impact on firm and consumer decisions—in particular, qualitatively impacting the firm's optimal pricing policy. Second, it is possible to increase firm profit, consumer surplus, and social welfare simultaneously by increasing the cost of strategic behavior, suggesting that firms can, essentially, force consumers to be myopic and make all parties better off; this helps explain how firms that do the most to make strategic behavior difficult are able to attract more demand and be successful in the marketplace. And third, efforts to mitigate strategic consumer waiting by committing to future prices instead of pricing dynamically may decrease the cost of strategic behavior and backfire, encouraging more consumers to be strategic; hence, in contrast to most previous research, price commitment may yield lower profit than dynamic pricing if consumers can choose to be strategic. [ABSTRACT FROM AUTHOR]

Nonlinear pricing is frequently used by fast-fashion retailers (e.g., Zara). Discounts of the form "Buy 2, get 20% off" or "Buy 3 and save 30%" are becoming common. As revealed in a recent study by Gallego et al. (2019), nonlinear dynamic pricing can significantly improve a company's revenue, by as much as 30%–90%, especially when inventories are high and the relative value of the marginal unit is neither too low nor too high, a situation that is common in fast-fashion retailing. They find that a single quantity discount threshold can capture most of the benefits of nonlinear pricing. The simplicity of this policy validates observed practice and concentrates managerial efforts to dynamically selecting the threshold and the depth of the discount. We consider a finite-horizon, finite-capacity dynamic pricing model where consumers may purchase multiple units of the same product. We present three models that differ in their complexity and revenue potential. The dynamic nonlinear pricing (DNP) model allows the seller to dynamically selecting a price for each bundle size. The dynamic linear pricing model restricts the seller to dynamically select a unit price for all bundle sizes. There can be a significant revenue gap between the two models, but the additional revenues require a nonlinear policy that may be more challenging to implement. This motivates the study of dynamic block pricing as an intermediate pricing model where prices are linear within each block. A heuristic for this last model provides almost as much revenue as DNP while avoiding its complexity. [ABSTRACT FROM AUTHOR]

Many revenue management problems require making capacity control and pricing decisions for multiple products. The decisions for the different products interact because either the products use a common pool of resources or the customers choose and substitute among the products. When pricing airline tickets, for example, different itinerary products use the capacities on common flight legs and the customers choose and substitute among different itinerary products that serve the same origin-destination pair. Finding the optimal capacity control and pricing decisions in such problems can be challenging because one needs to simultaneously consider the capacities available to serve a large pool of products. In "An Approximation Algorithm for Network Revenue Management under Nonstationary Arrivals," Ma, Rusmevichientong, Sumida, and Topaloglu develop efficient methods to make decisions with performance guarantees in high-dimensional capacity control and pricing problems. We provide an approximation algorithm for network revenue management problems. In our approximation algorithm, we construct an approximate policy using value function approximations that are expressed as linear combinations of basis functions. We use a backward recursion to compute the coefficients of the basis functions in the linear combinations. If each product uses at most L resources, then the total expected revenue obtained by our approximate policy is at least 1 / (1 + L) of the optimal total expected revenue. In many network revenue management settings, although the number of resources and products can become large, the number of resources used by a product remains bounded. In this case, our approximate policy provides a constant-factor performance guarantee. Our approximate policy can handle nonstationarities in the customer arrival process. To our knowledge, our approximate policy is the first approximation algorithm for network revenue management problems under nonstationary arrivals. Our approach can incorporate the customer choice behavior among the products, and allows the products to use multiple units of a resource, while still maintaining the performance guarantee. In our computational experiments, we demonstrate that our approximate policy performs quite well, providing total expected revenues that are substantially better than its theoretical performance guarantee. [ABSTRACT FROM AUTHOR]

In "Real-Time Dynamic Pricing for Revenue Management with Reusable Resources, Advance Reservation, and Deterministic Service Time Requirements," Lei and Jasin consider a fundamental dynamic pricing problem when resources are reusable. In this problem, demand arrives according to a price-sensitive nonstationary rate, requesting a service that uses a combination of different types of resources for a deterministic duration of time. The resources are reusable in the sense that they can be immediately used to serve a new customer on the completion of the previous service. Moreover, different customers may have different service time requirement and may book the service in advance. The objective is to construct a dynamic pricing control that maximizes expected total revenues. They develop real-time heuristic controls based on the solution of the deterministic relaxation of the original stochastic problem and show that the proposed controls are near optimal in the regime of large demand and large resource capacity. We consider a dynamic pricing problem in a system with reusable resources. Customers arrive randomly over time according to a specified nonstationary rate, and each customer requests a service that uses a combination of different types of resources for a deterministic duration of time. The resources are reusable in the sense that they can be immediately used to serve a new customer on the completion of the previous service. Our objective is to construct a dynamic pricing control that maximizes expected total revenues. This is a fundamental problem faced by firms in many industries. We develop real-time heuristic controls based on the solution of the deterministic relaxation of the original stochastic problem and show that they are near optimal in the regime of large demand and large resource capacity. We further show that our results can be extended to a more general setting with heterogeneous service time and advance reservation. [ABSTRACT FROM AUTHOR]

We develop a solution approach to the centralized pricing problem of a firm managing multiple substitutable products. Demand of these products undergoes a diffusion process, and customers choose among the products, with the choice probability of each product given by the logit model. We examine the firm's optimal pricing problem when product demand can be described by such "diffusion-choice" models. In particular, we focus on two models with proven merits and study a generalized version of the two models. To our knowledge, our work is the first to study the multiproduct pricing problem under the integrated diffusion-choice models, which are of both theoretical appeal and practical advantage. We establish uniqueness of the optimal solution and propose an efficient solution approach in addition to characterizing the optimal prices and their time trend. We show that the price trend can be attributed to diffusion dynamics as well as intertemporal changes in product costs and customer price sensitivity, all of which are integrated into a unified framework in this paper. Our model applies to both simultaneous and sequential product introductions and adapts to stochastic demand. [ABSTRACT FROM AUTHOR]

Multiarmed bandit (MAB) is a classic model for capturing the exploration–exploitation trade-off inherent in many sequential decision-making problems. The classic MAB framework, however, only allows "local" constraints on decisions and "sum of rewards" as objective. In many real-world applications, there are multiple complex constraints on resources that are consumed during the entire decision process, and performance may be evaluated through nonlinear utility functions on aggregate rewards. This article presents a new MAB framework that allows such "global" convex constraints and concave objective functions along with new algorithmic techniques with provably near-optimal performance bounds. The authors discuss applications in several domains, such as network revenue management, crowdsourcing, and pay-per-click advertising, which benefit from the new more general framework by admitting richer models and more efficient risk-averse solutions. We consider a very general model for managing the exploration–exploitation trade-off, which allows global convex constraints and concave objective on the aggregate decisions over time in addition to the customary limitation on the time horizon. This model provides a natural framework to study many sequential decision-making problems with long-term convex constraints and concave utility and subsumes the classic multiarmed bandit (MAB) model and the bandits with knapsacks problem as special cases. We demonstrate that a natural extension of the upper confidence bound family of algorithms for MAB provides a polynomial time algorithm with near-optimal regret guarantees for this substantially more general model. We also provide computationally more efficient algorithms by establishing interesting connections between this problem and other well-studied problems/algorithms, such as the Blackwell approachability problem, online convex optimization, and the Frank–Wolfe technique for convex optimization. We give several concrete examples of applications, particularly in risk-sensitive revenue management under unknown demand distributions, in which this more general bandit model of sequential decision making allows for richer formulations and more efficient solutions of the problem. [ABSTRACT FROM AUTHOR]