The Truth Behind the Myth of the Folk Theorem

Joseph Y. Halpern, Rafael Pass, Lior Seeman

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 some standard cryptographic hardness assumptions (the existence of public-key encryption), 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. As Nash equilibrium is a weak solution concept for extensive form games, we additionally define and study an appropriate notion of a subgame-perfect equilibrium for computationally bounded players, and show how to efficiently find such an equilibrium in repeated games (again, making standard cryptographic hardness assumptions).

Knowledge Graph



Sign up or login to leave a comment