A basic question for zero-sum repeated games consists in determining whether the mean payoff per time unit is independent of the initial state. In the special case of "zero-player" games, i.e., of Markov chains equipped with additive functionals, the answer is provided by the mean ergodic theorem. We generalize this result to repeated games. We show that the mean payoff is independent of the initial state for all state-dependent perturbations of the rewards if and only if an ergodicity condition is verified. The latter is characterized by the uniqueness modulo constants of nonlinear harmonic functions (fixed points of the recession function associated to the Shapley operator), or, in the special case of stochastic games with finite action spaces and perfect information, by a reachability condition involving conjugate subsets of states in directed hypergraphs. We show that the ergodicity condition for games only depends on the support of the transition probability, and that it can be checked in polynomial time when the number of states is fixed.
Then, in @cite_26 , Cavazos-Cadena and Hern 'a ndez-Hern 'a ndez introduced a weak convexity property, and showed that when the conjugate map @math is weakly convex, the recession function @math has only trivial fixed points if and only if the first of the directed graphs of @cite_22 consists of a single final class and of trivial classes (reduced to one node, and loop free). They deduced that when @math is weakly convex, the ergodic equation for all maps @math with @math is solvable if and only if @math has only trivial fixed points. We shall consider the same additive perturbations @math of the Shapley operator, but without any assumption on @math except that the payment @math be bounded. Indeed, this weak convexity property is rarely satisfied for games although it captures an interesting class of risk sensitive problems.
@cite_26 @cite_22
2084982707 1608548244
Abstract Given a monotone and homogeneous self-mapping f of the n -dimensional positive cone, a communication matrix M f is introduced and a family F of functions is obtained by multiplying each component of f by arbitrary positive numbers. Assuming that f satisfies a weak form of convexity, a necessary and sufficient criterion on the structure of M f is given so that each function in F has a (nonlinear) eigenvalue. An alternative necessary and sufficient condition in terms of the recession function of f is also provided. If A is a nonnegative matrix whose associated directed graph is strongly connected, the Perron-Frobenius theorem asserts that A has an eigenvector in the positive cone, (R + ) n . We associate a directed graph to any homogeneous, monotone function, f: (R + ) n → (R + ) n , and show that if the graph is strongly connected, then f has a (nonlinear) eigenvector in (R + ) n . Several results in the literature emerge as corollaries. Our methods show that the Perron-Frobenius theorem is really about the boundedness of invariant subsets in the Hilbert projective metric. They lead to further existence results and open problems.