Constantinos Daskalakis

X-Window Consortium Associate Professor, EECS, MIT

Game Theory and Computational Complexity

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.