ICS Theory Group

CompSci 269S, Fall 2007: Theory Seminar

November 30, 2007, 1:00pm, in Bren Hall 1423

Balloon Popping With Applications to Ascending Auctions

(from FOCS 2007) authored by Nicole Immorlica, Anna R Karlin, Mohammad Mahdian, and Kunal Talwar

presented by Matt Nguyen


The authors study the power of ascending auctions in a scenario in which a seller is selling a collection of identical items to anonymous unit-demand bidders. They show that even with full knowledge of the set of bidders' private valuations for the items, if the bidders are ex-ante identical, no ascending auction can extract more than a constant times the revenue of the best fixed price scheme.

This problem is equivalent to the problem of coming up with an optimal strategy for blowing up indistinguishable balloons with known capacities in order to maximize the amount of contained air. They show that the algorithm which simply inflates all balloons to a fixed volume is close to optimal in this setting.