The Complexity of Optimal Multidimensional Pricing

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

doi:10.1137/1.9781611973402.97

The Complexity of Optimal Multidimensional Pricing

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

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

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.

Original language	English
Title of host publication	Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms
Pages	1319-1328
Number of pages	10
ISBN (Electronic)	978-1-61197-340-2
DOIs	https://doi.org/10.1137/1.9781611973402.97
Publication status	Published - 2014

Access to Document

10.1137/1.9781611973402.97

Chen Diakononikolas ET AL 2014 The Complexity of optimal multidimensional pricingAccepted author manuscript, 349 KB

http://epubs.siam.org/doi/abs/10.1137/1.9781611973402.97

Cite this

@inproceedings{692fb001d602470687bde82b060ec7d2,

title = "The Complexity of Optimal Multidimensional Pricing",

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.",

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

year = "2014",

doi = "10.1137/1.9781611973402.97",

language = "English",

isbn = "978-1-61197-338-9",

pages = "1319--1328",

booktitle = "Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms",

}

TY - GEN

T1 - The Complexity of Optimal Multidimensional Pricing

AU - Diakonikolas, Ilias

AU - Paparas, Dimitris

AU - Yannakakis, Mihalis

AU - Chen, Xi

AU - Sun, Xiaorui

PY - 2014

Y1 - 2014

N2 - 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.

AB - 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.

U2 - 10.1137/1.9781611973402.97

DO - 10.1137/1.9781611973402.97

M3 - Conference contribution

SN - 978-1-61197-338-9

SP - 1319

EP - 1328

BT - Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms

ER -

The Complexity of Optimal Multidimensional Pricing

Abstract

Access to Document

Fingerprint

Cite this