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

Xi Chen, Ilias Diakonikolas, Dimitris Paparas, Xiaorui Sun and Mihalis Yannakakis

Games and Economic Behavior, 2018, vol. 110, issue C, 139-164

Abstract: 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.

Keywords: Deterministic mechanism design; NP-completeness; Complexity theory; Algorithms (search for similar items in EconPapers)
Date: 2018
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (3)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0899825618300484
Full text for ScienceDirect subscribers only

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:eee:gamebe:v:110:y:2018:i:c:p:139-164

DOI: 10.1016/j.geb.2018.03.016

Access Statistics for this article

Games and Economic Behavior is currently edited by E. Kalai

More articles in Games and Economic Behavior from Elsevier
Bibliographic data for series maintained by Catherine Liu ().