@inproceedings{borgs2008the,
author = {Borgs, Christian and Chayes, Jennifer and Immorlica, Nicole and Kalai, Adam Tauman and Mirrokni, Vahab and Papadimitriou, Christos},
title = {The Myth of the Folk Theorem},
booktitle = {STOC '08 Proceedings of the fortieth annual ACM symposium on Theory of computing},
year = {2008},
month = {May},
abstract = {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.},
publisher = {ACM Press},
url = {https://www.microsoft.com/en-us/research/publication/myth-folk-theorem/},
pages = {365-372},
isbn = {978-1-60558-047-0},
edition = {STOC '08 Proceedings of the fortieth annual ACM symposium on Theory of computing},
}