TY - GEN

T1 - Pricing randomized allocations

AU - Briest, Patrick

AU - Chawla, Shuchi

AU - Kleinberg, Robert

AU - Weinberg, S. Matthew

PY - 2010

Y1 - 2010

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=77951686246&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=77951686246&partnerID=8YFLogxK

U2 - 10.1137/1.9781611973075.49

DO - 10.1137/1.9781611973075.49

M3 - Conference contribution

AN - SCOPUS:77951686246

SN - 9780898717013

T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

SP - 585

EP - 597

BT - Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms

PB - Association for Computing Machinery (ACM)

T2 - 21st Annual ACM-SIAM Symposium on Discrete Algorithms

Y2 - 17 January 2010 through 19 January 2010

ER -