The myth of the Folk Theorem

• 成果类型: Article
• 署名作者: Borgs, Christian; Chayes, Jennifer; Immorlica, Nicole; Kalai, Adam Tauman; Mirrokni, Vahab; Papadimitriou, Christos
• 署名单位: Microsoft; Northwestern University; University of California System; University of California Berkeley
• 刊物名称: GAMES AND ECONOMIC BEHAVIOR
• ISSN/ISSBN: 0899-8256
• DOI: 10.1016/j.geb.2009.04.016
• 发表日期: 2010
• 页码: 34-43
• 关键词: Repeated games; Computable general equilibrium models

摘要

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; Chen et al., 2007), this gives our main result: the problem of finding an (epsilon) Nash equilibrium in a given n x n x n game (even when all payoffs are in {-1, 0, 1}) is PPAD-hard (under randomized reductions). (C) 2009 Elsevier Inc. All rights reserved.