Generic uniqueness of the bias vector of mean-payoff 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, Polytechnique - X, CNRS - Centre National de la Recherche Scientifique : UMR
Abstract : Zero-sum mean payoff games can be studied by means of a nonlinear spectral problem. When the state space is finite, the latter consists in finding an eigenpair (u,λ) solution of T(u)=λ1+u where T:Rn→Rn is the Shapley (dynamic programming) operator, λ is a scalar, 1 is the unit vector, and u∈Rn. The scalar λ yields the mean payoff per time unit, and the vector u, called the bias, allows one to determine optimal stationary strategies. The existence of the eigenpair (u,λ) is generally related to ergodicity conditions. A basic issue is to understand for which classes of games the bias vector is unique (up to an additive constant). In this paper, we consider perfect information zero-sum stochastic games with finite state and action spaces, thinking of the transition payments as variable parameters, transition probabilities being fixed. We identify structural conditions on the support of the transition probabilities which guarantee that the spectral problem is solvable for all values of the transition payments. Then, we show that the bias vector, thought of as a function of the transition payments, is generically unique (up to an additive constant). The proof uses techniques of max-plus (tropical) algebra and nonlinear Perron-Frobenius theory.
Type de document :
Communication dans un congrès
PGMO-COPI’14, Oct 2014, Palaiseau, France. 〈http://www.fondation-hadamard.fr/pgmo-copi-14〉
Liste complète des métadonnées

https://hal.inria.fr/hal-01112285
Contributeur : Marianne Akian <>
Soumis le : lundi 2 février 2015 - 15:40:43
Dernière modification le : jeudi 11 janvier 2018 - 06:22:34

Identifiants

  • HAL Id : hal-01112285, version 1

Collections

Citation

Marianne Akian, Stephane Gaubert, Antoine Hochart. Generic uniqueness of the bias vector of mean-payoff zero-sum games. PGMO-COPI’14, Oct 2014, Palaiseau, France. 〈http://www.fondation-hadamard.fr/pgmo-copi-14〉. 〈hal-01112285〉

Partager

Métriques

Consultations de la notice

246