The truth behind the myth of the Folk theorem

• 成果类型: Article
• 署名作者: Halpern, Joseph Y.; Pass, Rafael; Seeman, Lior
• 署名单位: Cornell University
• 刊物名称: GAMES AND ECONOMIC BEHAVIOR
• ISSN/ISSBN: 0899-8256
• DOI: 10.1016/j.geb.2019.04.008
• 发表日期: 2019
• 页码: 479-498
• 关键词: Equilibrium Computation; folk theorem; repeated games; bounded rationality

摘要

We study the problem of computing an epsilon-Nash equilibrium in repeated games. Earlier work by Borgs et al. (2010) suggests that this problem is intractable. We show that if we make a slight change to their model-modeling the players as polynomial-time Turing machines that maintain state- and make a standard cryptographic assumption (that public-key cryptography can carried out), the problem can actually be solved in polynomial time. Our algorithm works not only for games with a finite number of players, but also for constant-degree graphical games (where, roughly speaking, which players' actions a given player's utility depends on are characterized by a graph, typically of bounded degree). As Nash equilibrium is a weak solution concept for extensive-form games, we additionally define and study an appropriate notion of subgame-perfect equilibrium for computationally bounded players, and show how to efficiently find such an equilibrium in repeated games (again, assuming public-key cryptography). (C) 2019 Published by Elsevier Inc.