A Simple and Approximately Optimal Mechanism for an Additive Buyer
- 16 June 2020
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 67 (4), 1-40
- https://doi.org/10.1145/3398745
Abstract
We consider a monopolist seller with n heterogeneous items, facing a single buyer. The buyer has a value for each item drawn independently according to (non-identical) distributions, and her value for a set of items is additive. The seller aims to maximize his revenue. We suggest using the a priori better of two simple pricing methods: selling the items separately, each at its optimal price, and bundling together, in which the entire set of items is sold as one bundle at its optimal price. We show that for any distribution, this mechanism achieves a constant-factor approximation to the optimal revenue. Beyond its simplicity, this is the first computationally tractable mechanism to obtain a constant-factor approximation for this multi-parameter problem. We additionally discuss extensions to multiple buyers and to valuations that are correlated across items.Keywords
Funding Information
- National Science Foundation (CCF-1717899)
This publication has 36 references indexed in Scilit:
- Revenue Maximization for Selling Multiple Correlated ItemsPublished by Springer Science and Business Media LLC ,2015
- The power of randomness in Bayesian optimal mechanism designGames and Economic Behavior, 2015
- Revenue maximization with a single sampleGames and Economic Behavior, 2015
- Pricing lotteriesJournal of Economic Theory, 2015
- The Complexity of Optimal Mechanism DesignPublished by Society for Industrial & Applied Mathematics (SIAM) ,2013
- On revenue maximization for selling multiple independently distributed itemsProceedings of the National Academy of Sciences of the United States of America, 2013
- Multidimensional mechanism design: Revenue maximization and the multiple-good monopolyJournal of Economic Theory, 2007
- The Lovely but Lonely Vickrey AuctionPublished by MIT Press ,2005
- Haggling over substitutesJournal of Economic Theory, 2004
- Optimal Auction DesignMathematics of Operations Research, 1981