Selling Multiple Correlated Goods: Revenue Maximization and Menu-Size Complexity (old title: "The Menu-Size Complexity of Auctions")

Sergiu Hart and Noam Nisan

Papers from arXiv.org

Abstract: We consider the well known, and notoriously difficult, problem of 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 when there are two (or more) goods, _simple mechanisms_ -- such as selling the goods separately or as a bundle -- _may yield only a negligible fraction of the optimal revenue_. This resolves the open problem of Briest, Chawla, Kleinberg, and Weinberg (JET 2015) who prove the result for at least three goods in the related setup of a unit-demand buyer. We also introduce the menu size as a simple measure of the complexity of mechanisms, and show that the revenue may increase polynomially with _menu size_ and that no bounded menu size can ensure any positive fraction of the optimal revenue. The menu size also turns out to "pin down" the revenue properties of deterministic mechanisms.

Date: 2013-04, Revised 2018-11
References: View references in EconPapers View complete reference list from CitEc
Citations:

Published in Journal of Economic Theory 183 (2019), 991-1029

Downloads: (external link)
http://arxiv.org/pdf/1304.6116 Latest version (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:arx:papers:1304.6116

Access Statistics for this paper

More papers in Papers from arXiv.org
Bibliographic data for series maintained by arXiv administrators ().