The myth of the Folk Theorem

The Folk Theorem for repeated games suggests that finding Nash equilibria in repeated games should be easier than in one-shot games. In contrast, we show that the problem of finding any Nash equilibrium for a three-player infinitely-repeated game is as hard as it is in two-player one-shot games. More specifically, for any two-player game, we give a simple construction of a three-player game whose Nash equilibria (even under repetition) correspond to those of the one-shot two-player game. Combined with recent computational hardness results for one-shot two-player normal-form games (Daskalakis et al., 2006; Chen et al., 2006; Chen et al., 2007), this gives our main result: the problem of finding an (epsilon) Nash equilibrium in a given n×n×n game (even when all payoffs are in {−1,0,1}) is PPAD-hard (under randomized reductions).