The Complexity of Optimal Multidimensional Pricing

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

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract / Description of output

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.
Original languageEnglish
Title of host publicationProceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms
Pages1319-1328
Number of pages10
ISBN (Electronic)978-1-61197-340-2
DOIs
Publication statusPublished - 2014

Fingerprint

Dive into the research topics of 'The Complexity of Optimal Multidimensional Pricing'. Together they form a unique fingerprint.

Cite this