Skip to Main content Skip to Navigation
Journal articles

Multigrid methods for two-player zero-sum stochastic games

Marianne Akian 1, 2 Sylvie Detournay 1, 2
1 MAXPLUS - Max-plus algebras and mathematics of decision
CMAP - Centre de Mathématiques Appliquées - Ecole Polytechnique, Inria Saclay - Ile de France
Abstract : 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 multi-level policy iteration, similar to FMG, which allows to improve substantially the computation time for solving some variational inequalities.
Document type :
Journal articles
Complete list of metadata

https://hal.inria.fr/hal-00773036
Contributor : Marianne Akian <>
Submitted on : Friday, January 11, 2013 - 2:52:24 PM
Last modification on : Thursday, March 5, 2020 - 6:27:37 PM

Links full text

Identifiers

Collections

Citation

Marianne Akian, Sylvie Detournay. Multigrid methods for two-player zero-sum stochastic games. Numerical Linear Algebra with Applications, Wiley, 2012, 19 (2), pp.313--342. ⟨10.1002/nla.1815⟩. ⟨hal-00773036⟩

Share

Metrics

Record views

363