Pricing randomized allocations

Patrick Briest, Shuchi Chawla, Robert Kleinberg, S. Matthew Weinberg

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

60 Scopus citations


Randomized mechanisms, which map a set of bids to a probability distribution over outcomes rather than a single outcome, are an important but ill-understood area of computational mechanism design. We investigate the role of randomized outcomes (henceforth, "lotteries") in the context of a fundamental and archetypical multi-parameter mechanism design problem: selling heterogeneous items to unit-demand bidders. To what extent can a seller improve her revenue by pricing lotteries rather than items, and does this modification of the problem affect its computational tractability? Our results show that the answers to these questions hinge on whether consumers can purchase only one lottery (the buy-one model) or purchase any set of lotteries and receive an independent sample from each (the buy-many model). In the buy-one model, there is a polynomial-time algorithm to compute the revenue-maximizing envy-free prices (thus overcoming the inapproximability of the corresponding item pricing problem) and the revenue of the optimal lottery system can exceed the revenue of the optimal item pricing by an unbounded factor as long as the number of item types is at least 4. In the buy-many model with n item types, the profit achieved by lottery pricing can exceed item pricing by a factor of Θ(log n) but not more, and optimal lottery pricing cannot be approximated within a factor of O(nε) for some ε > 0, unless NP ⊆ ∩δ>0 BPTIME(2O(nδ)). Our lower bounds rely on a mixture of geometric and algebraic techniques, whereas the upper bounds use a novel rounding scheme to transform a mechanism with randomized outcomes into one with deterministic outcomes while losing only a bounded amount of revenue.

Original languageEnglish (US)
Title of host publicationProceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms
PublisherAssociation for Computing Machinery (ACM)
Number of pages13
ISBN (Print)9780898717013
StatePublished - 2010
Externally publishedYes
Event21st Annual ACM-SIAM Symposium on Discrete Algorithms - Austin, TX, United States
Duration: Jan 17 2010Jan 19 2010

Publication series

NameProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms


Other21st Annual ACM-SIAM Symposium on Discrete Algorithms
Country/TerritoryUnited States
CityAustin, TX

All Science Journal Classification (ASJC) codes

  • Software
  • General Mathematics


Dive into the research topics of 'Pricing randomized allocations'. Together they form a unique fingerprint.

Cite this