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

DOI10.1145/3439722MaRDI QIDQ5056403zbMATH OpenOpenAlexFDO

Authors Yannai A. Gonczarowski, S. Matthew Weinberg

Publication date 8 December 2022

Published in Journal of the ACM (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1808.02458

zbMATH Keywords

auctionsalgorithmic mechanism designalgorithmic game theoryPAC learninggeneralization boundssample complexitymulti-dimensional auctionsapproximate revenue maximization

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Auctions, bargaining, bidding and selling, and other market models (91B26) Algorithmic game theory and complexity (91A68) Mechanism design theory (91B03)

Abstract: We consider the sample complexity of revenue maximization for multiple bidders in unrestricted multi-dimensional settings. Specifically, we study the standard model of $n$ additive bidders whose values for $m$ heterogeneous items are drawn independently. For any such instance and any $varepsilon>0$, we show that it is possible to learn an $varepsilon$-Bayesian Incentive Compatible auction whose expected revenue is within $varepsilon$ of the optimal $varepsilon$-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.

Recommendations

• The sample complexity of revenue maximization
• Sampling and Representation Complexity of Revenue Maximization
• Settling the sample complexity of single-parameter revenue maximization
• The sample complexity of auctions with side information
• Revenue maximization with a single sample

Cited in

(7)

• Improved two sample revenue guarantees via mixed-integer linear programming
• Settling the sample complexity of single-parameter revenue maximization
• The sample complexity of revenue maximization
• Selling to multiple no-regret buyers
• The sample complexity of auctions with side information
• On the optimal fixed-price mechanism in bilateral trade
• Sampling and Representation Complexity of Revenue Maximization

This page was built for publication: The Sample Complexity of Up-to-ε Multi-dimensional Revenue Maximization

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5056403)