VC v. VCG: Inapproximability of Combinatorial Auctions via Generalizations of the VC Dimension
Michael Schapira
Yale & UC Berkeley
Date and time: Thursday February 25, 2010; 11:00 AM -- 12:00 noon.
Venue: 1000 SEO

Abstract:
The existence of incentive-compatible computationally-efficient protocols for combinatorial auctions with decent approximation ratios is the paradigmatic problem in computational mechanism design. It is believed that in many cases good approximations for combinatorial auctions may be unattainable due to an inherent clash between truthfulness and computational efficiency. However, to date, researchers lack the machinery to prove such results. We present a new approach that we believe holds great promise for making progress on this important problem. We develop new technologies for lower bounding the VC-dimension of k-tuples of disjoint sets. We apply this machinery to prove the first computational-complexity hardness results for truthful mechanisms for combinatorial auctions.

Joint work with Elchanan Mossel, Christos Papadimitriou and Yaron Singer

About the speaker:
Michael Schapira is a postdoc at Yale University and UC Berkeley, co-advised by Prof. Joan Feigenbaum and Prof. Scott Shenker. He completed his Ph.D. at the Hebrew University of Jerusalem under the supervision of Prof. Noam Nisan. His main research interests are twofold. In the area of algorithmic foundations of networking, he is interested in the design and analysis of Internet protocols focusing on understanding existing Internet protocols and the fundamental trade-offs that should guide the design of the future Internet, and fixing today's protocols and devising long-term solutions that take us beyond what incremental fixes to these protocols can achieve. In algorithmic game theory. he is interested in the interface of computer science, game theory and economic theory exploring the possibility/impossibility borderline of incentive-compatible computation.