Skip to content. Skip to navigation
McGill Home SOCS Home
Personal tools
You are here: Home Announcements and Events Seminars profile

Seminars
Fall 2013 Schedule
Winter 2014 Schedule
Archive


         
     
 
2013/02/15, MC103, 14:30 - 15:30

Game Theory and Computational Complexity
Costis Daskalakis , Massachusetts Institute of Technology

Abstract:

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.

Biography of Speaker:

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.