The complexity of mean payoff games on graphs

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 boolean AND 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 boolean AND coNP, but no polynomial or pseudo-polynomial-time algorithm is known for them.