Premium
Algorithms for Stochastic Games With Perfect Monitoring
Author(s) -
Abreu Dilip,
Brooks Benjamin,
Sannikov Yuliy
Publication year - 2020
Publication title -
econometrica
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 16.7
H-Index - 199
eISSN - 1468-0262
pISSN - 0012-9682
DOI - 10.3982/ecta14357
Subject(s) - subgame perfect equilibrium , discounting , markov perfect equilibrium , mathematical economics , nash equilibrium , mathematical optimization , computer science , folk theorem , subgame , equilibrium selection , mathematics , repeated game , economics , best response , game theory , epsilon equilibrium , finance
We study the pure‐strategy subgame‐perfect Nash equilibria of stochastic games with perfect monitoring, geometric discounting, and public randomization. We develop novel algorithms for computing equilibrium payoffs, in which we combine policy iteration when incentive constraints are slack with value iteration when incentive constraints bind. We also provide software implementations of our algorithms. Preliminary simulations indicate that they are significantly more efficient than existing methods. The theoretical results that underlie the algorithms also imply bounds on the computational complexity of equilibrium payoffs when there are two players. When there are more than two players, we show by example that the number of extreme equilibrium payoffs may be countably infinite.