  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 exceeds 4. In the buy-many model with n item types, the profit
achieved by lottery pricing can exceed item pricing by a factor of O(log n) but
not more, and optimal lottery pricing cannot be approximated within a factor of
O(n^eps) for some eps>0, unless NP has subexponential-time randomized
algorithms. 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.
