The folk theorem 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 (epsilon) Nash equilibrium for a three-player infinitely-repeated game is computationally intractable (even when all payoffs are in {-1,0,-1}), unless all of PPAD ... more >>>