  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.
