The sample complexity of revenue maximization

By Richard J. Cole, Tim Roughgarden. Symposium on the Theory of Computing, 2014

295 citations recorded by the source corpus.

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 of this paper 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 nonidentical 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 ε 0, so that a (1 -- ε)-approximation of the optimal revenue is achievable? We prove that, under standard tail conditions on the underlying distributions, m = poly(k, 1/ε) 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. To capture how our sample complexity upper bound depends on the set of allowable distributions, we introduce α-strongly regular distributions, which interpolate between the well-studied classes of regular (α = 0) and MHR (α = 1) distributions. We give evidence that this definition is of independent interest.

Subfields: Artificial Intelligence, Management Science and Operations Research, Marketing

View Paper: https://www.semanticscholar.org/paper/03ac1da4e4b713bf7017f71377aaa23c6c6b8763

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Management Science and Operations Research

In Marketing

Citations in the corpus

Algorithms with predictions (2020, background): “For instance, Devanur and Hayes (2009) and Vee et al. (2010) explored how predictions can be used to obtain nearly optimal online matching bounds, while Cole and Roughgarden (2014) and Medina and Vassilvitskii (2017) showed how to learn from samples to maximize revenue in auction settings.”
Competitive caching with machine learned advice (2018, methodology): “Introduced in the seminal work of Cole and Roughgarden [CR14], this notion of Learning from Samples, can be viewed as ﬁrst designing a good prediction function, h , and then using it in the algorithms.”