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.|
|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|
|Pages:||188 - 206|
|Type of Material:||Journal Article|
|Journal/Proceeding Title:||Operations Research|
Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.