Spring 2010 Seminar Series

DATE: April 29th
LOCATION: E51-376
TIME: 4:15pm
Reception immediately following in the ORC Conference Room, E40-106

SPEAKER:
Robert Kleinberg

TITLE
Pricing Randomized Allocations

ABSTRACT
We compare the revenue properties of selling strategies in which the seller is allowed to set prices on randomized allocations (henceforth, "lotteries") versus those in which only deterministic allocations can be sold. It is well known to economists that optimal pricing for single-parameter consumers does not require selling lotteries, but this ceases to be the case when one considers multi-parameter problems. To what extent can a seller improve revenue by pricing lotteries rather than items, and does this modification of the problem affect its computational tractability? We investigate these questions in the context of an archetypical profit maximization problem: selling heterogeneous items in unlimited supply to unit-demand bidders. The answers 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, lotteries can improve revenue by an unbounded factor, and an optimal lottery pricing system can be computed in polynomial time despite the inapproximability of the corresponding item pricing problem. In the buy-many model, lotteries improve profit by only a logarithmic factor and the optimal pricing problem is inapproximable unless NP has subexponential-time randomized algorithms.

 

This is joint work with Patrick Briest, Shuchi Chawla, and Matt Weinberg.