A simple and approximately optimal mechanism for an additive Buyer

Moshe Babaioff, Nicole Immorlica, Brendan Lucier, S. Matthew Weinberg

Research output: Chapter in Book/Report/Conference proceedingConference contribution

69 Scopus citations

Abstract

We consider a monopolist seller with n heterogeneousitems, facing a single buyer. The buyer hasa value for each item drawn independently according to(non-identical) distributions, and his value for a set ofitems is additive. The seller aims to maximize his revenue.It is known that an optimal mechanism in this setting maybe quite complex, requiring randomization [19] and menusof infinite size [15]. Hart and Nisan [17] have initiated astudy of two very simple pricing schemes for this setting:item pricing, in which each item is priced at its monopolyreserve; and bundle pricing, in which the entire set ofitems is priced and sold as one bundle. Hart and Nisan [17]have shown that neither scheme can guarantee more thana vanishingly small fraction of the optimal revenue. Insharp contrast, we show that for any distributions, thebetter of item and bundle pricing is a constant-factorapproximation to the optimal revenue. We further discussextensions to multiple buyers and to valuations that arecorrelated across items.

Original languageEnglish (US)
Title of host publicationProceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
PublisherIEEE Computer Society
Pages21-30
Number of pages10
ISBN (Electronic)9781479965175
DOIs
StatePublished - Dec 7 2014
Externally publishedYes
Event55th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2014 - Philadelphia, United States
Duration: Oct 18 2014Oct 21 2014

Publication series

NameProceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
ISSN (Print)0272-5428

Other

Other55th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2014
CountryUnited States
CityPhiladelphia
Period10/18/1410/21/14

All Science Journal Classification (ASJC) codes

  • Computer Science(all)

Fingerprint Dive into the research topics of 'A simple and approximately optimal mechanism for an additive Buyer'. Together they form a unique fingerprint.

  • Cite this

    Babaioff, M., Immorlica, N., Lucier, B., & Weinberg, S. M. (2014). A simple and approximately optimal mechanism for an additive Buyer. In Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS (pp. 21-30). [6978986] (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS). IEEE Computer Society. https://doi.org/10.1109/FOCS.2014.11