Abstract:
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).