The complexity of mean payoff games using universal graphs

Nathanaël Fijalkow, Paweł Gawrychowski, Pierre Ohlmann

We study the computational complexity of solving mean payoff games. This class of games can be seen as an extension of parity games, and they have similar complexity status: in bot…