The myth of the Folk Theorem
The Folk Theorem for repeated games 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 Nash equilibrium for a three-player infinitely-repeated game is as hard as it is in two-player one-shot games. More specifically, for any two-player game, we give a simple construction of a three-player game whose Nash equilibria (even under repetition) correspond to those of the one-shot two-player game. Combined with recent computational hardness results for one-shot two-player normal-form games ([Daskalakis et al., 2006], [Chen et al., 2006] and [Chen et al., 2007]), this gives our main result: the problem of finding an (epsilon) Nash equilibrium in a given n×n×n game (even when all payoffs are in {-1,0,1}) is PPAD-hard (under randomized reductions).
Year of publication: |
2010
|
---|---|
Authors: | Borgs, Christian ; Chayes, Jennifer ; Immorlica, Nicole ; Kalai, Adam Tauman ; Mirrokni, Vahab ; Papadimitriou, Christos |
Published in: |
Games and Economic Behavior. - Elsevier, ISSN 0899-8256. - Vol. 70.2010, 1, p. 34-43
|
Publisher: |
Elsevier |
Keywords: | Repeated games Computable general equilibrium models |
Saved in:
Online Resource
Saved in favorites
Similar items by person
-
Borgs, Christian, (2010)
-
Borgs, Christian, (2010)
-
Bargaining dynamics in exchange networks
Bayati, Mohsen, (2015)
- More ...