A Simple and Approximately Optimal Mechanism for an Additive Buyer

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

Research output: Contribution to journalArticle

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.

Original languageEnglish (US)
Article number24
JournalJournal of the ACM
Volume67
Issue number4
DOIs
StatePublished - Aug 6 2020

All Science Journal Classification (ASJC) codes

  • Software
  • Control and Systems Engineering
  • Information Systems
  • Hardware and Architecture
  • Artificial Intelligence

Keywords

  • Mechanism design
  • approximation
  • auction design
  • revenue
  • simple vs. optimal

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