February 23, 2010: Seminar - Michael Schapira: "VC v. VCG: Inapproximability of Combinatorial Auctions via Generalizations of the VC Dimension"

Seminar Announcement

VC v. VCG: Inapproximability of Combinatorial Auctions via Generalizations of the VC Dimension

Michael Schapira
Yale & UC Berkeley
Thursday February 25
11:00 AM, 1000 SEO


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.

Brief Bio:

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.

Host: Prof. Bhaskar DasGupta

Copyright 2016 The Board of Trustees
of the University of Illinois.webmaster@cs.uic.edu
Helping Women Faculty Advance
Funded by NSF