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.