A simple and approximately optimal mechanism for a buyer with complements

Alon Eden, Michal Feldman, Ophir Friedler, Inbal Talgam-Cohen, S. Matthew Weinberg

Research output: Contribution to journalArticlepeer-review

Abstract

We consider a revenue-maximizing seller with m heterogeneous items and a single buyer whose valuation for the items may exhibit both substitutes and complements. We show that the better of selling the items separately and bundling them together—guarantees a Θ(d)-fraction of the optimal revenue, where d is a measure of the degree of complementarity; it extends prior work showing that the same simple mechanism achieves a constant-factor approximation when buyer valuations are subadditive (the most general class of complement-free valuations). Our proof is enabled by a recent duality framework, which we use to obtain a bound on the optimal revenue in the generalized setting. Our technical contributions are domain specific to handle the intricacies of settings with complements. One key modeling contribution is a tractable notion of “degree of complementarity” that admits meaningful results and insights—we demonstrate that previous definitions fall short in this regard.

Original languageEnglish (US)
Pages (from-to)188-206
Number of pages19
JournalOperations Research
Volume69
Issue number1
DOIs
StatePublished - Jan 1 2021

All Science Journal Classification (ASJC) codes

  • Computer Science Applications
  • Management Science and Operations Research

Keywords

  • Approximation
  • Complements
  • Mechanism design
  • Revenue

Fingerprint Dive into the research topics of 'A simple and approximately optimal mechanism for a buyer with complements'. Together they form a unique fingerprint.

Cite this