On the Complexity of Optimal Lottery Pricing and Randomized Mechanisms

Xi Chen, I. Diakonikolas, A. Orfanou, D. Paparas, Xiaorui Sun, M. Yannakakis

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract / Description of output

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 languageEnglish
Title of host publicationFoundations of Computer Science (FOCS), 2015 IEEE 56th Annual Symposium on
PublisherInstitute of Electrical and Electronics Engineers (IEEE)
Number of pages16
ISBN (Print)978-1-4673-8191-8
Publication statusPublished - 1 Oct 2015

Keywords / Materials (for Non-textual outputs)

  • 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


Dive into the research topics of 'On the Complexity of Optimal Lottery Pricing and Randomized Mechanisms'. Together they form a unique fingerprint.

Cite this