The complexity of mean payoff games on graphs

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