A Simple and Approximately Optimal Mechanism for an Additive Buyer

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

Research output: Contribution to journalArticlepeer-review


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 languageAmerican English
Article number24
JournalJournal of the ACM
Issue number4
StatePublished - Aug 6 2020

ASJC Scopus subject areas

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


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


Dive into the research topics of 'A Simple and Approximately Optimal Mechanism for an Additive Buyer'. Together they form a unique fingerprint.

Cite this