A mean-payoff game is a finite directed graph on in which every vertex has an outgoing edge, with a partition of the vertices between two players, Max and Min, and integer weights 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 is the infinite sequence of edges followed from a vertex when Max plays a strategy and Min plays a strategy . The mean payoff of a play is . The zero-threshold winning set is the set of vertices from which Max has a strategy with for every strategy of Min. The game is given by an explicit binary encoding of the graph, the ownership and the signed weights. Write for the total length of this encoding. Write for the largest absolute weight. The question is to compute at a cost controlled by the binary length rather than by the magnitude 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 of the weights. Such a cost can be exponential in . 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 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 of every such game correctly with probability at least . For an absolute constant , this algorithm uses at most 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 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 such that, for every game, some has the machine halted after steps on every tape of random bits. On at least of these tapes, the output tape holds exactly . The Lean library also bounds this number of steps by a polynomial in the sum of and . 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 within steps, for some real , 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.
RandomMean is a Lean library: 11 items, in four groups. Each has a page written by OctoInform, listed below.
No item matches.