Skip to main content

A Simple and Approximately Optimal Mechanism for a Buyer with Complements

Author(s): Eden, Alon; Feldman, Michal; Friedler, Ophir; Talgam-Cohen, Inbal; Weinberg, S Matthew

To refer to this page use:
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 𝛩(đť‘‘)-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.
Publication Date: 2021
Citation: Eden, Alon, Michal Feldman, Ophir Friedler, Inbal Talgam-Cohen, and S. Matthew Weinberg. "A Simple and Approximately Optimal Mechanism for a Buyer with Complements." Operations Research 69, no. 1 (2021): 188-206. doi:10.1287/opre.2020.2039
DOI: 10.1287/opre.2020.2039
ISSN: 0030-364X
EISSN: 1526-5463
Pages: 188 - 206
Type of Material: Journal Article
Journal/Proceeding Title: Operations Research
Version: Author's manuscript

Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.