# The Complexity of Optimal Multidimensional Pricing

arXiv: https://arxiv.org/abs/1311.2138 · HTML: https://mlsanity.com/paper/1311.2138/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 9 Nov 2013.

## Built on by (most cited first, 1 of 1)

- [Learning to Price Homogeneous Data](https://mlsanity.com/paper/2407.05484/) (2024)

## Abstract (arXiv)

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.