Projects per year
Abstract
We study the optimal lottery problem and the optimal mechanism design problem in the setting of a single unit-demand buyer with item values drawn from independent distributions. Optimal solutions to both problems are characterized by a linear program with exponentially many variables. For the menu size complexity of the optimal lottery problem, we present an explicit, simple instance with distributions of support size 2, and show that exponentially many lotteries are required to achieve the optimal revenue. We also show that, when distributions have support size 2 and share the same high value, the simpler scheme of item pricing can achieve the same revenue as the optimal menu of lotteries. The same holds for the case of two items with support size 2 (but not necessarily the same high value). For the computational complexity of the optimal mechanism design problem, we show that unless the polynomial-time hierarchy collapses (more exactly, PNP = P#P), there is no universal efficient randomized algorithm to implement an optimal mechanism even when distributions have support size 3.
Original language | English |
---|---|
Title of host publication | Foundations of Computer Science (FOCS), 2015 IEEE 56th Annual Symposium on |
Publisher | Institute of Electrical and Electronics Engineers (IEEE) |
Pages | 1464-1479 |
Number of pages | 16 |
ISBN (Print) | 978-1-4673-8191-8 |
DOIs | |
Publication status | Published - 1 Oct 2015 |
Keywords
- computational complexity
- linear programming
- pricing
- randomised algorithms
- linear program
- menu size complexity
- optimal lottery pricing complexity
- optimal lottery problem
- optimal mechanism design problem
- polynomial-time hierarchy collapse
- randomized mechanism
- single unit-demand buyer
- Additives
- Algorithm design and analysis
- Complexity theory
- Cost accounting
- Polynomials
- Pricing
- Standards
- Lottery pricing
- optimal mechanism design
- unit-demand buyer
Fingerprint
Dive into the research topics of 'On the Complexity of Optimal Lottery Pricing and Randomized Mechanisms'. Together they form a unique fingerprint.Projects
- 1 Finished
-
Sublinear Algorithms for Approximating Probability Distribution
Diakonikolas, I.
1/09/14 → 31/08/15
Project: Research