Title: The Power of VCG: On Algorithms that are Maximal In Range
Shahar Dobzinski
Hebrew University of Jerusalem
Department of Computer Science
Abstract:
Consider the following simple type of approximation algorithms: limit the set of possible outcomes, and completely optimize over the restricted subrange. In this talk we will study the power of this type of these algorithms in two settings: multi-unit auctions, and combinatorial auctions with subadditive bidders.
From a game-theoretic point of view, our results provide a characterization of the power of the main positive result of mechanism design: the VCG mechanism. Another motivation is that our lower bounds might be a crucial step towards setting lower bounds on the power of polynomial time truthful mechanisms. We will explain and discuss these issues.
Joint work with Noam Nisan.