Using Strategy Improvement to Stay Alive

Luboš Brim, Jakub Chaloupka

We design a novel algorithm for solving Mean-Payoff Games (MPGs). Besides solving an MPG in the usual sense, our algorithm computes more information about the game, information tha…