 The truth behind the myth of the Folk theoremJoseph Halpern (), Rafael Pass and Lior Seeman Games and Economic Behavior, 2019, vol. 117, issue C, 479-498 Abstract: We study the problem of computing an ϵ-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). Keywords: Equilibrium Computation; Folk theorem; Repeated games; Bounded rationality (search for similar items in EconPapers) Downloads: (external link) Related works: Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text Persistent link: https://EconPapers.repec.org/RePEc:eee:gamebe:v:117:y:2019:i:c:p:479-498 DOI: 10.1016/j.geb.2019.04.008 Access Statistics for this article Games and Economic Behavior is currently edited by E. Kalai More articles in Games and Economic Behavior from Elsevier |
Is your work missing from RePEc? Here is how to contribute.
Questions or problems? Check the EconPapers FAQ or send mail to .
EconPapers is hosted by the
School of Business at Örebro University.