Title: Polyhedral Clinching Auctions and the AdWords Polytope
Speaker: Gagan Goel, Google Research
Date: Wednesday, February 29, 2012 11:00-12:00pm
Location: DIMACS Center, CoRE Bldg, Room 431, Rutgers University, Busch Campus, Piscataway, NJ
Abstract:
Motivated by ad auctions, a mechanism design problem that has come to the fore is that of designing auctions in the presence of budget-constrained bidders. Recent results in this direction extend Ausubel's clinching auction to give Pareto-optimal auctions for specific allocation scenarios such as multi-unit supply (Dobzinski et al) and certain matching markets (Fiat et al). A natural question one must ask is: For what all allocation scenarios can we design a Pareto-optimal auction in the presence of budget-constrained bidders? In this work, we give a Pareto-optimal auction for any allocation scenario that can be described using a polymatroid. Our auction extends Ausubel's clinching auction. We also show that a very general model of Adwords that includes multiple slots and multiple keywords can be described using a polymatroid. Finally we give some impossibility results for more general allocation scenarios. As a byproduct, we also get an impossibility result for multi-unit auctions with decreasing marginal utilities, thus resolving a conjecture by Ausubel stating that a variation of the clinching auction should work for this setting. This conjecture was later reinforced by Dobzinski et al.
This is a joint work with Vahab Mirrokni and Renato Paes Leme.