Theory Lunch Seminar

Seminars
Computer Science Department
Carnegie Mellon University
Draft Auctions
Wednesday, November 20, 2013 - 12:00pm to 1:00pm
6115 
Gates&Hillman Centers
Abstract:

We introduce draft auctions, which is a sequential auction format where at each iteration players bid for the right to buy items at a fixed price. We show that draft auctions offer an exponential improvement in social welfare at equilibrium over sequential item auctions where predetermined items are auctioned at each time step. Specifically, we show that for any subadditive valuation the social welfare at equilibrium is an O(log^2(m)) approximation to the optimal social welfare, where m is the number of items. We also provide tighter approximation results for several subclasses. Our welfare guarantees hold for Bayes-Nash equilibria and for no-regret learning outcomes,  via the smooth-mechanism framework. Of independent interest, our techniques show that in a combinatorial auction setting, efficiency guarantees of a mechanism via smoothness for a very restricted class of cardinality valuations, extend with a small degradation, to subadditive valuations, the largest complement-free class of valuations. Variants of draft auctions have been used in practice and have been experimentally shown to outperform other auctions. Our results provide a theoretical justification.

Joint work with Nikhil Devanur and Vasilis Syrgkanis

Keywords:
For More Information, Please Contact:

euiwoonl [atsymbol] cs.cmu.edu