Algorithms and Complexity Seminar
Thursday, April 6, 2006, 4-5:15pm in 32-G575.
Monopoly pricing, profit extraction and popping balloons
Nicole Immorlica (Microsoft Research)
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)
Host: Piotr Indyk