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 can be solved in randomized
polynomial time. This is done by showing that finding Nash
equilibria of (k+1)-player infinitely-repeated games is as hard
as finding Nash equilibria of k-player one-shot games, where
PPAD-hardness is known (Daskalakis, Goldberg and Papadimitriou,
2006; Chen, Deng and Tang, 2006; Chen, Tang and Valiant, 2007).
This also shows that no computationally-efficient learning
dynamics, e.g., "no regret" algorithms, are RATIONAL in
general games with three or more players. In other words, when
one's opponents use such a strategy, it is not in general a best
reply to follow suit (under the same computational assumption).