The complexity of optimal multidimensional pricing for a unit-demand buyer

• 成果类型: Article
• 署名作者: Chen, Xi; Diakonikolas, Ilias; Paparas, Dimitris; Sun, Xiaorui; Yannakakis, Mihalis
• 署名单位: Columbia University; University of Southern California; University of Wisconsin System; University of Wisconsin Madison; University of California System; University of California Berkeley
• 刊物名称: GAMES AND ECONOMIC BEHAVIOR
• ISSN/ISSBN: 0899-8256
• DOI: 10.1016/j.geb.2018.03.016
• 发表日期: 2018
• 页码: 139-164
• 关键词: Deterministic mechanism design; NP-completeness; Complexity theory; algorithms

摘要

We resolve the complexity of revenue-optimal deterministic auctions in the unit-demand single-buyer Bayesian setting, i.e., the optimal item pricing problem, when the buyer's values for the items are independent. We show that the problem of computing a revenue optimal pricing can be solved in polynomial time for distributions of support size 2, and its decision version is NP-complete for distributions of support size 3. We also show that the problem remains NP-complete for the case of identical distributions. (C) 2018 Elsevier Inc. All rights reserved.