Quasipolynomial algorithms for mean-payoff, stochastic and parity games

The explanation

Picture a game board with two spots, A and B. Max moves from A and Min moves from B. Every move scores points for Max, and a negative score is a loss. From A, Max can stay at A for −1 or move to B for +3. From B, Min can stay at B for +1 or return to A for −2. Play goes on forever. Max wins if the long-run average score per move is at least zero.

Work it out. If Max stays at A, the average is −1. If Max moves to B, Min gets the choice. Staying at B gives Max +1 per move. Returning to A makes a loop worth 3 − 2 = 1 over two moves, so 0.5 per move. Min picks 0.5, and Max prefers that to −1. So Max wins from A, and the game's value there is 0.5. The value is the best average Max can guarantee. Now change the −2 to −4. The loop now averages (3 − 4)/2 = −0.5, and Max loses from both spots.

This is a mean-payoff game (a two-player game on a network where only the long-run average score counts). The winning set is every starting spot from which Max can force an average of zero or more. In 1979, Ehrenfeucht and Mycielski proved that both players have optimal positional strategies. A positional strategy picks a move using only the current spot, never the history. That is why checking the four fixed plans above was enough.

The trouble is the size of the numbers. A computer writes each score in binary digits. Our own example: a score of about 1.15 quintillion (2 to the 60th) needs only 61 binary digits. In 1996, Zwick and Paterson gave pseudopolynomial algorithms. Their cost can be polynomial in the largest score, yet exponential in the number of digits. Faster methods existed for other measures. Björklund and Vorobyov proved an expected bound in terms of the number of spots. It counts arithmetic steps, not work on digits. A related game, the parity game, got a quasipolynomial algorithm in 2017. But the known translation runs from parity games to mean-payoff games, so that result did not carry over.

The single obstacle is simple to state. A natural method raises a running estimate for each spot step by step. With huge scores, the number of steps can grow in proportion to the size of the scores. The deterministic paper avoids computing that estimateSource 1. It only asks, for each spot, which end of a range the answer is forced towards. It splits the range in half again and again. It gives each spot weights that rise whenever the recursion gains groundSource 2. Along any branch, those rises can happen only about as often as the logarithm of the number of spots.

The deterministic paper claims an algorithm without randomness that returns the exact winning set. Its cost is at most 2 raised to C times the square of log₂(L + 2)Source 3. Here L is the total length of the input in binary digits, and C is some fixed constant. Such a bound is called quasipolynomial. Here is our own example. For an input of 1,000 digits, log₂(1,002) is about 9.97 and its square is about 99.4. So the bound is 2 to roughly 99 times C. A polynomial bound would be 2 to a fixed multiple of about 9.97. The paper notes that a polynomial bound would be a further improvementSource 4. The same paper claims to compute every spot's exact value and optimal positional strategies for both playersSource 5.

Two newer papers claim to stretch the method. The first adds chance spots, where a stated probability picks the next moveSource 6. It claims to find every spot whose expected long-run average is zero or more, with zeros includedSource 7. In a simple stochastic game, one player tries to reach a target spot and the other tries to stop them. Some moves are made by a fair coin. As a side result, the paper claims to decide whether such a game can be won with probability at least one halfSource 8. The second adds a parity condition. Each spot carries a whole number called its priority. Max must also make the smallest priority seen infinitely often an even number. These two goals can pull against each other, and the paper claims to handle them togetherSource 9.

A companion paper gives a randomized version. It returns the whole winning set correctly with probability at least 7/8Source 10. Its time bound holds on every run, even when the answer is wrongSource 11. The paper adds that a fast check catches a wrong answer. Repeating until the check passes then gives an always-correct methodSource 12. That repeated version is not part of the Lean check. Truffet has claimed a strongly polynomial method. The paper shows that one printed step of it loses the optimum on an explicit exampleSource 13.

How sure is this? A computer proof checker called Lean has checked a formal version of the randomized theorem. That covers the 7/8 success chance and the time bound on every run. Lean has also checked the finite counterexample to Truffet's step. The deterministic algorithm, exact values, chance spots and parity condition are outside that check. No specialists have published a review yet.

What it doesn't show. This does not give a polynomial-time algorithm for mean-payoff games.