Source-linked AI summary
The Sample Complexity of Revenue Maximization
Richard Cole, Tim Roughgarden
TL;DR
The paper asks how much past data is needed to achieve near-optimal revenue in single-item auctions with unknown, independent, non-identical bidder distributions. It models sample-based truthful auction selection, introduces strongly regular distributions, and proves polynomial dependence on bidders and accuracy, with a constructive empirical-Myerson variant. The results show that close constant-factor revenue guarantees require distributional detail when bidder distributions differ.
Problem
The paper asks how many samples per bidder are necessary and sufficient to guarantee near-optimal expected revenue when valuation distributions are unknown and non-identical.
Method
The paper studies truthful auctions selected from samples and analyzes strongly regular product distributions, including a variant of the empirical Myerson auction.
Results
poly(k, 1/ϵ) samples are necessary and sufficient for a (1−ϵ)-approximation of optimal revenue over strongly regular distributions.
Takeaways & Limitations
With multiple bidders having non-identical distributions, sufficiently close constant approximations require detailed distributional understanding and essentially optimal resolution of bidder competition.
Takeaways & Limitations
The sample-complexity bounds depend on the allowable distribution class, and unrestricted distributions admit no finite uniform sample guarantee.
Abstract
from arXiv · showhide
In the design and analysis of revenue-maximizing auctions, auction performance is typically measured with respect to a prior distribution over inputs. The most obvious source for such a distribution is past data. The goal is to understand how much data is necessary and sufficient to guarantee near-optimal expected revenue. Our basic model is a single-item auction in which bidders' valuations are drawn independently from unknown and non-identical distributions. The seller is given $m$ samples from each of these distributions "for free" and chooses an auction to run on a fresh sample. How large does m need to be, as a function of the number k of bidders and eps > 0, so that a (1 - eps)-approximation of the optimal revenue is achievable? We prove that, under standard tail conditions on the underlying distributions, m = poly(k, 1/eps) samples are necessary and sufficient. Our lower bound stands in contrast to many recent results on simple and prior-independent auctions and fundamentally involves the interplay between bidder competition, non-identical distributions, and a very close (but still constant) approximation of the optimal revenue. It effectively shows that the only way to achieve a sufficiently good constant approximation of the optimal revenue is through a detailed understanding of bidders' valuation distributions. Our upper bound is constructive and applies in particular to a variant of the empirical Myerson auction, the natural auction that runs the revenue-maximizing auction with respect to the empirical distributions of the samples. Our sample complexity lower bound depends on the set of allowable distributions, and to capture this we introduce alpha-strongly regular distributions, which interpolate between the well-studied classes of regular (alpha = 0) and MHR (alpha = 1) distributions. We give evidence that this definition is of independent interest.
1 Introduction
The paper studies how much sample data is needed to choose a near-optimal truthful auction when bidders have unknown, independent, non-identical valuation distributions. It establishes polynomial sample complexity under strongly regular distributions and develops a constructive empirical-Myerson-based strategy.
- The Model: The seller uses m samples from each bidder’s unknown distribution to choose a truthful auction, then evaluates it on a fresh valuation profile against the optimal auction for the true distributions.The sample-based strategy must achieve at least (1−ϵ) times optimal expected revenue uniformly over an allowed distribution class.
- The Model: The sample complexity question is meaningful only after restricting the allowable distributions, because no finite sample count guarantees near-optimal revenue over unrestricted distributions.For sufficiently large-valued rare events, all observed samples can be zero, forcing the auction strategy to guess the relevant scale.
- Our Results: poly(k, 1/ϵ) samples are necessary and sufficient for a (1−ϵ)-approximation to optimal revenue over strongly regular distributions.The upper bound is constructive and applies to a variant of the empirical Myerson auction.
- Our Results: The lower bound’s dependence on k arises from the combination of bidder competition, non-identical distributions, and requiring a very close constant-factor approximation.Related relaxations can have sample complexity depending only on ϵ, including digital goods, i.i.d. regular bidders, or a 1/4-approximation target.
- Our Results: For sufficiently accurate constant approximations, prior-independent approaches cannot replace detailed knowledge of valuation distributions and near-optimal resolution of bidder competition.The empirical Myerson analysis excludes the very highest samples to avoid upper-tail errors caused by small samples.
2 Preliminaries
Myerson’s framework characterizes optimal single-item revenue through bidders’ virtual valuations and quantile-space revenue functions. The section also notes extensions to prior-independent auctions and grouped bidder settings.
- Extensions: The sample-complexity upper bound also yields a prior-independent auction achieving a (1 −ϵ)-approximation for different regular distributions when sufficiently many bidders of each type exist.The results extend to k groups with i.i.d. valuations within each group, with bounds depending on the number of bidders n.
- Revenue characterization: The revenue function represents a bidder’s sole-bidder expected revenue as R_i(q_i) = v(q_i) · q_i in quantile space.Here q_i is the probability that bidder i’s valuation is at least v.
- Revenue characterization: Expected virtual welfare equals expected revenue for every single-item auction.This equivalence makes virtual-welfare analysis useful for reasoning about revenue.
- Optimal auction: Myerson’s auction allocates to the bidder with the highest non-negative virtual valuation, yielding the optimal expected revenue.Virtual valuations may be ironed when they are not non-decreasing.
3 Statement of Main Results
The main theorems give matching qualitative upper and lower bounds: polynomially many samples suffice and are necessary for near-optimal revenue under strongly regular distributions. The lower bound depends substantially on the number of bidders and the regularity parameter.
- Upper bound: m = Ω(k^10/ϵ) samples suffice for a (1 −ϵ)-approximation under independent regular valuation distributions.The constructive strategy is a variant of the empirical Myerson auction.
- Lower bound: The lower bound grows as α decreases, with dependence on k that is linear or near-linear at the MHR and regular extremes.At α = 1 and α = 0, the stated lower bounds are Ω(√k/ϵ) and Ω(k/ϵ), respectively.
- Lower bound: The lower-bound theorem specifies separate regimes for 0 < α < 1 and α = 0 through conditions involving m, α, k, and ϵ.These regimes include the inequalities and sample bounds stated in parts iii–v of Theorem 3.2.
4 Applications of Strong Regularity
α-strong regularity interpolates between regular and MHR distributions and supports generalized revenue guarantees. The section applies this interpolation to quantile bounds and approximation results for existing mechanisms.
- Definition and interpolation: The definition is presented as independently useful because it broadens the standard distribution classes used in Bayesian revenue guarantees.It interpolates between the previously common classes of all, regular, and MHR distributions.
- Quantile bound: q(r) ≥ α^1/(1−α) for an α-strongly regular distribution with monopoly price r.This generalizes the corresponding MHR quantile property.
- Applications: α-strong regularity extends an existing social-network revenue guarantee by replacing the MHR term 1/e with α^1/(1−α).The extension follows by reoptimizing the proof under the relaxed distributional assumption.
- Applications: For downward-closed single-parameter environments, VCG with eager monopoly reserves earns at least α/(α+1) of optimal revenue.The result applies when bidders’ valuations are drawn from α-strongly regular distributions.
5 The Lower Bound: Proof of Theorem 3.2
The lower bound constructs α-strongly regular bidder distributions that make unseen high valuations ambiguous, forcing every auction strategy to lose a nonzero fraction of optimal revenue. This yields polynomial sample requirements, including Ω(k/ε) for regular distributions and stronger bounds for other α values.
- Ω(k/ε^(1/(1+α))) samples are necessary for 1/k ≤ α < 1 and sufficiently small constant ε.
- Ω(k/ε) samples are necessary for a (1 − ε)-approximation in the regular case α = 0.
- The hard instance truncates α-strongly regular base distributions at random points, creating type A and type B bidders with different virtual valuations at truncation points.Each constructed distribution remains α-strongly regular, while its virtual valuation jumps at the truncation point.
- The lower bound exploits a gap between the virtual valuation at a truncation point and the linear virtual valuation below it.This gap is identified as the source of the lower bound in Theorem 3.2.
- An event E occurs with positive probability under which every auction strategy allocates to a non-optimal bidder often enough to lose ε(α, δ)R* in expected virtual welfare.Because optimal virtual welfare dominates strategy virtual welfare pointwise, this implies a revenue ratio of at most 1 − ε(α, δ).
6 The Upper Bound
The upper bound analyzes a constructive empirical Myerson auction that estimates each bidder’s revenue curve from samples, irons it, and runs Myerson’s allocation and payment rule on the resulting empirical virtual values. With sufficiently many polynomially many samples, it achieves a (1 − ε)-approximation.
- The auction constructs each bidder’s empirical revenue curve from ordered samples, discards the largest samples, adds boundary points, and connects the remaining points.Discarding the largest samples avoids poor approximation at the high-value end, which matters most for revenue.
- Taking the least concave upper bound produces the ironed empirical revenue curve, whose slopes define nondecreasing empirical ironed virtual values.
- The empirical auction awards the item to the bidder with the highest non-negative empirical ironed virtual value and charges the lowest bid needed to win.
- The analysis bounds empirical quantile and revenue-curve deviations with high probability, then uses these bounds to control expected revenue loss relative to Myerson’s auction.
7 Conclusions
The paper establishes polynomial sample complexity for learning near-optimal single-item auctions under strongly regular distributions. It closes by identifying tightness, broader environments, computational difficulty, and strategic-data questions as open directions.
- The paper gives upper and lower sample-complexity bounds for learning near-optimal single-item auctions from i.i.d. samples of unknown distributions.
- The required number of samples scales polynomially with the number of bidders k and the inverse accuracy 1/ε.
- Open problems include proving tight bounds in k and 1/ε and extending sample-complexity guarantees beyond single-item auctions.
- Further directions ask whether learning can be information-theoretically easy but computationally hard, especially in richer mechanism settings.
- The paper also asks whether near-optimal auctions remain learnable when sample-contributing bidders later participate strategically in the final auction.