The Setting
Take a mean-payoff game on a set of vertices, given by an input code of length . The library’s solver is recursive: a call on a box with corners in and reference width , positive rational support weights and budgets answers small instances directly, and otherwise calls itself many times over, to take medians and majorities of random trials. For its bit complexity on a Turing machine with a random tape, the question is how many steps the root call can need, as a function of .
The library runs the recursion on a stack machine. A step either starts a job, leaving on the stack a frame that records what to do with the answer, or hands a returned value to the frame on top of the stack. The rank of the root call is the number of steps it needs. A preparation computes a step count in unary from the input code, and the control loop runs exactly that many steps on every tape, one random sample index per step; the library bounds the rank of the root call by that count.
The Stack Machine
An environment is a tuple of a raw arena , the game graph encoded as bit strings with, on each edge , its transformed weight , where is the weight of , and four unary counters, lists of units in which a counter of length stands for : the sample exponent , the number of samples, the number of trials and the step budget of the basic solver, the solver run directly on boxes of reference width at most . A register pack is a record of eight registers: budgets, a box , a counter , two vectors and of binary words, a list of such vectors, an orientation and a list of orientations.✦ An orientation is a choice, or , with a list of masks, its exceptions, each a boolean list marking a set of vertices.✦ A register left unset holds zero: the zero budget, the zero box, the empty counter or list, or the orientation choosing with no masks✦; the empty pack has every register at zero.✦
A stack cell is a pair of a tag, a unary counter naming a job or a frame, and a register pack.✦ A control state is a pair of a current cell, which holds the job being called or the value being returned, and a stack, the list of cells holding the pending frames.✦ A control accumulator is a pair ✦ of an environment and a control state, and a machine input is a triple whose unary counter , the random counter, is the sample index of the step.
A step runs one case. A case either returns a pack, which becomes the current cell under the return tag ✦, or calls a job: the job’s tag and pack become the current cell✦, and a frame, a cell recording what to do with the answer, is pushed onto the stack.✦ In the cases below the current box is , with floor , ceiling , midpoint and grid width ; the narrowed box at a vector is the box centered at of width ✦, and the widened box at is the box centered at of width . Besides solve, the job of the root call, there are nine jobs.
Ask calls trials with the counter and leaves a median frame✦, which returns the boxed median of the answers✦: their coordinatewise median, or when there are none.✦
Trials with a counter calls solve times on its budgets and box and returns the list of answers, through trials head and vector cons frames.✦
Update at , written , asks on the budgets reduced in and the narrowed box at ✦; a first center frame asks on the budgets reduced in and the same box✦, and a second center frame returns the average of the two answers, clipped to .✦
Centers with a counter and a vector returns the list , through centers head and vector cons frames.✦
Orient on a box with returns the base orientation of the basic solver’s output ✦: with the mask of the vertices such that , it chooses with the complement of as exception when has measure above one half under the budgets, and with as exception otherwise.✦ On a wider box it calls centers with the counter from and leaves an orient loop frame.✦
Orientation trials with a counter collects orientations by calls of orient, through orient head and orient cons frames.✦
Orientation plus calls orientation trials with the counter and leaves a combine frame✦, which returns the majority✦: the choice when more than half of the orientations choose , with all their masks concatenated.✦
Tighten asks on the budgets reduced in .✦ When the answer moves the floor of the box, relative to , a first tightening frame tightens the box with its floor at the answer; otherwise it asks on the budgets reduced in ✦, and a second tightening frame does the same with the ceiling and returns the box when the ceiling does not move.✦ Two box passing frames, for the floor and the ceiling, pass up the box a nested tightening returns.✦
Reweight with an orientation asks once for each of its masks, in order, on the budgets reweighted by that mask for the orientation’s choice, and returns the list of answers, through reweight head and vector cons frames.✦
The orient loop frame takes the last center and the masks of the vertices with and of those with . When has measure above one half it returns the orientation choosing with the complement of as exception, and when has, the one choosing with the complement of .✦ Otherwise it calls orient on the widened box at the center of index , the random counter, or at when there is none✦, and an orient tail frame appends and to the masks of the returned orientation.✦
Solve returns, when the budgets are small, the vector prescribed for small budgets on the box, and when , the output of the basic solver run on and the box within steps.✦ Otherwise it calls tighten✦, and its main chain runs through frames: a solve tight frame calls orientation plus on the tightened box✦, a solve oriented frame calls reweight with the returned orientation✦, and a solve reweighted frame calls solve on the tightened box capped high, for the choice , or capped low, for , by its width less its grid width.✦ A cap high frame returns the coordinatewise minimum of that answer and the reweighted answers✦, a cap low frame their coordinatewise maximum✦, and an include inner frame makes this vector the answer of the outer call.✦
The dispatch of a machine input is the control state obtained by reading the tag of the current cell: tags to run the cases of solve, ask, trials, update, centers, orient, orientation trials, orientation plus, tighten and reweight, and any other tag resumes.✦ Resuming keeps when the stack is empty; otherwise it runs the frame case named by the tag of the top cell, one of twenty-two, and keeps for a larger tag.✦ The advance step is the map taking a control accumulator and a random counter to the accumulator that keeps the environment and replaces the state by its dispatch: (1)✦ The control loop is the map taking a control accumulator and a list of random counters to the result of the advance step applied once for each counter in turn: (2)✦
The Preparation
The preparation reads a binary string of length ; denotes the length of a unary counter , and the counter of units. The input logarithm is the program that takes to the counter of its length, adds one twice, writes the result in binary and returns its ceiling base 2 logarithm as a unary counter.✦ The preparation exponent is the program that multiplies the constant counter by the square of the input logarithm, the square taken by the fixed power code, which raises a counter to a fixed exponent by repeated multiplication.✦ The iteration count of is the number (3)✦
The preparation root parses as a game with vertices and top width , where is the weight bound of the transformed weights . It sets to the binary length of plus one and the sample exponent to , so that is the least power of two with , and (4) It returns the seed made of , , and the initial accumulator ✦: the environment holds the game’s arena✦, and calls solve, over an empty stack, on the budgets and , where is the all-ones vector, and the box .
The preparation value of doubles a single unit times, which gives the counter , and assembles it with the seed✦: it returns the counter of units, cut into chunks of units each, together with the chunk length , the number of samples, the number of chunks, the width and the initial accumulator. As is a power of two, a chunk of fair bits gives a uniform sample index in .
The Claim
For a game , is its input code and its root control bound, the natural number , 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); both are defined in the imported library MeanPayoff, and is rootControlBound in MeanPayoff/ArithmeticBounds.lean. The control state of the root call calls solve on the root budgets and the root box of with nothing pending.
Theorem 1. Let be a mean-payoff game. The rank of the control state of its root call is at most its root control bound, (5)✦ and the root control bound is at most the iteration count of its input code, (6)✦ For every binary string of length , the preparation exponent has length (7)✦ and the number of chunks of the preparation value is the counter (8)✦
In the paper, the result reads: with solver invocations per main chain and smaller-rank descendants per chain node, the number of solver invocations from one invocation of rank at most satisfies and , hence with and . The library counts the control steps of the root call instead of its solver invocations.
What Is Checked
The claim is stated over mean-payoff games with their input code, the control state of the root call with its rank, the root control bound, and, for every binary string, the preparation exponent, the iteration count (3) and the preparation value.
Beyond the claim, the control loop (2) runs within a size bound: for every control accumulator , every list of random counters and every , (9)✦ where is the encoded size and . The coordinatewise minimum and maximum of the cap frames obey a bound of the same kind: for a vector and a list of vectors of encoded size in all, the coordinatewise minimum, or maximum, of the vector with the first vectors of the list has encoded size at most for every .