Multigrid methods for two-player zero-sum stochastic games

We present a fast numerical algorithm for large scale zero-sum stochastic games with perfect information, which combines policy iteration and algebraic multigrid methods. This algorithm can be applied either to a true finite state space zero-sum two-player game or to the discretization of an Isaacs equation. We present numerical tests on discretizations of Isaacs equations or variational inequalities. We also present a full multilevel policy iteration, similar to full multigrid algorithm (FMG), which allows one to improve substantially the computation time for solving some variational inequalities. Copyright (C) 2012 John Wiley & Sons, Ltd.