Renato Paes Leme
Abstract:
A central issue in applying auction theory in practice is the problem of dealing with budget-constrained agents. Toward this goal and motivated by AdWords auctions, we present an auction for {\em polymatroidal} constraints that is polynomial-time computable, incentive-compatible, individually-rational, and Pareto-optimal, while respecting budgets. Our auction employs a novel clinching technique with a clean geometric description and only needs an oracle access to the submodular function defining the polymatroid. As a result, this auction not only simplifies and generalizes all previous results, it applies to several new applications including AdWords Auctions, bandwidth markets, and video on demand. In particular, our characterization of the AdWords auction as polymatroidal constraints might be of independent interest. This allows us to design the first mechanism for Ad Auctions taking into account simultaneously budgets, multiple keywords and multiple slots.
In order to extend this result to more general polyhedral constraints, we prove several structural properties of Pareto-optimal truthful auctions for polyhedral environments and present a characterization of such auctions. This characterization results in various impossibly results and one positive result: we illustrate simple polytope constraints for which it is impossible to achieve a truthful Pareto-optimal auction even for two players. Moreover, as a byproduct of this characterization, we get an impossibility result for multi-unit auctions with decreasing marginal utilities.
http://arxiv.org/abs/1201.0404
This is a joint work with Gagan Goel and Vahab Mirrokni.