The Power of Two Choices in Dynamic Pricing: As Good As Full Feedback, Instance-Wise
Organizations: Operations Research Center, Massachusetts Institute of Technology. · School of Data Science, The Chinese University of Hong Kong, Shenzhen. · Microsoft Research NYC.
Abstract
We study the dynamic pricing problem, where a firm sells a product to myopic customers and their values are independent samples from an unknown value distribution . With posted prices, the firm only sees whether each customer buys, and the minimax regret is [KL03]. A menu instead offers several options, each selling the product with some probability at some expected payment. Infinitely many menu options allow the seller to fully reveal customer values, reducing the regret to . How many options are needed? Perhaps surprisingly, a second menu option suffices, achieving the same regret as infinite menus (up to factors). This holds broadly: without knowing any property of , our algorithm with two menu options attains regret in general, regret for monotone-hazard-rate distributions, and instance-dependent regret when is a suitable notion of "dimension". All are optimal even with infinite menus. Moreover, we argue, via a novel lower-bound construction, that our algorithm is near-optimal for each problem instance. Along the way, we study the query complexity of revenue maximization, where an algorithm issues a query to each customer to learn the property of interest (either the best price or the CDF) up to some precision. We show that interval queries suffice to achieve the same query complexity as value queries (up to factors) for both properties and across several classes of value distributions. We provide a new interval-query algorithm for each property. The best-price-estimation algorithm is the key ingredient in our main dynamic pricing algorithm, and the CDF-estimation algorithm underpins a simpler algorithm attaining regret with three menu options.
Figures & tables
| Value Distribution | With Infinite Choices (Size- Menus) | With a Second Choice (Size- Menus) | Only Posted Price (Size- Menus) |
| General | ( Theorem 4.1 a) | ( Theorem 3.4 a) | [ 41 ] |
| MHR | ( Theorem 4.1 b) | ( Theorem 3.4 b) | [ 58 , 50 ] |
| Constant curvature | ( Theorem 4.1 c) | ( Theorem 3.4 c) | [ 42 ] ( Lemma B.29 ) |
| Interval Dimension | ( Theorem 4.1 d) | ( Theorem 3.5 ) | [ 42 ] ( Theorem 4.6 ) |
| Property | Value Distribution | Sample Complexity | Interval-Query Complexity | Threshold-Query Complexity |
| CDF | General | [ 25 ] | [ 50 ] | |
| [ 37 ] | ||||
| Regular | ( Lemma B.16 ) | [ 49 ] [ 50 ] 5 5 5 Their hard instance [ 50 , Theorem 3.7] is also MHR, even though they do not state so explicitly. | ||
| MHR | ||||
| Constant Curvature | ( Lemma B.17 ) | ( Theorem 3.2 ) | ( Lemma B.27 ) | |
| Monopoly Price | General | [ 25 ] | [ 50 ] |
| Problem | Full Feedback / Infinite Menus | Bandit Feedback / Posted Prices |
|---|---|---|
| Dynamic Pricing | using size-2 ( Theorem 3.5 ) | [ 42 ] |
| ( Theorems 4.4 and 4.2 ) | ( Theorem 4.6 ) | |
| Lipschitz Bandits | [ 42 ] | [ 42 ] |
| even if ( Lemma D.18 ) | [ 59 ] |
Appendix figures & tables4 assets
Supplementary material from the paper’s appendix.
Appendix
Dynamic Pricing
Dynamic pricing studies how sellers and platforms adjust prices as demand, competition, inventory, and resource constraints change.
See all 59 papers