Pricing Randomized Allocations - Computer Science > Computer Science and Game TheoryReport as inadecuate

Pricing Randomized Allocations - Computer Science > Computer Science and Game Theory - Download this document for free, or read online. Document in PDF available to download.

Abstract: Randomized mechanisms, which map a set of bids to a probability distributionover outcomes rather than a single outcome, are an important but ill-understoodarea of computational mechanism design. We investigate the role of randomizedoutcomes henceforth -lotteries- in the context of a fundamental andarchetypical multi-parameter mechanism design problem: selling heterogeneousitems to unit-demand bidders. To what extent can a seller improve her revenueby pricing lotteries rather than items, and does this modification of theproblem affect its computational tractability? Our results show that theanswers to these questions hinge on whether consumers can purchase only onelottery the buy-one model or purchase any set of lotteries and receive anindependent sample from each the buy-many model. In the buy-one model, thereis a polynomial-time algorithm to compute the revenue-maximizing envy-freeprices thus overcoming the inapproximability of the corresponding item pricingproblem and the revenue of the optimal lottery system can exceed the revenueof the optimal item pricing by an unbounded factor as long as the number ofitem types exceeds 4. In the buy-many model with n item types, the profitachieved by lottery pricing can exceed item pricing by a factor of Olog n butnot more, and optimal lottery pricing cannot be approximated within a factor ofOn^eps for some eps>0, unless NP has subexponential-time randomizedalgorithms. Our lower bounds rely on a mixture of geometric and algebraictechniques, whereas the upper bounds use a novel rounding scheme to transform amechanism with randomized outcomes into one with deterministic outcomes whilelosing only a bounded amount of revenue.

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



Related documents