Sampling and Representation Complexity of Revenue Maximization
Not on the map. Why?
Abstract (arXiv)
We consider (approximate) revenue maximization in auctions where the distribution on input valuations is given via "black box" access to samples from the distribution. We observe that the number of samples required -- the sample complexity -- is tightly related to the representation complexity of an approximately revenue-maximizing auction. Our main results are upper bounds and an exponential lower bound on these complexities.
Key facts. Cited by 7 papers in the map (data through 7 Oct 2026). First posted on arXiv 19 Feb 2014.
Builds on
No reference list yet.
Built on by
Citing papers per year: 2021: 1; 2022: 1; 2023: 3; 2024: 0; 2025: 2.
7 papers.
- 2022Benefits of Permutation-Equivariance in Auction Mechanismscited by 7
- 2023New Guarantees for Learning Revenue Maximizing Menus of Lotteries and Two-Part Tariffscited by 4
- 2023Mode Connectivity in Auction Designcited by 3
- 2021Recommender Systems meet Mechanism Designcited by 2
- 2025An Interpretable Automated Mechanism Design Framework with Large Language Modelscited by 2
- 2025Learning Optimal Posted Prices for a Unit-Demand Buyercited by 1
- 2023A Robust Multi-Item Auction Design with Statistical Learningcited by 0
- 2025Learning Optimal Posted Prices for a Unit-Demand Buyer2 Jun 2025
- 2025An Interpretable Automated Mechanism Design Framework with Large Language Models16 Feb 2025
- 2023Mode Connectivity in Auction Design18 May 2023
- 2023New Guarantees for Learning Revenue Maximizing Menus of Lotteries and Two-Part Tariffs22 Feb 2023
- 2023A Robust Multi-Item Auction Design with Statistical Learning2 Feb 2023
- 2022Benefits of Permutation-Equivariance in Auction Mechanisms11 Oct 2022
- 2021Recommender Systems meet Mechanism Design25 Oct 2021