Publication 2004-003

Consider the problem of value interation for solving Markov stochastic games. One simply iterates backwards, via a Jacobi-like procedure. The convergence of the Gauss-Seidel form of this procedure is shown for both the discounted and ergodic cost problems, under appropriate conditions, with extensions to problems where one stops when a boundary is hit or if any one of the players chooses to stop, with associated costs. Generally, the Gauss-Seidel procedure accelerates convergence.

Key words. Stochastic games, Markov games, Gauss-Seidel procedure, numerical algorithms.