The Setting
Let be a mean-payoff game on a set of vertices with integer edge weights , written for a machine as its input code , a binary string of length . The task is to output the zero-threshold winning set with a machine that reads its random choices off a tape of fair bits. A list of bits is correct for when it marks exactly the vertices of .
The algorithm works with the transformed weights , the weight bound and the top width . Its solver takes a box with corners in and reference width , positive rational support weights , and budgets , , and returns a random vector of the box. The thresholded solver is the random list of bits whose -th bit says whether , for the output of the root call .
The library builds this algorithm as a register program on and a tape of fair bits, and reaches it from the solver through two machines: the solver as a control machine whose random choices are uniform sample indices, and a raw control machine on bit strings and unary counters, in which a counter stands for its length.
The Solver as a Control Machine
Fix a bound , with sample count , a power of two, and trial count , the global parameters at ; fair bits give a uniform index in . A state of the solver for at bound is a call of a job under a continuation , or a return of a value to , where a continuation is a stack of pending frames, each a job waiting for the value of the call above it, over the empty continuation . The jobs are solve, ask, trials, update, centers, orient, orientation trials, orientation plus, tighten and reweight; a solve job on budgets and a box is the call of on them.
The sampled step with sample index is the map on states that makes one move of the solver.✦ A return to stays as it is, a return to a pushed frame resumes that frame with the value, and a call makes its job’s first move: a solve job returns the small vector when the parameter of is below , the exact vector when has width at most , and otherwise tightens ; an ask runs trials and returns their median box, and trials with remaining run one solve at a time. An update asks the budgets reduced in on the box centered at its current center of width , the width of , and then, on the same box, the budgets reduced in ; centers with remaining run updates; an orient job on a box of width at most is the base orientation, and otherwise computes centers from the midpoint of the box; orientation trials repeat the orient job times, and orientation plus combines these trials into the choice made by a strict majority, with all their exception sets listed one after another; a tighten job asks the budgets reduced in ; a reweight job asks, for each exception set of the orientation in turn, the budgets reweighted at , in for the choice and in for the choice . An orientation is a choice between and together with a list of exception sets of vertices. The index is read in one place, the orientation loop: it takes the centers of the trial vectors, the positive and negative displacement sets of a center being the coordinates where it lies far above or far below the midpoint of the box, and when neither the positive nor the negative displacement set at the -th center has measure above , it orients the widened centered box at the -th center. A frame resumed with a value combines it: trial vectors and centers are collected into lists, the median box of the trial vectors in is returned, and the clipped average of two centers is returned. When the positive displacement set at the -th center has measure above for the budgets, the orientation loop returns the choice with the complement of that set as its exception set, and when the negative displacement set has, the choice with the complement of that set. An orientation computed on the widened centered box keeps its choice and has the two displacement sets appended to its exception sets. A tightening moves the floor of to when some coordinate of lies at least the grid width from the lower corner, and after a second ask the ceiling of to when some coordinate lies at least from the upper corner; otherwise the box is returned unchanged. A solve job on a box of width above calls the orientation plus job on the tightened box and then reweights by the choice between and and the exception sets of the orientation returned; it then calls the solve job on the budgets and the tightened box capped high, for the choice , or capped low, for , by its width minus its grid width , and returns the coordinatewise minimum, respectively maximum, of the vector of that call and the vectors returned by the reweighting. The base orientation of a box with lower corner and width , for the budgets and the exact vector of , is given by the set of coordinates with : if has measure above for , it chooses with the complement of as its exception set, and otherwise it chooses with as its exception set.✦
Each state has a rank , a number of steps after which the solver started at has halted, and an output law , the law of the value it returns. The solver’s step semantics, its one-step transition law on states, run for steps from , gives a random state . The sampled run is the random state reached from by sampled steps, each with a fresh uniform index: (1)✦
The Raw Control Machine
A register pack is a record of eight registers: budgets, a box, a unary counter, a first vector and a second vector of binary words, a list of vectors, an orientation and a list of orientations, where an orientation is a bit, true for , with a list of vertex masks.✦ A stack cell is a tag, a unary counter whose length names a job or a frame, with a register pack holding its data.✦ A raw control state is a current cell, holding the job called or, under tag , the value returned, over a stack of cells holding the pending frames; is the pack of its current cell.✦
An environment is a raw arena, a bit string that can code a graph, together with four counters.✦ An environment represents at bound , written , when its arena codes the graph of with the transformed weight on each edge and its counters have lengths , , and at least , the last bounding the steps of the basic solver, the solver that returns the exact vector on a box of width at most .✦
A raw control state represents a solver state , written , when its current cell carries the tag of the job calls, or tag when returns, with a pack holding the job’s budgets, box, counts and vectors or the returned value, and its stack represents the continuation of cell by cell, each cell carrying the tag and the data of its frame.✦ A pack represents a value , written , when the register of the value’s kind holds it: a vector in , a list of vectors, an orientation or a list of orientations in its own register, an inner box in the box register.✦
The advance step with environment and a sample index, given as a counter, moves by the tag of its current cell: tags to make the first move of the jobs in the order listed above, and any other tag resumes the frame on top of the stack, or leaves as it is when the stack is empty.✦ Its moves compute the solver’s operations on raw data: coordinatewise medians of trial vectors, strict majorities of orientations, and the basic solver on boxes of width at most . For a box of midpoint and width and a center , they build the masks of the displacement sets and , the centered boxes of widths and , and the grid width .
The control loop is the raw control state reached from by the advance step with and the indices in turn.✦ Drawn samples at bound are independent counters , each uniform in .✦
The Root Call and the Register Program
The root environment holds the arena of and the counters , , and at bound , computed as (2)✦ with the binary length of . In the root call the budgets are (3)✦ and its initial box is the box of reference width : (4)✦ The initial control state calls job , the solve job, on a pack holding these budgets and this box, over the empty stack.✦ The root call has a bound on its number of steps, its root control bound , where is the number of control steps the library allows for one solver invocation on a game with vertices and top width (controlAllowance) and is its bound on the number of solver invocations of the root call (rootInvocationBound); is rootControlBound, defined in the imported library MeanPayoff (MeanPayoff/ArithmeticBounds.lean).
The classification by half of a binary word and a vector of binary words is the list of bits (5)✦ where is on a true condition and on a false one.
On the preparation computes the number of samples and of random bits, (6)✦ and the auxiliary data : the numbers , and , the width , the root environment and the initial control state . The answer on random bits is the list of bits obtained by cutting into chunks of bits, reading the -th chunk as a binary number , running the control loop on and classifying the first vector of the final pack by : (7)✦
The register program is a program on five registers. It runs the preprocessing, which reads and computes the preparation, then draws a fresh fair bit for each of the units of the counter left by the preparation, then runs the postprocessing, which computes the answer on these bits and and writes it out. The postprocessing cost of an input of the postprocessing, random bits with auxiliary data, is the step bound for computing its answer plus the cost of writing it out, plus ; is the encoded size of .✦ For constants and , the step limit on is (8)✦ where is the preprocessing cost, the steps of reading the input and of the preparation. Run for steps from its initial configuration on , ends in a random configuration whose output is the list .
The Claim
Theorem 1. Let be a mean-payoff game on vertices.
(a) The initial control state represents the root call over the empty continuation: (9)✦
(b) If is a vector of the box , a pack represents , and is a binary word of value , then the classification (5) gives (10)✦
Let further be a state of the solver for at a bound , with sample count .
(c) If an environment and a raw control state satisfy and , then for all indices (11)✦
(d) For every and every function from states to the rationals, (12)✦
(e) If are drawn samples at bound , then for every such (13)✦
(f) If and are as in (c) and , if are drawn samples at bound , and if functions on packs and on the values can return, both to the rationals, satisfy whenever , then (14)✦
(g) If , are drawn samples at bound , and maps lists of bits to the rationals, then (15)✦
(h) If is uniform in , then for every such the answer (7) satisfies (16)✦
(i) If constants and bound the postprocessing cost, for every input of the postprocessing, and , then for every such (17)✦
(j) Under the same bound on the postprocessing cost, (18)✦
In the paper, the result reads: compute , , and the global parameters, run and return ; by Corollary 6.4 the single event , for the box solution of , has probability at least , and on it Proposition 2.5 identifies with the entire zero-threshold winning set.
What Is Checked
The claim is stated over mean-payoff games and their input codes; the solver’s states at a bound with the sampled step, the sampled run (1), the step semantics, ranks and output laws; the raw control machine with its environments, packs, control loop and representations; the root environment (2), budgets (3), box (4) and initial control state; the classification (5); the preparation (6) and the answer; and the register program run for the step limit (8) under a polynomial bound on the postprocessing cost.
The library also bounds the sizes of the raw computations. Every pair of environment and control state that the control loop passes through, from a start on a list of indices, has encoded size at most .✦ Cutting random bits into samples keeps every intermediate state of encoded size at most ✦, and every partial coordinatewise maximum or minimum of vectors has encoded size at most , for the input in each case.