The Sample Complexity of Up-to-ε Multi-dimensional Revenue Maximization
- 22 March 2021
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 68 (3), 1-28
- https://doi.org/10.1145/3439722
Abstract
We consider the sample complexity of revenue maximization for multiple bidders in unrestricted multi-dimensional settings. Specifically, we study the standard model of \(\) additive bidders whose values for \(\) heterogeneous items are drawn independently. For any such instance and any \(\), we show that it is possible to learn an \(\)-Bayesian Incentive Compatible auction whose expected revenue is within \(\) of the optimal \(\)-BIC auction from only polynomially many samples. Our fully nonparametric approach is based on ideas that hold quite generally and completely sidestep the difficulty of characterizing optimal (or near-optimal) auctions for these settings. Therefore, our results easily extend to general multi-dimensional settings, including valuations that are not necessarily even subadditive, and arbitrary allocation constraints. For the cases of a single bidder and many goods, or a single parameter (good) and many bidders, our analysis yields exact incentive compatibility (and for the latter also computational efficiency). Although the single-parameter case is already well understood, our corollary for this case extends slightly the state of the art.
Keywords
Funding Information
- ISF (1435/14)
- Israel-USA Binational Science Foundation (2014389)
- European Union's Horizon 2020 research and innovation programme (740282)
- NSF (CCF-1717899)
- NSF CAREER (CCF-1942497)
This publication has 36 references indexed in Scilit:
- Maximal revenue with multiple goods: Nonmonotonicity and other observationsTheoretical Economics, 2015
- Simple Mechanisms for a Subadditive Buyer and Applications to Revenue MonotonicityPublished by Association for Computing Machinery (ACM) ,2015
- Making the Most of Your SamplesPublished by Association for Computing Machinery (ACM) ,2015
- The power of randomness in Bayesian optimal mechanism designGames and Economic Behavior, 2015
- Revenue maximization with a single sampleGames and Economic Behavior, 2015
- Sampling and Representation Complexity of Revenue MaximizationLecture Notes in Computer Science, 2014
- Mechanism design via optimal transportPublished by Association for Computing Machinery (ACM) ,2013
- Algorithmic pricing via virtual valuationsPublished by Association for Computing Machinery (ACM) ,2007
- Haggling over substitutesJournal of Economic Theory, 2004
- Optimal Auction DesignMathematics of Operations Research, 1981