preprint · arXiv (Cornell University) · 2015
The Sample Complexity of Revenue Maximization
Cited by 6Open access
Abstract
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.
Cite this paper
Cole, R., & Roughgarden, T. (2015). The Sample Complexity of Revenue Maximization. arXiv (Cornell University). https://doi.org/10.48550/arxiv.1502.00963
Cole, Richard, and Tim Roughgarden. “The Sample Complexity of Revenue Maximization.” arXiv (Cornell University), 2015, https://doi.org/10.48550/arxiv.1502.00963.
Cole, Richard, and Tim Roughgarden. 2015. “The Sample Complexity of Revenue Maximization.” arXiv (Cornell University). https://doi.org/10.48550/arxiv.1502.00963.
Cole, R. and Roughgarden, T. (2015) ‘The Sample Complexity of Revenue Maximization’, arXiv (Cornell University). Available at: https://doi.org/10.48550/arxiv.1502.00963.
@misc{cole2015sample,
title = {{The Sample Complexity of Revenue Maximization}},
author = {Cole, Richard and Roughgarden, Tim},
journal = {arXiv (Cornell University)},
year = {2015},
doi = {10.48550/arxiv.1502.00963}
}Made from the index record. Check names, capitalisation and page numbers against the paper. Need another style? AI for Research has over 10,000.