Source-linked AI summary
Dynamic Pricing with Limited Supply
Moshe Babaioff, Shaddin Dughmi, Robert Kleinberg, Aleksandrs Slivkins
TL;DR
The paper asks how to price sequential buyers with limited supply without knowing their value distribution, relative to an offline benchmark that does know it. It uses a supply-aware bandit approach for detail-free posted pricing and obtains near-benchmark revenue, with stronger rates under additional conditions. The results also identify limits from distribution-dependent constants and the failure of standard per-round bandit intuition.
Problem
The problem is to maximize revenue from k limited-supply items sold to n sequential buyers without knowing the IID demand distribution, while comparing against an offline mechanism that does know it.
Method
The paper designs detail-free online posted-price strategies using a bandit index based on estimated total payoff under inventory and horizon constraints.
Results
O((k log n)2/3) is the offline-benchmark revenue gap for regular distributions and the fixed-price-benchmark gap for all distributions; a stronger rate is available under additional conditions.
Takeaways & Limitations
Limited-supply dynamic pricing can be treated as a bandit problem when exploration and exploitation are evaluated using constrained total payoff rather than per-round revenue.
Takeaways & Limitations
The analysis faces a technical limitation because standard UCB1 charging arguments fail in the limited-supply setting, and some guarantees rely on distribution-dependent constants.
Abstract
from arXiv · showhide
We consider the problem of dynamic pricing with limited supply. A seller has $k$ identical items for sale and is facing $n$ potential buyers ("agents") that are arriving sequentially. Each agent is interested in buying one item. Each agent's value for an item is an IID sample from some fixed distribution with support $[0,1]$. The seller offers a take-it-or-leave-it price to each arriving agent (possibly different for different agents), and aims to maximize his expected revenue. We focus on "prior-independent" mechanisms -- ones that do not use any information about the distribution. They are desirable because knowing the distribution is unrealistic in many practical scenarios. We study how the revenue of such mechanisms compares to the revenue of the optimal offline mechanism that knows the distribution ("offline benchmark"). We present a prior-independent dynamic pricing mechanism whose revenue is at most $O((k \log n)^{2/3})$ less than the offline benchmark, for every distribution that is regular. In fact, this guarantee holds without *any* assumptions if the benchmark is relaxed to fixed-price mechanisms. Further, we prove a matching lower bound. The performance guarantee for the same mechanism can be improved to $O(\sqrt{k} \log n)$, with a distribution-dependent constant, if $k/n$ is sufficiently small. We show that, in the worst case over all demand distributions, this is essentially the best rate that can be obtained with a distribution-specific constant. On a technical level, we exploit the connection to multi-armed bandits (MAB). While dynamic pricing with unlimited supply can easily be seen as an MAB problem, the intuition behind MAB approaches breaks when applied to the setting with limited supply. Our high-level conceptual contribution is that even the limited supply setting can be fruitfully treated as a bandit problem.
1 Introduction
The paper studies detail-free online posted pricing when limited supply makes standard bandit intuition inadequate. It develops mechanisms that approach offline or fixed-price benchmarks, with guarantees depending on distributional assumptions and supply-demand ratios.
- Problem: The model has k items and n sequential agents whose values are drawn from an unknown demand distribution; prices adapt to observed history and remaining supply.The seller observes only purchase decisions and uses take-it-or-leave-it posted prices.
- Motivation: Detail-free posted-price mechanisms aim to perform well for any demand distribution without relying on its details, while remaining incentive-compatible and practical.Posted prices require agents to decide only whether their values exceed the offer.
- Bandit connection: Standard MAB approaches fail with limited supply because maximizing per-round revenue can exhaust inventory too quickly, making higher prices more profitable.The paper instead treats exploration and exploitation while accounting for the supply constraint.
- Main guarantees: O((k log n)2/3) is the regret gap from the offline benchmark for regular demand distributions, using a detail-free pricing strategy.The same rate holds against the fixed-price benchmark for every demand distribution, and the fixed-price result is best possible up to O(log n).
- Distribution-dependent guarantees: O(√k log n) is achievable with a distribution-dependent constant when k/n is sufficiently small, but that constant can be arbitrarily large and the rate is not directly comparable to the distribution-independent bound.A separate MHR guarantee gives an offline-benchmark gap of O(k3/4 poly log(k)).
- Limits: The paper establishes matching lower-bound behavior for distribution-dependent constants and notes that its main bounds become uninformative when k = O(log^2 n).The lower bound does not match the regular-distribution upper bound because it does not assume regularity.
2 Related Work
Prior work studies dynamic pricing and online mechanisms under varying supply, valuation, and information assumptions. This paper distinguishes its limited-supply, IID, posted-price setting from related approaches and connects it to stochastic bandits.
- Dynamic pricing research commonly uses parameterized demand distributions and priors on their parameters.
- Prior work on unknown demand includes unlimited-supply settings, single-item settings, and continuous-time models related to large-supply cases.
- Some prior regret lower bounds use fractional sales benchmarks and therefore do not directly imply bounds for this paper’s benchmarks.
- Related unlimited-supply work studies adversarial valuations and posted-price mechanisms, whereas this paper considers limited supply and IID valuations.
- Earlier limited-supply mechanisms for IID valuations are generally not posted-price mechanisms and often provide multiplicative rather than additive guarantees.
- Dynamic pricing reveals only a binary sale decision, unlike secretary problems, where the arriving agent’s private value is revealed.
3 Preliminaries
The paper formalizes demand, revenue, pricing strategies, and regret for limited-supply dynamic pricing. It relates the fixed-price and offline benchmarks for regular distributions, enabling the main analysis to focus on fixed prices.
- Valuations are IID from a distribution F on [0,1], with sales rate S(p), single-round revenue R(p)=pS(p), and regularity defined through concavity of R.
- A fixed-price strategy offers the same price p until k items are sold, then stops selling.
- A fixed-price strategy with price p sells nS(p) items in expectation before supply depletion is considered.
- Detail-free strategies do not use the demand distribution and are evaluated against both offline and fixed-price benchmarks.
- Regret is the additive expected-revenue loss relative to the best fixed-price mechanism and can theoretically be negative.
- For regular distributions, a fixed-price strategy is close to the offline benchmark, so fixed-price regret transfers to offline-benchmark regret.
- The analysis characterizes fixed-price revenue and identifies an optimal price using the Myerson reserve price and the supply-demand balance.
4 The main technical result: the upper bound in Theorem 1.2
The paper’s main technical result gives CappedUCB a distribution-free O((k log n)2/3) regret guarantee against the fixed-price benchmark. The algorithm uses confidence-bound indices for estimated total payoff, while the analysis handles limited-supply dependence through concentration events and a tuned discretization parameter.
- Main upper bound: O((k log n)2/3) regret is achieved by a detail-free pricing strategy against the fixed-price benchmark, without assumptions on the demand distribution.This upper bound is the main technical result underlying the paper’s regular-distribution guarantee.
- Pricing strategy: CappedUCB assigns each active price an index based on estimated total payoff under inventory and horizon constraints, rather than single-round expected payoff.The index is a UCB for the total payoff of a fixed-price strategy, incorporating both exploitation and exploration.
- Analysis: The analysis must overcome the failure of standard UCB1 charging arguments in the limited-supply setting.It bounds regret through a nontrivial charging scheme for suboptimal prices and uses high-probability events controlling sales and revenue deviations.
- Pricing strategy: The strategy selects the active price with the highest index and sets the price to infinity after selling all k items.Active prices form a geometric grid, and the algorithm uses empirical sales rates plus confidence radii to construct its indices.
- Regret bound: Choosing δ = k^-1/3(log n)2/3 balances the leading terms and yields O((k log n)2/3) regret.The proof analyzes a non-exiting auxiliary process and then relates its first k sales to CappedUCB’s realized revenue.
5 The O(
The section improves the regret guarantee for regular demand distributions when the supply-to-demand ratio is sufficiently small, using a distribution-dependent constant. It also explains that parameter choices trade off improved performance in this setting against guarantees for arbitrary distributions.
- Improved regret bound: O(√k log n) regret is achieved for regular demand distributions when k/n is sufficiently small, with a distribution-dependent constant.The bound uses CappedUCB with parameter δ = k^-1/2 log(n), under a condition k/n ≤ s_F.
- Improved regret bound: For monotone hazard rate distributions, the threshold can be taken as s_F = 1/4.
- Proof idea: The improvement comes from regularity-based lower bounds on the badness of prices, which reduce the exploration-related regret term.
- Trade-off: The improved parameter choice yields a trivial O(k) guarantee for arbitrary demand distributions, so parameters can be varied to balance the two settings.
6 Lower Bounds
The paper proves lower bounds showing that detail-free pricing cannot substantially improve the principal regret rates, including when constants may depend on the demand distribution. The proof reduces limited-supply pricing to the unlimited-supply case.
- Lower bounds: The lower bounds are stated relative to the fixed-price benchmark and match the upper-bound rates in the corresponding theorems.
- Lower bounds: No detail-free pricing strategy can achieve regret o(k^2/3) for arbitrarily large k and n.
- Proof strategy: The proof uses a black-box reduction from unlimited supply to limited supply by randomly routing posted prices to agents in an artificial instance.
7 Selling very few items: proof of Theorem 1.5
For very small supply, the paper introduces a descending-price strategy under the monotone hazard rate assumption. The strategy achieves a multiplicative approximation to the offline benchmark, which yields an additive regret bound after parameter tuning.
- Mechanism 2: Mechanism 2 tests prices p_l = (1 − δ)^l in descending order and stops when estimated sales or revenue indicates that a suitable price has been reached.
- Theorem 7.1: Omitted threshold-dependent bound: Mechanism 2 achieves regret O(·) against the offline benchmark under monotone hazard rate.The supplied theorem statement truncates the displayed bound, but specifies parameters ε = k^-1/4 and δ = (k log k)^-1/4.
- Mechanism 2: The mechanism then offers the detected price while unsold items remain, after exploration based on acceptance rates and per-agent revenue.
- Performance guarantee: The expected revenue is at least a 1 − O(δ) fraction of the offline benchmark.
- Proof strategy: The proof controls exploration accuracy with Chernoff bounds and compares fixed-price limited-supply revenue with unlimited-supply revenue.
8 Conclusions and open questions
The paper frames limited-supply dynamic pricing as a bandit problem through an index based on estimated total payoff under supply constraints. It identifies open questions involving broader algorithms, demand distributions, valuation dependence, and information sharing across prices.
- Conceptual contribution: The index assigns each price an estimated expected total payoff under the known supply constraint, rather than only its expected per-round revenue.
- Conceptual contribution: The reduction may extend to other index-based algorithms and settings where the best arm is not the arm with the highest expected per-round payoff.
- Open questions: A general black-box reduction is unresolved because algorithms such as EXP3 spend prohibitively large amounts of time exploring.
- Open questions: Open problems include extending guarantees to irregular distributions, all regular distributions in the improved-rate setting, and stronger lower bounds for regular distributions.
- Open questions: The results do not immediately extend beyond IID valuations, including random permutations of adversarial values or adversarial valuations.
- Open questions: The algorithms do not directly use information that sales at one price reveal about smaller prices or that sales rates are non-increasing.
Appendix A: Benchmark comparison
Appendix A compares fixed-price strategies with the offline benchmark for regular demand distributions, using revenue concavity and correlation-gap arguments. It establishes additive and multiplicative approximation properties and diminishing marginal returns as the number of agents changes.
- Proof structure: The proof of the appendix lemma uses a price p∗ selected through the reserve price and the inverse sales rate, with revenue monotonicity handling the relevant cases.The argument concludes by applying the claims at p = p∗ to obtain the required sales-rate bound.
- Fixed-price benchmark comparison: A fixed-price strategy achieves an additive approximation to the offline benchmark for every regular demand distribution.This is stated as Lemma A.1, though the quantitative bound is truncated in the supplied passage.
- Fixed-price benchmark comparison: Revenue from a fixed price is bounded using the Myerson reserve price and the concavity of revenue as a function of selling probability.Symmetry gives each agent the same allocation probability, and Jensen’s inequality compares the auction revenue with a single-price revenue benchmark.
- Multiplicative comparison: A multiplicative version of the benchmark comparison also holds for regular demand distributions.The appendix identifies this stronger result as Lemma A.4 and notes that it follows from the preceding claims.
- Correlation-gap comparison: A correlation-gap argument lower-bounds independent-demand fixed-price revenue by a constant multiple of the corresponding correlated environment’s revenue.The rank function min(|Y|, k) is the k-uniform matroid rank function, and correlated high-valued agents are always bounded by k.
- Revenue monotonicity: For prices above the k/n quantile, increasing the price and reducing the number of agents yields diminishing marginal returns in fixed-price revenue.The appendix states this as Corollary (Lemma 7.3), comparing prices p ≤ p′ and n′ ≤ n.
Appendix B: Monotone Hazard Rate distributions
Appendix B records properties of monotone hazard rate distributions through log-concavity of the sales rate. It derives a lower bound on sales at the reserve price and bounds the sensitivity of the inverse sales rate.
- Definitions: For a distribution F, the sales rate is S(x) = 1 − F(x), while f(x) denotes the density and F(x) the cumulative distribution function.These definitions are used throughout the appendix.
- Characterization: MHR distributions are characterized by a log-concave sales rate, meaning log S(x) is concave in x.This characterization is stated as Fact B.1.
- Reserve-price sales rate: S(r) ≥ 1/e at any Myerson reserve price r for an MHR distribution supported on [0, ∞].The reserve price maximizes R(x) = xS(x), and the appendix derives this bound from the first-order condition and log-concavity.
- Inverse sales-rate sensitivity: Log-concavity is used to bound the sensitivity of the inverse sales rate for sales probabilities α and β with β ≥ α.The appendix introduces this result as Claim B.3 and proves it using concavity and monotonicity of log S.