  We study the computational complexity of solving mean payoff games. This
class of games can be seen as an extension of parity games, and they have
similar complexity status: in both cases solving them is in $\textbf{NP} \cap
\textbf{coNP}$ and not known to be in $\textbf{P}$. In a breakthrough result
Calude, Jain, Khoussainov, Li, and Stephan constructed in 2017 a
quasipolynomial time algorithm for solving parity games, which was quickly
followed by two other algorithms with the same complexity. Our objective is to
investigate how these techniques can be extended to the study of mean payoff
games.
  The starting point is the notion of separating automata, which has been used
to present all three quasipolynomial time algorithms for parity games and gives
the best complexity to date. The notion naturally extends to mean payoff games
and yields a class of algorithms for solving mean payoff games. The
contribution of this paper is to prove tight bounds on the complexity of
algorithms in this class. We construct two new algorithms for solving mean
payoff games. Our first algorithm depends on the largest weight $N$ (in
absolute value) appearing in the graph and runs in sublinear time in $N$,
improving over the previously known linear dependence in $N$. Our second
algorithm runs in polynomial time for a fixed number $k$ of weights.
  We complement our upper bounds by providing in both cases almost matching
lower bounds, showing the limitations of the separating automata approach. We
show that we cannot hope to improve on the dependence in $N$ nor break the
linear dependence in the exponent in the number $k$ of weights. In particular,
this shows that separating automata do not yield a quasipolynomial algorithm
for solving mean payoff games.
