@article{cba18f60b7e74d6bbbaa2e66e5e0ffad,
title = "A Simple and Approximately Optimal Mechanism for an Additive Buyer",
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 = "Mechanism design, approximation, auction design, revenue, simple vs. optimal",
author = "Moshe Babaioff and Nicole Immorlica and Brendan Lucier and Weinberg, {S. Matthew}",
note = "Funding Information: Weinberg is supported by NSF CCF-1717899. Authors{\textquoteright} addresses: M. Babaioff, N. Immorlica, and B. Lucier, Microsoft Research, One Memorial Drive, Cambridge, MA 02139; emails: {moshe, nicimm, brlucier}@microsoft.com; S. Matthew Weinberg, Princeton University, 35 Olden Street, Princeton, NJ 08540; email: smweinberg@princeton.edu. Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from permissions@acm.org. {\textcopyright} 2020 Copyright held by the owner/author(s). Publication rights licensed to ACM. 0004-5411/2020/06-ART24 $15.00 https://doi.org/10.1145/3398745 Publisher Copyright: {\textcopyright} 2020 ACM.",
year = "2020",
month = aug,
day = "6",
doi = "10.1145/3398745",
language = "English (US)",
volume = "67",
journal = "Journal of the ACM",
issn = "0004-5411",
publisher = "Association for Computing Machinery (ACM)",
number = "4",
}