عنوان انگلیسی مقاله:
The truth behind the myth of the Folk theorem
ترجمه فارسی عنوان مقاله:
حقیقت پشت اسطوره قضیه Folk
Sciencedirect - Elsevier - Games and Economic Behavior, 117 (2019) 479–498: 10:1016/j:geb:2019:04:008
Joseph Y.Halpern, RafaelPass, LiorSeeman∗
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