Monday, November 23, 2009
4:00pm

5130 Upson Hall

Abstract:

A paradigmatic problem in algorithmic mechanism design is the existence of incentive-compatible, computationally efficient mechanisms for combinatorial auctions with good approximation ratio for the social welfare.  It is common belief that there is clash between truthfulness and computational efficiency, which makes this goal unattainable.

In this talk we show some computational complexity lower bound for VCG-based auctions, an important class of truthful mechanisms.  In particular, we show that, under a broad class of valuation functions (including submodular valuations), the approximation ratio of such auctions for k bidders cannot be better than k, unless SAT can be decided by polynomially sized circuits.  This result holds for a class of randomized, truthful-in-expectation mechanisms as well.  To prove this, we developed tools on VC-dimension, which may be of independent interest.

This is joint work with Shaddin Dughmi (Stanford) and Bobby Kleinberg (Cornell).