loading...
Balloon Popping With Applications to Ascending Auctions
Providence, Rhode Island October 21-October 23
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/FOCS.2007.6948th Annual IEEE Symposium on Foundat ...
 This Article 
 
PDF
HTML
 
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   

We 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. We 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. We show that the algorithm which simply inflates all balloons to a fixed volume is close to optimal in this setting.

Citation:
Nicole Immorlica, Anna R. Karlin, Mohammad Mahdian, Kunal Talwar, "Balloon Popping With Applications to Ascending Auctions," focs, pp.104-112, 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS'07), 2007
Usage of this product signifies your acceptance of the Terms of Use.