Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > CHRISTIAN BORGS:
All reports by Author Christian Borgs:

TR07-082 | 27th July 2007
Christian Borgs, Jennifer Chayes, Nicole Immorlica, Adam Kalai, Vahab Mirrokni, Christos H. Papadimitriou

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




ISSN 1433-8092 | Imprint