The complexity of optimal multidimensional pricing

DOI10.1137/1.9781611973402.97MaRDI QIDQ5384059zbMATH OpenOpenAlexFDO

Authors Xi Chen, Ilias Diakonikolas, Xiaorui Sun, Mihalis Yannakakis, D. Paparas

Publication date 20 June 2019

Published in Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1311.2138

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Microeconomic theory (price theory and economic markets) (91B24) Auctions, bargaining, bidding and selling, and other market models (91B26)

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.

Recommendations

• The complexity of optimal multidimensional pricing for a unit-demand buyer
• On the complexity of simple and optimal deterministic mechanisms for an additive buyer
• The complexity of optimal mechanism design
• Extreme value theorems for optimal multidimensional pricing
• Extreme-value theorems for optimal multidimensional pricing

Cited in

(14)

• The complexity of optimal multidimensional pricing for a unit-demand buyer
• Bargaining mechanisms for one-way games
• Robust multidimensional pricing: separation without regret
• Multidimensional bargaining and posted prices
• Pricing lotteries
• Extreme value theorems for optimal multidimensional pricing
• On the complexity of simple and optimal deterministic mechanisms for an additive buyer
• On the Complexity of Optimal Lottery Pricing and Randomized Mechanisms for a Unit-Demand Buyer
• The pricing problem. Part II: Computational complexity
• Algorithms and Data Structures
• Extreme-value theorems for optimal multidimensional pricing
• On the complexity of a bundle pricing problem
• Multivariate decisions with unknown price vector
• A pricing problem under Monge property

This page was built for publication: The complexity of optimal multidimensional pricing

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5384059)