CSAIL Event Calendar: Previous Series

Monopoly Pricing, Profit Extraction and Popping Balloons

Speaker: Nicole Immorlica , Microsoft Research
Date: April 6 2006
Time: 5:15PM to 6:30PM
Location: 32-G575
Host: Piotr Indyk, MIT CSAIL

A horde of caffeine-starved grad students storm Toscanini's yearning for a latte. Each grad student i would give anything for a latte, but has just v_i dollars in his or her pocket. The cashier miraculously knows this set of values {v_i} but, since grad students are indistinguishable, is unable to determine who holds which amount of money. We study how much money the cashier can extort from the grad students by reducing our problem to an interesting algorithmic question regarding how to blow up seemingly identical balloons with varying capacities in order to maximize the amount of contained air.

Our work is motivated by the question of how much surplus a monopolist can extract through the use of price discrimination. If the monopolist has complete information about the buyers' types, he can clearly extract the full surplus of the market by charging each buyer his valuation. When the monopolist has only distribution information about the types, as in our setting, a uniform pricing mechanism extracts max_i iv_i (where v_i are sorted in decreasing order). We show that the monopolist can never extract significantly more revenue than the optimal uniform pricing scheme using a suitably general class of mechanisms.

(Joint work with Anna Karlin, Mohammad Mahdian, and Kunal Talwar)

See other events that are part of Algorithms and Complexity Spring 2006

See other events happening in April 2006