The Menu-Size Complexity of Auctions
Sergiu Hart and Noam Nisan
Abstract
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
-
http://arxiv.org/abs/1304.6116
-
ACM Conference on Economic Commerce, 2013 [abstract]
-
Revised, November 2017
See also:
Last modified:
© Sergiu Hart