The Menu-Size Complexity of Auctions
Sergiu Hart and Noam Nisan
We consider the menu size of auctions and mechanisms in general
as a measure of
their complexity, and study how it affects revenue. Our setting
has a single revenue-maximizing seller selling two or more
heterogeneous goods to a single buyer whose private values for the
goods are drawn from a (possibly correlated) known distribution,
and whose valuation is additive
over the goods.
We show that the revenue may increase arbitrarily
with menu size and that a bounded menu size cannot ensure
any positive fraction of the optimal revenue.
The menu size turns out to "pin down" the revenue properties
of deterministic mechanisms: their menu size is at most
exponential in the number of goods,
and indeed their revenue may be larger than that achievable
by the simplest types of auctions by a similar factor.
Our model is related to a previously studied "unit-demand" model and
our results also answer an open problem in that model.
First version: August 2012
The Hebrew University of Jerusalem,
Center for Rationality DP-637, April 2013
ACM Conference on Economic Commerce, 2013 [abstract]
Revised, November 2017
© Sergiu Hart