  We propose a novel algorithm for the solution of mean-payoff games that
merges together two seemingly unrelated concepts introduced in the context of
parity games, small progress measures and quasi dominions. We show that the
integration of the two notions can be highly beneficial and significantly
speeds up convergence to the problem solution. Experiments show that the
resulting algorithm performs orders of magnitude better than the
asymptotically-best solution algorithm currently known, without sacrificing on
the worst-case complexity.
