We study the complexity of finding the values and optimal strategies of
MEAN PAYOFF GAMES on graphs, a family of perfect information games
introduced by Ehrenfeucht and Mycielski and considered by Gurvich,
Karzanov and Khachiyan. We describe a pseudo-polynomial time algorithm
for the solution of such games, the decision problem for which is in
$\NP\,\cap\,\coNP$. Finally, we describe a polynomial reduction from
mean payoff games to the SIMPLE STOCHASTIC GAMES studied by Condon.
These games are also known to be in $\NP\,\cap\,\coNP$, but no
polynomial or pseudo-polynomial time algorithm is known for them.

This is the full version of the paper. An extended abstract
version of the paper will appear in the proceedings COCOON'95.