  We study two-player (zero-sum) concurrent mean-payoff games played on a
finite-state graph. We focus on the important sub-class of ergodic games where
all states are visited infinitely often with probability 1. The algorithmic
study of ergodic games was initiated in a seminal work of Hoffman and Karp in
1966, but all basic complexity questions have remained unresolved. Our main
results for ergodic games are as follows: We establish (1) an optimal
exponential bound on the patience of stationary strategies (where patience of a
distribution is the inverse of the smallest positive probability and represents
a complexity measure of a stationary strategy); (2) the approximation problem
lie in FNP; (3) the approximation problem is at least as hard as the decision
problem for simple stochastic games (for which NP intersection coNP is the
long-standing best known bound). We present a variant of the strategy-iteration
algorithm by Hoffman and Karp; show that both our algorithm and the classical
value-iteration algorithm can approximate the value in exponential time; and
identify a subclass where the value-iteration algorithm is a FPTAS. We also
show that the exact value can be expressed in the existential theory of the
reals, and establish square-root sum hardness for a related class of games.
