# The Menu-Size Complexity of Revenue Approximation

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 22 Apr 2016.

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

- [Mode Connectivity in Auction Design](https://mlsanity.com/paper/2305.11005/) (2023)
- [Recommender Systems meet Mechanism Design](https://mlsanity.com/paper/2110.12558/) (2021)
- [A Robust Multi-Item Auction Design with Statistical Learning](https://mlsanity.com/paper/2302.00941/) (2023)

## Abstract (arXiv)

Consider a monopolist selling n items to an additive buyer whose item values are drawn from independent distributions F1,F2,ldots,Fn possibly having unbounded support. Unlike in the single-item case, it is well known that the revenue-optimal selling mechanism (a pricing scheme) may be complex, sometimes requiring a continuum of menu entries. Also known is that simple mechanisms with a bounded number of menu entries can extract a constant fraction of the optimal revenue. Nonetheless, whether an arbitrarily high fraction of the optimal revenue can be extracted via a bounded menu size remained open. We give an affirmative answer: for every n and varepsilon>0, there exists C=C(n,varepsilon) s.t. mechanisms of menu size at most C suffice for obtaining (1-varepsilon) of the optimal revenue from any F1,ldots,Fn. We prove upper and lower bounds on the revenue-approximation complexity C(n,varepsilon) and on the deterministic communication complexity required to run a mechanism achieving such an approximation.