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

Antoine Hochart 1, 2
1 TROPICAL - TROPICAL
CMAP - Centre de Mathématiques Appliquées - Ecole Polytechnique, Inria Saclay - Ile de France
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 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 :
Theses
Complete list of metadatas

https://pastel.archives-ouvertes.fr/tel-01423953
Contributor : Antoine Hochart <>
Submitted on : Sunday, January 1, 2017 - 1:11:03 PM
Last modification on : Wednesday, March 27, 2019 - 4:08:32 PM
Long-term archiving on: Sunday, April 2, 2017 - 1:41:31 PM

Identifiers

  • HAL Id : tel-01423953, version 1

Collections

Citation

Antoine Hochart. Nonlinear Perron-Frobenius theory and mean-payoff zero-sum stochastic games. Optimization and Control [math.OC]. Ecole polytechnique, Palaiseau, France, 2016. English. ⟨NNT : 2016SACLX079⟩. ⟨tel-01423953v1⟩

Share

Metrics

Record views

244

Files downloads

27