The Myth of the Folk Theorem

Christian Borgs, Jennifer Chayes, Nicole Immorlica, Adam Kalai, Vahab Mirrokni, Christos Papadimitriou

STOC '08 Proceedings of the fortieth annual ACM symposium on Theory of computing |

Published by ACM Press

View Publication

A well-known result in game theory known as “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 (approximate) 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, for which PPAD-hardness is known (Daskalakis, Goldberg and Papadimitriou, 2006; Chen, Deng and Teng, 2006; Chen, Teng and Valiant, 2007). This also explains why no computationally-efficient learning dynamics, such as the “no regret” algorithms, can be rational (in general games with three or more players) in the sense that, when one’s opponents use such a strategy, it is not in general a best reply to follow suit.