OctoInform Beta

Randomized quasipolynomial-time mean-payoff games

A mean-payoff game is a finite directed graph G=(V,E)G=(V,E) on V={1,…,n}V=\{1,\ldots,n\} in which every vertex has an outgoing edge, with a partition V=VMax∪VMinV=V_{\mathrm{Max}}\cup V_{\mathrm{Min}} of the vertices between two players, Max and Min, and integer weights w:E→ℤw\colon E\to\mathbb{Z} on the edges. A strategy of a player chooses, at each vertex the player owns, the next edge as a function of the whole history of the play. A strategy is positional when its choice depends only on the current vertex. The play πv,σ,τ=(e0,e1,…)\pi_{v,\sigma,\tau}=(e_0,e_1,\ldots) is the infinite sequence of edges followed from a vertex vv when Max plays a strategy σ\sigma and Min plays a strategy τ\tau. The mean payoff of a play π=(e0,e1,…)\pi=(e_0,e_1,\ldots) is MP⁡w(π)=liminf⁡T→∞1T∑j=0T−1w(ej)\operatorname{MP}_w(\pi)=\liminf_{T\to\infty}\frac1T\sum_{j=0}^{T-1}w(e_j). The zero-threshold winning set UU is the set of vertices vv from which Max has a strategy σ\sigma with MP⁡w(πv,σ,τ)≥0\operatorname{MP}_w(\pi_{v,\sigma,\tau})\ge0 for every strategy τ\tau of Min. The game is given by an explicit binary encoding of the graph, the ownership and the signed weights. Write LL for the total length of this encoding. Write M=max⁡e∈E|w(e)|M=\max_{e\in E}|w(e)| for the largest absolute weight. The question is to compute UU at a cost controlled by the binary length LL rather than by the magnitude MM of the weights.

Ehrenfeucht and Mycielski proved the positional structure of mean-payoff games. A cost is pseudopolynomial when it is polynomial in the magnitude MM of the weights. Such a cost can be exponential in LL. Zwick and Paterson gave pseudopolynomial algorithms for mean-payoff games. For graphs without parallel edges, Björklund and Vorobyov obtained a strategy improvement algorithm with an expected 2O(nlog⁡n)2^{O(\sqrt{n\log n})} bound on the arithmetic operations. A parity game is played on a graph whose vertices carry priorities, and the winner of a play is determined by the priorities that occur infinitely often. Calude, Jain, Khoussainov, Li and Stephan gave a quasipolynomial algorithm for parity games. The bounds of Fijalkow, Gawrychowski and Ohlmann for mean-payoff games involve the magnitude of the weights or depend exponentially on the number of distinct weights. The recursion of Ohlmann for mean-payoff games leaves its subexponential complexity analysis open.

The preprint proves that a uniform randomized algorithm returns the whole set UU of every such game correctly with probability at least 7/87/8. For an absolute constant C>0C>0, this algorithm uses at most 2C(log⁡2(L+2))22^{C(\log_2(L+2))^2} bit operations on every random tape, in a standard model polynomially equivalent to a uniform probabilistic Turing machine. The preprint derives from it an always-correct algorithm, of quasipolynomial expected bit cost, that returns UU with positional winning strategies for both players certified by a polynomial-time check; the Lean library does not contain this algorithm.

The Lean library RandomMean proves that there are a three-tape Turing machine that reads one random bit at each step and a real C>0C>0 such that, for every game, some t≤2C(log⁡2(L+2))2t\le2^{C(\log_2(L+2))^2} has the machine halted after tt steps on every tape of tt random bits. On at least 7/87/8 of these 2t2^t tapes, the output tape holds exactly UU. The Lean library also bounds this number of steps tt by a polynomial in the sum of LL and 225000⌈log⁡2(L+2)⌉22^{25000\lceil\log_2(L+2)\rceil^2}. Lean has checked every result of the Lean library, so the Lean library is the reference. Each result on these pages is stated as the Lean library states it and linked to the Lean declaration behind it, and where the preprint states it differently, the preprint’s statement is given beside it. The preprint is a guide only: it gives the results their order and their names. OpenAI’s catalog entry also lists Turn-Based Stochastic Mean-Payoff Games in Deterministic Quasipolynomial Time and Mean-payoff parity games in quasipolynomial time, of which the Lean library contains nothing, and Deterministic quasipolynomial-time mean-payoff games. Of that last preprint, only the statement that a deterministic three-tape Turing machine computes UU within 2C(log⁡2(L+2))22^{C(\log_2(L+2))^2} steps, for some real C>0C>0, is proved in Lean, in the library MeanPayoff that RandomMean imports, and it is not stated on these pages; that preprint’s exact values and optimal positional strategies are in neither library.

The Lean library: RandomMean

RandomMean is a Lean library: 11 items, in four groups. Each has a page written by OctoInform, listed below.