Game Theory and Computational Complexity
Costis Daskalakis - Massachusetts Institute of Technology
Feb. 15, 2013, 1 p.m. - Feb. 15, 2013, 2 p.m.
MC103
Can Game Theory predict rational behavior? In two-player zero-sum games the Nash equilibrium makes rather convincing predictions, which can also be computed efficiently with linear programming. We show, however, that the Nash equilibrium is in general intractable, casting doubt on whether it always truly captures the behavior of computationally bounded agents. We also discuss ways to overcome this intractability barrier, including approximation, dynamics, and studying well-behaved families of games. We conclude with a broader discussion of the interactions of Game Theory with the Theory of Computation. Constantinos Daskalakis is the x-window consortium associate professor of computer science at MIT. He holds a diploma in electrical and computer engineering from the National Technical University of Athens, and a Ph.D. in electrical engineering and computer sciences from UC-Berkeley. His research interests lie in theoretical computer science and applied probability with a focus on the computational aspects of the Internet, online markets and social networks. Daskalakis has been honored with the 2007 Microsoft Graduate Research Fellowship, the 2008 ACM Doctoral Dissertation Award, the Game Theory and Computer Science Prize from the Game Theory Society, the 2010 Sloan Fellowship in Computer Science, the 2011 SIAM Outstanding Paper Prize, the 2011 Ruth and Joel Spira Award for Distinguished Teaching, and the 2012 Microsoft Research Faculty Fellowship.
