TY - JOUR
T1 - The Sample Complexity of Up-to-ϵ Multi-dimensional Revenue Maximization
AU - Gonczarowski, Yannai A.
AU - Weinberg, S. Matthew
N1 - Funding Information:
An extended abstract of this work appeared in FOCS 2018 [Gonczarowski and Weinberg 2018]. This research was conducted while Gonczarowski was at the Hebrew University of Jerusalem and Microsoft Research. Gonczarowski was supported in part by the Adams Fellowship Program of the Israel Academy of Sciences and Humanities. His work was supported in part by ISF grant 1435/14 administered by the Israeli Academy of Sciences, by Israel-USA Binational Science Foundation (BSF) grant number 2014389, and by the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement No 740282). Weinberg was supported by NSF CCF-1717899 and by NSF CAREER award CCF-1942497. Authors’ addresses: Y. A. Gonczarowski, Microsoft Research, One Memorial Drive, Cambridge, MA 02139; email: yan-nai@gonch.name; S. M. Weinberg, Princeton University, 35 Olden Street, Princeton, NJ 08540; email: smweinberg@ princeton.edu. Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from permissions@acm.org. © 2021 Copyright held by the owner/author(s). Publication rights licensed to ACM. 0004-5411/2021/03-ART15 $15.00 https://doi.org/10.1145/3439722
Funding Information:
This research was conducted while Gonczarowski was at the Hebrew University of Jerusalem and Microsoft Research. Gonczarowski was supported in part by the Adams Fellowship Program of the Israel Academy of Sciences and Humanities. His work was supported in part by ISF grant 1435/14 administered by the Israeli Academy of Sciences, by Israel-USA Binational Science Foundation (BSF) grant number 2014389, and by the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation programme (grant agreement No 740282).Weinberg was supported by NSF CCF-1717899 and by NSF CAREER award CCF-1942497.
Publisher Copyright:
© 2021 Copyright held by the owner/author(s). Publication rights licensed to ACM.
PY - 2021/6
Y1 - 2021/6
N2 - 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.
AB - 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.
KW - Algorithmic game theory
KW - PAC learning
KW - algorithmic mechanism design
KW - approximate revenue maximization
KW - auctions
KW - generalization bounds
KW - multi-dimensional auctions
KW - sample complexity
UR - http://www.scopus.com/inward/record.url?scp=85119949561&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85119949561&partnerID=8YFLogxK
U2 - 10.1145/3439722
DO - 10.1145/3439722
M3 - Article
AN - SCOPUS:85119949561
SN - 0004-5411
VL - 68
JO - Journal of the ACM
JF - Journal of the ACM
IS - 3
M1 - 15
ER -