CS TALK
May 27, 2009
3:00 p.m., AKW 500

Speaker: Michael Schapira, Yale University & UC Berkeley
Title: The Hardness of Being Truthful

Abstract: The central problem in computational mechanism design is the tension between incentive compatibility and computational efficiency. We establish the first significant approximability gap between algorithms that are both truthful *and* computationally-efficient, and algorithms that only achieve *one* of these two desiderata. This result relies on a combination of *new techniques* from mechanism design theory, combinatorics, and complexity theory. We extend this new machinery to prove similar results for combinatorial auctions -- the paradigmatic problem in computational mechanism design. In particular, we generalize the notion of VC dimension to handle *k-tuples of disjoint sets,* and develop new technologies for lower bounding this VC-dimension. We believe that these are of independent interest.

Based on joint work with Christos Papadimitriou and Yaron Singer (2008), and on joint work with Elchanan Mossel, Christos Papadimitriou, and Yaron Singer (2009).