Most results in revenue-maximizing mechanism design hinge on “getting the price right”—selling goods to bidders at prices low enough to encourage a sale but high enough to garner nontrivial revenue. This approach is difficult to implement when the seller has little or no a priori information about bidder valuations or when the setting is sufficiently complex, such as matching markets with heterogeneous goods. In this paper, we apply a robust approach to designing auctions for revenue. Instead of relying on prior knowledge regarding bidder valuations, we “let the market do the work” and let prices emerge from competition for scarce goods. We analyze the revenue guarantees of one of the simplest imaginable implementations of this idea: first, we enhance competition in the market by increasing demand (or alternatively, by limiting supply), and second, we run a standard second price (Vickrey) auction. In their renowned work from 1996 , Bulow and Klemperer [Bulow J, Klemperer P (1996) Auctions vs. negotiations. Amer. Econom. Rev. 86(1):180–194.] apply this method to markets with single goods. As our main result, we give the first application beyond single-parameter settings, proving that, simultaneously for many valuation distributions, this method achieves expected revenue at least as good as the optimal revenue in the original market. Our robust and simple approach provides a handle on the elusive optimal revenue in multiitem matching markets and shows when the use of welfare-maximizing Vickrey auctions is justified, even if revenue is a priority. By establishing quantitative tradeoffs, our work provides guidelines for a seller in choosing among two different revenue-extracting strategies: sophisticated pricing based on market research or advertising to draw additional bidders.
more »
« less
This content will become publicly available on November 1, 2024
Static Pricing for Multi-unit Prophet Inequalities
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.
more » « less- Award ID(s):
- 2225259
- NSF-PAR ID:
- 10496734
- Publisher / Repository:
- Informs
- Date Published:
- Journal Name:
- Operations Research
- ISSN:
- 0030-364X
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
null (Ed.)We study the power of selling opaque products, that is, products where a feature (such as color) is hidden from the customer until after purchase. Opaque products, which are sold with a price discount, have emerged as a powerful vehicle to increase revenue for many online retailers and service providers that offer horizontally differentiated items. In the opaque selling models we consider, all of the items are sold at a single common price alongside opaque products that may correspond to various subsets of the items. We consider two types of customers, risk-neutral ones, who assume they will receive a truly random item of the opaque product, and pessimistic ones, who assume they will receive their least favorite item of the opaque product. We benchmark opaque selling against two common selling strategies: discriminatory pricing, where one explicitly charges different prices for each item, and single pricing, where a single price is charged for all the items. We give a sharp characterization of when opaque selling outperforms discriminatory pricing; namely, this result holds for situations where all customers are pessimistic or the item valuations are supported on two points. In the latter case, we also show that opaque selling with just one opaque product guarantees at least 71.9% of the revenue from discriminatory pricing. We then provide upper bounds on the potential revenue increase from opaque selling strategies over single pricing and describe cases where the increase can be significantly more than that of discriminatory pricing. Finally, we provide pricing algorithms and conduct an extensive numerical study to assess the power of opaque selling for a variety valuation distributions and model extensions. This paper was accepted by Gabriel Weintraub, revenue management and market analytics.more » « less
-
This paper studies a dynamic pricing problem under model misspecification. To characterize model misspecification, we adopt the ε-contamination model—the most fundamental model in robust statistics and machine learning. In particular, for a selling horizon of length T, the online ε-contamination model assumes that demands are realized according to a typical unknown demand function only for [Formula: see text] periods. For the rest of [Formula: see text] periods, an outlier purchase can happen with arbitrary demand functions. The challenges brought by the presence of outlier customers are mainly due to the fact that arrivals of outliers and their exhibited demand behaviors are completely arbitrary, therefore calling for robust estimation and exploration strategies that can handle any outlier arrival and demand patterns. We first consider unconstrained dynamic pricing without any inventory constraint. In this case, we adopt the Follow-the-Regularized-Leader algorithm to hedge against outlier purchase behavior. Then, we introduce inventory constraints. When the inventory is insufficient, we study a robust bisection-search algorithm to identify the clearance price—that is, the price at which the initial inventory is expected to clear at the end of T periods. Finally, we study the general dynamic pricing case, where a retailer has no clue whether the inventory is sufficient or not. In this case, we design a meta-algorithm that combines the previous two policies. All algorithms are fully adaptive, without requiring prior knowledge of the outlier proportion parameter ε. Simulation study shows that our policy outperforms existing policies in the literature.more » « less
-
more » « less
We study the problem of maximizing payoff generated over a period of time in a general class of closed queueing networks with a finite, fixed number of supply units that circulate in the system. Demand arrives stochastically, and serving a demand unit (customer) causes a supply unit to relocate from the “origin” to the “destination” of the customer. The key challenge is to manage the distribution of supply in the network. We consider general controls including customer entry control, pricing, and assignment. Motivating applications include shared transportation platforms and scrip systems. Inspired by the mirror descent algorithm for optimization and the backpressure policy for network control, we introduce a rich family of mirror backpressure (MBP) control policies. The MBP policies are simple and practical and crucially do not need any statistical knowledge of the demand (customer) arrival rates (these rates are permitted to vary in time). Under mild conditions, we propose MBP policies that are provably near optimal. Specifically, our policies lose at most [Formula: see text] payoff per customer relative to the optimal policy that knows the demand arrival rates, where K is the number of supply units, T is the total number of customers over the time horizon, and η is the demand process’ average rate of change per customer arrival. An adaptation of MBP is found to perform well in numerical experiments based on data from NYC Cab.
This paper was accepted by Gabriel Weintraub, revenue management and market analytics.
Funding: Y. Kanoria was supported by the National Science Foundation’s Division of Civil, Mechanical, and Manufacturing Innovation [Grant CMMI-1653477].
Supplemental Material: The data files and online appendices are available at https://doi.org/10.1287/mnsc.2023.4934 .
-
We study the problem of optimal information sharing in the context of a service system. In particular, we consider an unobservable single server queue offering a service at a fixed price to a Poisson arrival of delay-sensitive customers. The service provider can observe the queue, and may share information about the state of the queue with each arriving customer. The customers are Bayesian and strategic, and incorporate any information provided by the service provider into their prior beliefs about the queue length before making the decision whether to join the queue or leave without obtaining service. We pose the following question: which signaling mechanism and what price should the service provider select to maximize her revenue? We formulate this problem as an instance of Bayesian persuasion in dynamic settings. The underlying dynamics make the problem more difficult because, in contrast to static settings, the signaling mechanism adopted by the service provider affects the customers' prior beliefs about the queue (given by the steady state distribution of the queue length in equilibrium). The core contribution of this work is in characterizing the structure of the optimal signaling mechanism. We summarize our main results as follows. (1) Structural characterization: Using a revelation-principle style argument, we find that it suffices to consider signaling mechanisms where the service provider sends a binary signal of "join" or "leave", and under which the equilibrium strategy of a customer is to follow the service provider's recommended action. (2) Optimality of threshold policies: For a given fixed price for service, we use the structural characterization to show that the optimal signaling mechanism can be obtained as a solution to a linear program with a countable number of variables and constraints. Under some mild technical conditions on the waiting costs, we establish that there exists an optimal signaling mechanism with a threshold structure, where service provider sends the "join" signal if the queue length is below a threshold, and "leave" otherwise. (In addition, at the threshold, the service provider randomizes.) For the special case of linear waiting costs, we derive an analytical expression for the optimal threshold i terms of the two branches of the Lambert-W function. (3) Revenue comparison: Finally, we show that with the optimal choice of the fixed price and using the corresponding optimal signaling mechanism, the service provider can achieve the same revenue as with the optimal state-dependent pricing mechanism in a fully-observable queue. This implies that in settings where state-dependent pricing is not feasible, the service provider can effectively use optimal signaling (with the optimal fixed price) to achieve the same revenue.more » « less
