The Sample Complexity of Up-to-ϵ Multi-dimensional Revenue Maximization

Yannai A. Gonczarowski, S. Matthew Weinberg

Research output: Contribution to journalArticlepeer-review

14 Scopus citations

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.

Original languageEnglish (US)
Article number15
JournalJournal of the ACM
Volume68
Issue number3
DOIs
StatePublished - Jun 2021

All Science Journal Classification (ASJC) codes

  • Software
  • Control and Systems Engineering
  • Information Systems
  • Hardware and Architecture
  • Artificial Intelligence

Keywords

  • Algorithmic game theory
  • PAC learning
  • algorithmic mechanism design
  • approximate revenue maximization
  • auctions
  • generalization bounds
  • multi-dimensional auctions
  • sample complexity

Fingerprint

Dive into the research topics of 'The Sample Complexity of Up-to-ϵ Multi-dimensional Revenue Maximization'. Together they form a unique fingerprint.

Cite this