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

JOURNAL OF MATHEMATICAL ANALYSIS AND APPLICATIONS

卷:457

Article

Akian, Marianne¹  Gaubert, Stephane¹  Hochart, Antoine² 

[1] Univ Paris Saclay, CMAP, INRIA, Ecole Polytech,CNRS, F-91128 Palaiseau, France

[2] Univ Toulouse I, Toulouse Sch Econ, F-31015 Toulouse, France

关键词: Zero-sum games;    Ergodic control;    Nonexpansive mappings;    Fixed point sets;    Policy iteration;   

DOI  :  10.1016/j.jmaa.2017.07.017

来源: Elsevier

【 摘 要 】

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, lambda) solution of T(u) = lambda e + u, where T : R-n -> R-n is the Shapley (or dynamic programming) operator, lambda is a scalar, e is the unit vector, and u is an element of R-n. The scalar A yields the mean payoff per time unit, and the vector u, called bias, allows one to determine optimal stationary strategies in the mean-payoff game. The existence of the eigenpair (u, lambda) 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 nonlinear Perron-Frobenius theory. As an application of our results, we obtain an explicit perturbation scheme allowing one to solve degenerate instances of stochastic games by policy iteration. (C) 2017 Elsevier Inc. All rights reserved.

【 授权许可】

Free