Generic uniqueness of the bias vector of finite stochastic games with perfect information

Abstract : Mean-payoff zero-sum stochastic 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)=λe+u, where T:Rn→Rn is the Shapley (or dynamic programming) operator, λ is a scalar, e 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 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 (or tropical) algebra and nonlinear Perron-Frobenius theory. As an application of our results, we obtain a perturbation scheme allowing one to solve degenerate instances of stochastic games by policy iteration.
Type de document :
Article dans une revue
Journal of Mathematical Analysis and Applications, Elsevier, 2018, 457, pp.1038-1064. 〈https://www.journals.elsevier.com/journal-of-mathematical-analysis-and-applications〉. 〈10.1016/j.jmaa.2017.07.017〉
Liste complète des métadonnées

https://hal.inria.fr/hal-01425543
Contributeur : Marianne Akian <>
Soumis le : mardi 3 janvier 2017 - 16:02:26
Dernière modification le : mardi 18 décembre 2018 - 10:56:29

Lien texte intégral

Identifiants

Citation

Marianne Akian, Stéphane Gaubert, Antoine Hochart. Generic uniqueness of the bias vector of finite stochastic games with perfect information. Journal of Mathematical Analysis and Applications, Elsevier, 2018, 457, pp.1038-1064. 〈https://www.journals.elsevier.com/journal-of-mathematical-analysis-and-applications〉. 〈10.1016/j.jmaa.2017.07.017〉. 〈hal-01425543〉

Partager

Métriques

Consultations de la notice

441