A Simple and Approximately Optimal Mechanism for a Buyer with Complements

• 成果类型: Article
• 署名作者: Eden, Alon; Feldman, Michal; Friedler, Ophir; Talgam-Cohen, Inbal; Weinberg, S. Matthew
• 署名单位: Harvard University; Tel Aviv University; Technion Israel Institute of Technology; Princeton University
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.2020.2039
• 发表日期: 2021
• 页码: 188-206
• 关键词: Revenue maximization; Optimal auction

摘要

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 Theta(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.