Econometrica

Journal Of The Econometric Society

An International Society for the Advancement of Economic
Theory in its Relation to Statistics and Mathematics

Edited by: Guido W. Imbens • Print ISSN: 0012-9682 • Online ISSN: 1468-0262

Econometrica: Jul, 2020, Volume 88, Issue 4

Algorithms for Stochastic Games with Perfect Monitoring

https://doi.org/10.3982/ECTA14357
p. 1661-1695

Dilip Abreu, Benjamin Brooks, Yuliy Sannikov

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.


Log In To View Full Content

Supplemental Material

Supplement to "Algorithms for Stochastic Games with Perfect Monitoring"

This appendix contains material not found within the manuscript.