Applied Math Colloquium - Friday, Nov. 20, 2009
Bobby Kleinberg, Computer Science, Cornell
3:30 PM at 655 Rhodes Hall
Title: Pricing Lotteries
Abstract:
A seller of digital goods may wish to set prices to maximize profit, given a model for the distribution of consumer characteristics. We study the use of randomized outcomes (henceforth, "lotteries") in such pricing problems. It is well known to economists that optimal mechanisms for single-parameter agents do not randomize over outcomes, 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 complexity? 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, some of which are quite surprising, 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).
This is joint work with Patrick Briest, Shuchi Chawla, and Matt Weinberg.