The Menu-Size Complexity of Auctions

Sergiu Hart
Noam Nisan

We consider the menu size of auctions as a measure of auction complexity and study how it affects revenue. Our setting
has a single revenue-maximizing seller selling two or more heterogenous items to a single buyer whose private values
for the items are drawn from a (possibly correlated) known distribution, and whose valuation is additive over the
items. We show that the revenue may increase arbitrarily with menu size and that a bounded menu size can not ensure any
positive fraction of the optimal revenue. The menu size turns out to "nail down" the revenue properties of
deterministic auctions: their menu size may be at most exponential in the number of items and indeed their revenue may
be larger than that achievable by the simplest types of auctions by a factor that is exponential in the number of items
but no larger. Our model is related to a previously studied "unit-demand" model and our results also answer an open
problem in that model.

April, 2013