@booklet {sergiuhart-tmcoa2013,
	title = {Menu-Size Complexity of Auctions, The},
	howpublished = {Discussion Papers},
	year = {2013},
	month = {4},
	abstract = {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.},
	url = {http://www.ma.huji.ac.il/hart/abs/m-corr.html},
	author = {Sergiu Hart, Noam Nisan}
}
