The Setting
A mean-payoff game is played by Max and Min on a finite directed graph with vertex set of size , each vertex owned by one of the two players, and with integer weights on its edges, the owner of the current vertex choosing the next edge. The zero-threshold winning set of a mean-payoff game is the set of vertices of from which Max can force the long-run average weight of the play to be nonnegative. The main theorem gives a randomized algorithm that computes all of in time quasipolynomial in the length of the game’s code.
The library states it about one fixed Turing machine with three tapes that reads one random bit at each step. Running time becomes a number of steps, and the probability of success becomes the share of random tapes on which the machine writes .
Machines with a Random Tape
Every game has a fixed input code , a bit string whose length is denoted .
A three-tape machine with a random tape is a Turing machine with three tapes that, at each step, also reads the next bit of a random tape . Such a machine halts within steps on an input and a random tape when its configuration after steps, started on and , is a halting one. The good tapes of on a game at step are the random tapes on which writes on its tape 2: (1)
The Randomized Solver
A register program is a program on finitely many registers, each a stack of bits, whose steps may also flip a fair coin. Run on an input for steps, unfolds into its coin tree , the binary tree that branches at each coin flip and whose leaves are the configurations after steps, a leaf behind flips having probability ; for a property of leaves, is the total probability of the leaves that have it. Compiling gives a three-tape machine with a random tape, and to an input and a step limit the compilation attaches a step count of .
The randomized solver is the register program with five registers that runs on an input of length in three stages: preprocessing, drawing of coins, and postprocessing.✦ The preprocessing stage reads from a game on vertices with weights and computes its top width , where are the transformed weights, , and is the number of binary digits of ; it also computes the numbers (2) and the auxiliary data collects the game, , , , and the initial job, the single solve job with which the recursion starts, on the box with reference width . The second stage draws fair coins one at a time and records them. The postprocessing stage cuts the coins into blocks of bits, each read as a uniform index in , and runs the recursive solver as a stack of jobs for steps, one index per step, starting from the initial job. The output of is the set of vertices whose coordinate in the vector returned by the first solve job exceeds .
A solve job carries a solver input : a box with corners in , a reference width , positive rational support weights and budgets ; it returns a vector. An orientation is a choice between and together with a list of masks, each mask a list of truth values indexed by the vertices.✦ Among the jobs, an ask job returns the coordinatewise median of the vectors returned by solve jobs, and an orientation job returns the majority choice of orientation trials. The majority is strict, and the returned orientation carries the masks of all the trials.✦ A solve job whose budgets are small returns the small vector of the budgets and the box; otherwise a solve job on a box of width at most is answered by the basic solver, the procedure for small boxes, which is run on the game and the box for steps and returns a vector. The initial solve job carries the support weights and , each the vector with every entry equal to , and the budgets , two rational numbers. On a wider box, a solve job first tightens the box. A tighten job asks with the -reduced budgets on the box; if some coordinate of the returned vector lies at least the grid width , the box’s width divided by , above the lower corner, it raises the floor of the box to that vector and tightens again. Otherwise it asks with the -reduced budgets and, if some coordinate of the returned vector lies at least below the upper corner, it lowers the ceiling to that vector and tightens again; if neither happens the box is tight.
On the tight box, a solve job obtains an orientation from an orientation job and, for each mask of the orientation, asks on the box with the budgets reweighted by that mask, on the side if the orientation chooses and on the side if it chooses . It then calls itself on the box with its high cap at the cap width, the box’s width minus , for , and with its low cap for , and returns the coordinatewise minimum for , the coordinatewise maximum for , of the vector this call returns and the vectors returned by the asks.
A single orientation trial on a box of width at most marks the coordinates with , where is the vector returned by the basic solver, the lower corner and the width of the box; if the marked set has measure above one half for the budgets it returns with the complement of the set as its exception, and otherwise with the set as its exception.✦ On a wider box it computes centers, starting from the midpoint of the box, each next center being the clipped average of the answers of two ask jobs, with the -reduced and the -reduced budgets, on the box of width divided by centered at the current center. For the last center and the midpoint of the box it marks the coordinates with and those with ; if the first set has measure above one half it returns with its complement as exception, and if the second does it returns with its complement as exception. If neither does, it runs an orientation trial on the box of width divided by centered at a center chosen by a random index, and extends the orientation returned by the two masks.
The compilation of the solver is the machine of the main theorem. For constants and , the step limit of on is (3)✦ where is the step budget of the preprocessing stage and is the size of the code of a datum ; the third term is the step budget of the postprocessing stage. The total running time of on is , a step count of .✦ The postprocessing cost of an input of the postprocessing stage, recorded coins with auxiliary data, is the number of steps that stage is allowed on , the writing of its output included.✦
The Claim
Theorem 1 (Main theorem). There are a three-tape machine that reads one random bit per step and a real such that, for every game , with the length of its input code , some step count satisfies (4)✦ (5)✦
In the paper, the result reads: for a game on a finite directed graph with , , an ownership partition and signed integer weights , every vertex having an outgoing edge and self-loops and parallel edges permitted, in which the owner of a vertex chooses the next edge, both players may use strategies depending on the entire finite history, and a play has mean payoff , and for the total length of an explicit binary encoding of the graph, ownership and signed weights (endpoints and ownership charged), there is a uniform randomized algorithm that returns the entire set , where is the play from in which Max follows and Min follows , correctly with probability at least and whose total cost on every random tape is at most bit operations, for an absolute constant , in a standard model polynomially equivalent to a uniform probabilistic Turing machine, the bound including preprocessing, recursive calls, intermediate arithmetic and random-bit generation.
What Is Checked
The main theorem is stated over three-tape machines with a random tape and over games , through their input codes and their winning sets .
Take constants and with for every input of the postprocessing stage. The solver then satisfies, for every bit string and every game , (6)✦ (7)✦
For all constants and there is a real such that, for every bit string of length , (8)✦
Let be a register program, a game and a step limit, put , and suppose that every leaf of has halted. Then (9)✦ (10)✦ and if the probability in (10) is at least , then (11)✦