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

Summary Stochastic zero-sum games have a recursive structure that is expressed in their dynamic programming operator, the Shapley operator. The latter allows us to study the asymptotic behavior of the average payment per unit time. In particular, the average payment exists and does not depend on the initial state if the ergodic equation - a nonlinear eigenvalue equation involving the Shapley operator - has a solution. Understanding under which conditions this equation admits a solution is a central problem in nonlinear Perron-Frobenius theory, and is the main topic of study in this thesis. Various known classes of Shapley operators can be characterized by properties based entirely on the order relation or the metric structure of the space. We first extend this characterization to "payoff-free" Shapley operators, which arise from games without instantaneous payoffs. For this purpose, we establish an expression in minimax form for homogeneous functions of degree one and non-expansive with respect to a weak Minkowski norm. We then address the problem of whether the ergodic equation has a solution for any additive perturbation of payments, a problem that extends the notion of ergodicity of Markov chains. When the payments are bounded, this "ergodicity" property is characterized by the uniqueness, to within one additive constant, of the fixed point of a Shapley operator without payments. We give a combinatorial solution expressed by means of hypergraphs to this problem, as well as to related fixed point existence problems. Then, we derive complexity results. Using the theory of accretive operators, we then generalize the hypergraph condition to all types of Shapley operators, including those from games with unbounded payoffs. In a third step, we consider the problem of uniqueness, to within one additive constant, of the eigenvector. We first show that uniqueness occurs for a generic perturbation of the payoffs. Then, in the framework of perfect information games with a finite number of actions, we specify the geometric nature of the set of perturbations where uniqueness occurs. We derive a perturbation scheme that allows us to solve degenerate instances for iteration over policies.