Selling Multiple Correlated Goods: Revenue Maximization and MenuSize
Complexity
(old title: The MenuSize Complexity of Auctions)
Sergiu Hart and Noam Nisan
(*) Errata and misprints:
 Page 1016, line 14 (fourth line in the Proof of Lemma
9.1): the inequality should be
H^{1/K} ≤ 1 + ε^{2}
("1+" is missing; the rest is ok).
Thanx to Yannai Gonczarowski for
pointing this out.
 Page 1021, last line (formula (22)): in the first sum,
x_{1} should be
x_{∞}
 Page 1022, line 5 of Remark A.8(b):
"w(1) = 1" should be
w(1) = 1/2
(the rest is ok).
Thanx to Ran BenMoshe
for pointing this out.
Abstract
We consider the
menu size
of mechanisms as a measure of their
complexity, and study how it relates to revenue extraction capabilities.
Our setting has a single revenuemaximizing seller selling a number of
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 when there are two (or more)
goods,
simple mechanisms of bounded menu sizesuch as selling the goods
separately, or as a bundle, or deterministicallymay yield only a
negligible fraction of the optimal revenue. We show that the revenue
increases at most linearly in menu size, and exhibit valuations for
which
it increases at least as a fixed fractional power of menu size.
For deterministic mechanisms,
their revenue is shown to be comparable to the revenue achievable by
mechanisms with similar menu size (which is exponential in the number of
goods). Thus, it is the number of possible outcomes
(i.e., the menu size) rather than restrictions on allocations (e.g.,
being deterministic) that stands out as the critical limitation for
revenue extraction.

First version: August 2012

The Hebrew University of Jerusalem,
Center for Rationality DP637, April 2013

http://arxiv.org/abs/1304.6116

ACM Conference on Economic Commerce, 2013 [abstract]

Revised, November 2017

Revised, November 2018

Revised, June 2019

Journal of Economic Theory 183 (2019), 9911029
Last modified:
© Sergiu Hart