Algorithms for Stochastic Games with Perfect Monitoring

We study the pure-strategy subgame-perfect Nash equilibria of stochastic games with perfect monitoring, geometric discounting, and public randomization. Novel algorithms are developed for calculating the discounted payoffs that can be attained in equilibrium. We also provide implementations of our algorithms. Preliminary simulations indicate that they are significantly more efficient than existing methods. The theoretical results that underlie the algorithms also yield a bound on the number of extremal equilibrium payoffs and on the computational complexity of equilibrium payoffs when there are two players