Format

Send to

Choose Destination
Proc Natl Acad Sci U S A. 2013 Jul 9;110(28):11232-7. doi: 10.1073/pnas.1309533110. Epub 2013 Jun 24.

On revenue maximization for selling multiple independently distributed items.

Author information

1
Institute for Interdisciplinary Information Sciences, Tsinghua University, Beijing 100084, China.

Abstract

Consider the revenue-maximizing problem in which a single seller wants to sell k different items to a single buyer, who has independently distributed values for the items with additive valuation. The k = 1 case was completely resolved by Myerson's classical work in 1981, whereas for larger k the problem has been the subject of much research efforts ever since. Recently, Hart and Nisan analyzed two simple mechanisms: selling the items separately, or selling them as a single bundle. They showed that selling separately guarantees at least a c/log2 k fraction of the optimal revenue; and for identically distributed items, bundling yields at least a c/log k fraction of the optimal revenue. In this paper, we prove that selling separately guarantees at least c/log k fraction of the optimal revenue, whereas for identically distributed items, bundling yields at least a constant fraction of the optimal revenue. These bounds are tight (up to a constant factor), settling the open questions raised by Hart and Nisan. The results are valid for arbitrary probability distributions without restrictions. Our results also have implications on other interesting issues, such as monotonicity and randomization of selling mechanisms.

KEYWORDS:

auction; mechanism design

Supplemental Content

Full text links

Icon for HighWire Icon for PubMed Central
Loading ...
Support Center