The Complexity of Optimal Multidimensional Pricing.

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

The Complexity of Optimal Multidimensional Pricing.

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

Research output: Working paper

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
Publisher	Computing Research Repository (CoRR)
Number of pages	30
Volume	abs/1311.2138
Publication status	Published - 2013

Access to Document

http://arxiv.org/abs/1311.2138

Cite this

@techreport{e8bc1369f74449e4b5dfef6a06f039d9,

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 = "Xi Chen and Ilias Diakonikolas and Dimitris Paparas and Xiaorui Sun and Mihalis Yannakakis",

year = "2013",

language = "English",

volume = "abs/1311.2138",

publisher = "Computing Research Repository (CoRR)",

type = "WorkingPaper",

institution = "Computing Research Repository (CoRR)",

}

TY - UNPB

T1 - The Complexity of Optimal Multidimensional Pricing.

AU - Chen, Xi

AU - Diakonikolas, Ilias

AU - Paparas, Dimitris

AU - Sun, Xiaorui

AU - Yannakakis, Mihalis

PY - 2013

Y1 - 2013

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.

M3 - Working paper

VL - abs/1311.2138

BT - The Complexity of Optimal Multidimensional Pricing.

PB - Computing Research Repository (CoRR)

ER -

The Complexity of Optimal Multidimensional Pricing.

Abstract

Access to Document

Fingerprint

Cite this