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.

## 3 comments

September 12, 2010 at 4:25 pm

ThorstenThis result crucially uses the fact that players cannot coordinate, even as a threat to “punish” players deviating from an equilibrium path. If players were allowed to coordinate (even only in the punishment phase of a repeated game equilibrium), it would be possible to compute the individually rational level of a player by imagining his opponents to be all controlled by a single adversary, and reducing to the two player case.

September 13, 2010 at 12:04 am

SpyrosThe tractability of “correlated threat points” and therefore the corresponding individually rational strategies for the players, has also been mentioned in a paper of Kontogiannis and Spirakis in WINE 2008, a little later than the paper of Borgs et al. in FOCS 2008.

For those interested, the reference is the following (DBLP entry):

Spyros C. Kontogiannis, Paul G. Spirakis: Equilibrium Points in Fear of Correlated Threats. WINE 2008: 210-221

September 15, 2010 at 1:38 pm

ItaiMy understanding is that the problem of finding a Nash equilibrium in which both players get non-negative payoffs is NP-hard, whereas the problem of finding any Nash equilibrium (no restriction on payoffs) is PPAD-complete. These are distinct complexity concepts.