# Approximation Schemes for a Unit-Demand Buyer with Independent Items via Symmetries

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 13 May 2019.

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

- [Optimal-er Auctions through Attention](https://mlsanity.com/paper/2202.13110/) (2022)

## Abstract (arXiv)

We consider a revenue-maximizing seller with n items facing a single buyer. We introduce the notion of symmetric menu complexity of a mechanism, which counts the number of distinct options the buyer may purchase, up to permutations of the items. Our main result is that a mechanism of quasi-polynomial symmetric menu complexity suffices to guarantee a (1-varepsilon)-approximation when the buyer is unit-demand over independent items, even when the value distribution is unbounded, and that this mechanism can be found in quasi-polynomial time. Our key technical result is a polynomial time, (symmetric) menu-complexity-preserving black-box reduction from achieving a (1-varepsilon)-approximation for unbounded valuations that are subadditive over independent items to achieving a (1-O(varepsilon))-approximation when the values are bounded (and still subadditive over independent items). We further apply this reduction to deduce approximation schemes for a suite of valuation classes beyond our main result. Finally, we show that selling separately (which has exponential menu complexity) can be approximated up to a (1-varepsilon) factor with a menu of efficient-linear (f(varepsilon) · n) symmetric menu complexity.