Potential theory for mean payoff games

We present an $O(mn2^n\log Z)$ deterministic algorithm for solving the mean payoff game problem, $m$ and $n$ being respectively the number of arcs and vertices in the game graph and $Z$ being the maximum weight (we assume that the weights are integer numbers). The theoretical basis for the algorithm is the potential theory for mean payoff games. This theory allows to restate the problem in terms of solving systems of algebraic equations with minima and maxima. Also we use arc reweighting technique to solve the mean payoff game problem by applying simple modifications to the game graph that do not change the set of winning strategies, obtaining at the end a trivial instance of the problem. We show that any game graph can be simplified by $n$ reweightings.