# Sampling and Representation Complexity of Revenue Maximization

arXiv: https://arxiv.org/abs/1402.4535 · HTML: https://mlsanity.com/paper/1402.4535/

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 19 Feb 2014.

## Built on by (most cited first, 7 of 7)

- [Benefits of Permutation-Equivariance in Auction Mechanisms](https://mlsanity.com/paper/2210.05579/) (2022)
- [New Guarantees for Learning Revenue Maximizing Menus of Lotteries and Two-Part Tariffs](https://mlsanity.com/paper/2302.11700/) (2023)
- [Mode Connectivity in Auction Design](https://mlsanity.com/paper/2305.11005/) (2023)
- [Recommender Systems meet Mechanism Design](https://mlsanity.com/paper/2110.12558/) (2021)
- [An Interpretable Automated Mechanism Design Framework with Large Language Models](https://mlsanity.com/paper/2502.12203/) (2025)
- [Learning Optimal Posted Prices for a Unit-Demand Buyer](https://mlsanity.com/paper/2506.02284/) (2025)
- [A Robust Multi-Item Auction Design with Statistical Learning](https://mlsanity.com/paper/2302.00941/) (2023)

## 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.