Corelab Seminar

Constantinos Daskalakis (MIT)
Fixed-Point Theorems, Nash Equilibria, and Harnessing Uncertainty

Recent results have shown that computing Nash equilibria is an intractable problem. It is not NP-hard, since Nash's theorem shows that a Nash equilibrium exists in every game, and this makes it unlikely that the problem is NP-hard. Instead, it is as intractable as any fixed-point computation problem in a precise technical sense. In the first part of the talk, we survey results on the complexity of the Nash equilibrium. In view of these results, the credibility of the Nash equilibrium is questioned: how do markets and players converge to equilibria, if finding them is an intractable problem? In the second part of the talk, we discuss ways to go around the computational barrier, such as looking at approximation or special cases of the problem. A particularly promising direction is to develop probabilistic tools to exploit algorithmically the uncertainty and symmetry that is inherent in certain game-theoretic settings. We present recent results in approximating equilibria of anonymous games, and optimally solving multi-dimensional pricing problems.