Every game in strategic form (a matrix game) has an equilibrium in mixed strategies. But finding an equilibrium in a specific game is a difficult problem. Gilboa and Zemel proved that this is a computationally difficult task: it is NP-hard to determine whether a specific game has a Nash equilibrium where both players gets non-negative payoffs. Computer scientists, who adore giving names to classes of problems, call the class of problems that are computationally equivalent to this problem PPAD.

The Folk Theorem tells us that the set of Nash equilibria of a repeated game is the set of feasible and individually rational payoffs. It therefore seems that this problem is simple. Indeed, the set of feasible payoffs can be easily determined from the payoff matrix, and the individually rational level of a player in a two-player game can be found using a linear program. The catch is that this is true only for two-player games. Apparently the determination of the min-max value of a player in a three-player game is difficult. In fact, a recent paper by Christian Borges, Jennifer Chayes, Nicole Immorlica, Adam Tauman Kalai, Vahab Mirrokni and Christos Papadimitriou shows that this problem is PPAD: it is as hard to calculate the individually rational level of a player in a three-player game as it is to find an equilibrium in a two-player game. So finding equilibria in repeated games is neither easier nor harder than finding equilibria in one-shot game. The six authors ruined our belief that repeated games are easy to play. Thanks guys.

And thanks to Jason Hartline who brought this paper to my attention.