A Simple and Approximately Optimal Mechanism for a Buyer with Complements

Alon Eden (), Michal Feldman (), Ophir Friedler (), Inbal Talgam-Cohen () and S. Matthew Weinberg ()
Additional contact information
Alon Eden: Computer Science Department, Harvard University, Cambridge, Massachusetts 02139, Simons Institute for the Theory of Computing, Berkeley, California 94720
Michal Feldman: Blavatnik School of Computer Science, Tel Aviv University, Tel Aviv 6997801, Israel, Microsoft Research, Herzliya 4672513, Israel
Ophir Friedler: Blavatnik School of Computer Science, Tel Aviv University, Tel Aviv 6997801, Israel
Inbal Talgam-Cohen: Computer Science Department, Technion, Haifa 3200003, Israel
S. Matthew Weinberg: Simons Institute for the Theory of Computing, Berkeley, California 94720, Computer Science Department, Princeton University, Princeton, New Jersey 08540

Operations Research, 2021, vol. 69, issue 1, 188-206

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.

Keywords: mechanism design; revenue; approximation; complements (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
https://doi.org/10.1287/opre.2020.2039 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:69:y:2021:i:1:p:188-206

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().