abstract
in this work we offer an o(|v |2 |e|w ) pseudo-polynomial time deterministic algorithm for
solving the value problem and optimal strategy synthesis in mean payoff games. this improves by a factor log(|v |w ) the best previously known pseudo-polynomial time upper bound
due to brim, et al. the improvement hinges on a suitable characterization of values, and a
description of optimal positional strategies, in terms of reweighted energy games and small
energy-progress measures.