Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR07-082 | 27th July 2007 00:00

The Myth of the Folk Theorem



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

ISSN 1433-8092 | Imprint