Skip to Main content Skip to Navigation

Nonlinear Perron-Frobenius theory and mean-payoff zero-sum stochastic games

Abstract : Zero-sum stochastic games have a recursive structure encompassed in their dynamic programming operator, so-called Shapley operator. The latter is a useful tool to study the asymptotic behavior of the average payoff per time unit. Particularly, the mean payoff exists and is independent of the initial state as soon as the ergodic equation - a nonlinear eigenvalue equation involving the Shapley operator - has a solution. The solvability of the latter equation in finite dimension is a central question in nonlinear Perron-Frobenius theory, and the main focus of the present thesis. Several known classes of Shapley operators can be characterized by properties based entirely on the order structure or the metric structure of the space. We first extend this characterization to "payment-free" Shapley operators, that is, operators arising from games without stage payments. This is derived from a general minimax formula for functions homogeneous of degree one and nonexpansive with respect to a given weak Minkowski norm. Next, we address the problem of the solvability of the ergodic equation for all additive perturbations of the payment function. This problem extends the notion of ergodicity for finite Markov chains. With bounded payment function, this "ergodicity" property is characterized by the uniqueness, up to the addition by a constant, of the fixed point of a payment-free Shapley operator. We give a combinatorial solution in terms of hypergraphs to this problem, as well as other related problems of fixed-point existence, and we infer complexity results. Then, we use the theory of accretive operators to generalize the hypergraph condition to all Shapley operators, including ones for which the payment function is not bounded. Finally, we consider the problem of uniqueness, up to the addition by a constant, of the nonlinear eigenvector. We first show that uniqueness holds for a generic additive perturbation of the payments. Then, in the framework of perfect information and finite action spaces, we provide an additional geometric description of the perturbations for which uniqueness occurs. As an application, we obtain a perturbation scheme allowing one to solve degenerate instances of stochastic games by policy iteration.
Document type :
Complete list of metadata

Cited literature [116 references]  Display  Hide  Download
Contributor : ABES STAR :  Contact
Submitted on : Wednesday, March 29, 2017 - 9:13:09 PM
Last modification on : Friday, October 23, 2020 - 5:02:38 PM
Long-term archiving on: : Friday, June 30, 2017 - 5:05:52 PM


Version validated by the jury (STAR)


  • HAL Id : tel-01423953, version 2


Antoine Hochart. Nonlinear Perron-Frobenius theory and mean-payoff zero-sum stochastic games. Optimization and Control [math.OC]. Université Paris Saclay (COmUE), 2016. English. ⟨NNT : 2016SACLX079⟩. ⟨tel-01423953v2⟩



Record views


Files downloads