The Setting
Let be a mean-payoff game on a set of vertices with integer edge weights , transformed weights and weight bound , and let be the top width of (2.1). The randomized solver is built from four procedures, Solve, Ask, Orient and OrientPlus, which call one another on solver inputs , made of a box with corners and in , a reference width , support weights and budgets . Two global parameters of (4.1) enter here, and ; is a power of two, so fair bits give a uniform index in .
The library runs the four procedures as one stack machine. Its states are calls of ten jobs, the four procedures and six auxiliary jobs, and returns of values to a stack of frames, and each step takes a random index below as an argument. A raw machine performs the same step on bit strings and unary counters packed into records.
The Stack Machine
A stack is a finite sequence of frames, with the empty stack and the stack with the frame on top; a frame holds what a job needs to continue once a subcall returns. A state of the machine is either a call state , a job to run above the stack , or a return state , a value handed back to . For an index , the step is the map on states that fixes every final state , hands a returned value to the frame on top by the resumption described below, (1)✦ and takes a call state either to a return of the job’s value to or to a call of a subjob above for a new frame . The resumption is likewise a return to or a call above with one or two new frames, computed from and the data in .✦ Frames come in kinds.
The jobs act on a box with corners and on budgets ; an orientation is a side, or , with a list of exception sets of vertices. Solve returns the small vector of for when the parameter of is below one, and the exact vector computed by the basic solver, the base procedure with step allowance , when has width at most . Otherwise it calls Tighten on , OrientPlus on the tightened box , Reweight on with the side and the exception sets of the orientation found (all three are described below), and Solve on capped on that side; it returns the coordinatewise minimum, for side , or maximum, for side , of the last answer and the reweighted ones. Ask returns the coordinatewise median of the answers of trials of Solve.
Each box carries a grid width , and the cap width of is the width of minus .
Update moves a center , a point of : it asks twice on a narrow box centered at , first with the budget reduced and then with reduced, and returns the average of the two answers clipped to . Centers applies Update times from and returns the centers it passes through. When has width at most , Orient returns the base orientation of . Otherwise it computes the centers from the midpoint of and the sets and of positive and negative displacement of , and returns side with exception set if , or else side with if , where is the measure the budgets put on vertex sets. Failing both, it calls Orient on a box centered at and appends and to the exception sets of the answer; this is the one place where the step reads . OrientPlus returns side when more than half of trials of Orient choose and side otherwise, with the exception sets of all trials.
The box centered at on which Orient is called again has the width of divided by .✦
Tighten asks on with reduced. If the answer has at some vertex , it calls Tighten on the box with corners and ; otherwise it asks again with reduced and, if that answer has at some , calls Tighten on the box with corners and , and else returns . For exception sets , Reweight asks on once for each with reweighted on and returns the list of answers; with side it reweights instead. The remaining two jobs run a given number of trials of Solve and of Orient, counting down and collecting the answers.
The Raw Machine
Raw data are bit strings and unary counters, lists of units in which a counter of length stands for ; is the length of a counter . A pack is a record of eight raw registers: budgets , a box , a counter , two vectors and , a list of vectors , an orientation and a list of orientations .✦ A raw orientation is a bit, true for , with a list of masks, one for each exception set.✦ A cell is a pack with a tag , a unary counter✦, and a raw state is a current cell above a raw stack , a list of cells.✦ The ten jobs carry the tags to , in the order Solve, Ask, trials of Solve, Update, Centers, Orient, trials of Orient, OrientPlus, Tighten, Reweight; the current cell of a raw return carries the tag ; the kinds of frame carry the tags to .
A pack holds a job when and of represent the budgets and the box of and the other registers of represent its remaining data: the number of trials or of updates still to run as the length of , the center in , the side and the exception sets of Reweight in .✦ A pack holds a value when the register of for the kind of represents it: a vector in , a list of vectors in , an orientation in , a list of orientations in , a box in .✦ A pack holds a frame when its registers represent the data that keeps.✦ A raw stack represents a stack frame by frame: the empty list represents , and represents when carries the tag of , holds and represents .✦ A raw state represents a state , written , by two rules: (2)✦
The raw machine reads a raw state together with a random counter , a unary counter whose length is the index of the step, and an environment , made of the arena of the game and four counters.✦ An environment represents the game when its arena is the code of the graph of with the transformed weights as binary words and its four counters have lengths , , and at least .✦ For each job the raw machine has a code ✦, and for each kind of frame a code , the two frames of Tighten that pass on a tightened box sharing one✦; each maps an environment, a random counter and a raw state to a raw state. The code of the frame where Orient compares and with takes the center of index from the list of centers in , and the midpoint of the box when there is none.
The Claim
Definition 1. Let be an environment, a random counter and a raw state. The resume code hands the raw state to the code of the frame named by the tag of the top cell of the stack: (3)✦ The raw step runs the code of the job named by the tag of the current cell: for a job and , (4)✦ On a return, , runs the code of the frame named by the tag of the top cell of the stack: for a frame with , (5)✦ On every other raw state, runs .✦
Theorem 1. Let be an environment that represents the game , let be a random counter, and let . If a raw state represents the call state in the sense of (2), then (6)✦ If the pack of a cell holds a frame , the pack of a cell holds a value and a raw stack represents a stack , then (7)✦ For every state and raw state with , (8)✦
In the paper, the result reads: Solve, Ask, Orient and OrientPlus are mutually recursive; a permitted solver input is with , , , , positive rational support weights and budgets ; a subcall inherits every parameter it does not mention, and a changed parameter belongs to that subcall alone; each subcall uses fresh fair bits independent of its history before the call; and repetitions on a fixed input are independent.
What Is Checked
The claims are stated over the step of (1) on the ten-job stack machine and its resumption , the raw step with the resume code and the codes and of jobs and frames, the representation (2) of states by raw states through packs that hold jobs, frames and values, and an environment that represents the game, with the index read off a random counter.