Skip to main content

A Simple and Approximately Optimal Mechanism for an Additive Buyer

Author(s): Babaioff, Moshe; Immorlica, Nicole; Lucier, Brendan; Weinberg, S Matthew

Download
To refer to this page use: http://arks.princeton.edu/ark:/88435/pr1c82c
Full metadata record
DC FieldValueLanguage
dc.contributor.authorBabaioff, Moshe-
dc.contributor.authorImmorlica, Nicole-
dc.contributor.authorLucier, Brendan-
dc.contributor.authorWeinberg, S Matthew-
dc.date.accessioned2021-10-08T19:47:56Z-
dc.date.available2021-10-08T19:47:56Z-
dc.date.issued2020-06en_US
dc.identifier.citationBabaioff, Moshe, Nicole Immorlica, Brendan Lucier, and S. Matthew Weinberg. "A Simple and Approximately Optimal Mechanism for an Additive Buyer." Journal of the ACM 67, no. 4 (2020): 24:1-24:40. doi:10.1145/3398745en_US
dc.identifier.issn0004-5411-
dc.identifier.urihttps://arxiv.org/pdf/1405.6146.pdf-
dc.identifier.urihttp://arks.princeton.edu/ark:/88435/pr1c82c-
dc.description.abstractWe 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.en_US
dc.format.extent24:1 - 24:40en_US
dc.language.isoen_USen_US
dc.relation.ispartofJournal of the ACMen_US
dc.rightsAuthor's manuscripten_US
dc.titleA Simple and Approximately Optimal Mechanism for an Additive Buyeren_US
dc.typeJournal Articleen_US
dc.identifier.doi10.1145/3398745-
dc.identifier.eissn1557-735X-
pu.type.symplectichttp://www.symplectic.co.uk/publications/atom-terms/1.0/journal-articleen_US

Files in This Item:
File Description SizeFormat 
SimpleApproximateOptimalMechanismAdditiveBuyer.pdf532.48 kBAdobe PDFView/Download


Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.