The Setting
Let be a mean-payoff game on a vertex set of vertices with edge weights , transformed weights , weight bound and top width . Procedure 4.3 is the solver of the recursion of Section 4 of the paper on randomized quasipolynomial-time mean-payoff games. It takes a solver input : a box with corners in and reference width , positive rational support weights and budgets . It returns a vector of . On the way it calls two other procedures, Ask, which returns a vector for a box and a budget, and OrientPlus, which returns an orientation, a choice of or with a list of exception sets of vertices, and it calls itself on a box capped in width. Its thresholds are set by the global parameter of (4.1), a power of two.
The solver is a machine with an explicit call stack and one case for each step of the recursion; its arithmetic, done on raw data, computes the paper’s quantities.
Raw Data and Frames
The solver works on raw data, bit strings and unary counters. A raw vector is a list of binary words that represents a vector of , and we write when the raw vector represents . A list of raw vectors represents a list of integer vectors when it has length and its -th entry represents .✦ A raw box is a raw encoding of a box and a raw budget is a raw encoding of a budget ; each is written with the letters of what it represents.
An environment is the raw arena of the game together with four unary counters.✦ An environment represents at top width when its arena encodes with each edge labelled by a binary word of value , its first three counters have lengths , and , where is the global parameter of (4.1) beside , and its fourth counter, the step budget of the run of the basic solver, in (4), has length at least .✦
A frame is the record of one call: a budget , a box , a counter of remaining trials, two vectors, a list of vectors, an orientation and a list of orientations, kept under a tag that names the job the frame runs or the step at which it resumes.✦ An orientation is a choice of or together with a list of exception sets of vertices, the sets on which the reweighted budgets halve a support weight. A raw orientation is a bit, true when the choice is , together with a list of bit strings, each marking a set of vertices. A control state is a nonempty call stack: the frame being run, on top of the frames waiting below it.✦ We write it , with on top and the frames below, and show of each frame only the fields its case reads.
A step of the machine reads the environment, a unary counter that gives the sample index used in that step, an index in , and the control state, and replaces the top frame. A job returns a value by leaving the return frame in its place, or calls another job by leaving that job’s frame above a frame that waits for the answer; a return frame resting on a waiting frame is handled by the waiting frame’s case. The jobs are , , and the solver’s own and .
For a box and a vector , the boxes and replace one corner by , and for a width the two capped boxes are (1) For a budget , the budgets and reduce to or to , with the reduction factor . For a set of vertices, the reweighted budgets are and , where and halve and on .
The Claim
Definition 1 (Procedure 4.3, the solver). Let an environment represent at top width , and let be a box of the game and a budget. A frame running answers at once when the parameter of (formula (3.2) of the paper) is below or when the width test of (3) passes; otherwise it starts the tightening and waits in the frame : (2)✦ where is the endpoint vector, with when and otherwise. The width test is the truth value, or , of a comparison of the reference width with : (3)✦ The basic run runs the basic solver on the arena and the box for the environment’s step budget.✦ When , the basic run returns the box solution, the exact vector of the game on the box : (4)✦ The tightening job asks with the reduced budget and waits in : (5)✦ The grid width of a box is shifted right by places, and the moves of the tightening job are measured against it: (6)✦ An answer that raises a coordinate of the lower corner by restarts the tightening on and leaves the frame ; any other answer is followed by a second ask, with : (7)✦ The second answer restarts the tightening on when it lowers a coordinate of the upper corner by ; otherwise the job returns the box : (8)✦ A frame left by a restart passes the returned box on: (9)✦ With the final box back, the solver frame calls OrientPlus with its budget and leaves the frame above an empty frame : (10)✦ The orientation that comes back starts the reweighting job on , and the choice is kept in : (11)✦ The reweighting job returns the empty list when is empty. Otherwise it asks on with the budget reweighted on the first set and keeps the remaining sets in : (12)✦ Each answer waits in a frame while the job runs on the remaining sets: (13)✦ The cap width of a box is obtained by subtracting from : (14)✦ When the list of answers reaches , the solver is called on the box capped at width , by (1), from above when and from below when : (15)✦ The minimum fold and the maximum fold take a raw vector and raw vectors , and when and for vectors of one box, they compute the coordinatewise minimum and maximum: (16)✦ (17)✦ The solution of the capped box is folded with the answers, by the minimum when and by the maximum when : (18)✦ (19)✦ and the empty frame passes the result on: (20)✦
In the paper, the result reads, in steps S1 to S5: given , compute and from (3.2); in S1, if , return the vector with coordinate when and otherwise, and if but , return ; in S2, with and , loop with changing bounds, taking and, if for some , replacing by and restarting, otherwise taking and, if for some , replacing by and restarting, otherwise stopping; in S3, on the final tightening box, ; in S4, when , take for every entry of the list and , and return the coordinatewise maximum of and all ; in S5, when , take and , and return the coordinatewise minimum of and all .
What Is Checked
The cases of the machine are stated over its control states, stacks of frames holding raw budgets, raw boxes, vectors and orientations; the width test, , and the basic run are stated for an environment that represents at top width and a raw box that represents a box of the game, and the folds for raw vectors that represent vectors of one box.
Each fold keeps, coordinate by coordinate, one of the two words it compares, and the library bounds its running result: after any prefix of the list has been folded in, the running vector has encoded size at most , where is the encoded size of the input.✦