The Menu-Size Complexity of Auctions
Sergiu Hart and 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.
First version: August 2012
The Hebrew University of Jerusalem,
Center for Rationality DP-637, April 2013
ACM Conference on Economic Commerce, 2013 [abstract]
© Sergiu Hart