Ergodicity conditions for zero-sum games

Marianne Akian 1, 2 Stephane Gaubert 1, 2 Antoine Hochart 1, 2
2 MAXPLUS - Max-plus algebras and mathematics of decision
CMAP - Centre de Mathématiques Appliquées - Ecole Polytechnique, Inria Saclay - Ile de France, X - École polytechnique, CNRS - Centre National de la Recherche Scientifique : UMR
Abstract : A basic question for zero-sum repeated games consists in determining whether the mean payoff per time unit is independent of the initial state. In the special case of "zero-player" games, i.e., of Markov chains equipped with additive functionals, the answer is provided by the mean ergodic theorem. We generalize this result to repeated games. We show that the mean payoff is independent of the initial state for all state-dependent perturbations of the rewards if and only if an ergodicity condition is verified. The latter is characterized by the uniqueness modulo constants of non-linear harmonic functions (fixed point of the recession operator of the Shapley operator), or, in the special case of stochastic games with finite action spaces and perfect information, by a reachability condition involving conjugated subsets of states in directed hypergraphs. We show that the ergodicity condition for games only depend on the support of the transition probability, and that it can be checked in polynomial time when the number of states is fixed.
Type de document :
Article dans une revue
Discrete and Continuous Dynamical Systems - Series A, American Institute of Mathematical Sciences, 2015, Special issue on optimal control and related fields, 35 (9), pp.31. 〈10.3934/dcds.2015.35.3901〉
Liste complète des métadonnées

https://hal.inria.fr/hal-01096206
Contributeur : Marianne Akian <>
Soumis le : mercredi 17 décembre 2014 - 04:53:39
Dernière modification le : jeudi 10 mai 2018 - 02:05:57

Lien texte intégral

Identifiants

Citation

Marianne Akian, Stephane Gaubert, Antoine Hochart. Ergodicity conditions for zero-sum games. Discrete and Continuous Dynamical Systems - Series A, American Institute of Mathematical Sciences, 2015, Special issue on optimal control and related fields, 35 (9), pp.31. 〈10.3934/dcds.2015.35.3901〉. 〈hal-01096206〉

Partager

Métriques

Consultations de la notice

518