The Setting
The randomized quasipolynomial-time solver for a mean-payoff game with vertices runs on a Turing machine with a random tape and calls recursive procedures on boxes in , where is the vertex set of . It works with the transformed weight of each edge , an affine function of its weight , and with the top width , a number computed from and the largest absolute value of a transformed weight.
From and the run fixes at the start the global parameters (4.1): an integer that grows with the number of binary digits of ; the sample size , a power of two, so that fair bits of the random tape give a uniform index in ; and the number of independent trials. With them comes the basic step budget .
Before the first call, the machine reads the input code of , the fixed encoding of as a binary word, and writes these numbers in unary, as counters: a counter is a list of units, and a counter of length stands for the number . The counters for , , and , with the arena of , form an environment of the run, as defined below.
The Environment
An environment of the run is a tuple of an arena , with edge weights written as binary words, and four counters.✦
For a width , write and for the parameters and of computed from in place of . An environment represents a game with vertices and edges at width when is the arena of in which each edge carries a binary word of value , and the counters have the lengths (1)✦
The Claim
Theorem 1. Let be a mean-payoff game with vertices, top width and global parameters , and . From the input code of , the root computation forms the counter of the number of binary digits of plus two✦, and the argument, the product of a constant counter of length with : (2)✦ From these it forms the counter of ✦, the counter of , computed with as its bound, the trial base , a sixth power taken by repeated multiplication✦, and the counters ✦ and ✦. Then (3)✦ (4)✦ (5)✦ (6)✦ (7)✦ and, with the arena written from the code of , the environment formed by the root computation satisfies (8)✦
In the paper, the result reads: with , and from (2.1), fixed for the whole run, , , , , and , which only the analysis uses.
What Is Checked
The claim is stated over a mean-payoff game with vertices and its input code, its top width and global parameters , and , the counters , , , , and that the root computation forms from that code, and the environments of the run with the relation (1) of representing a game at a width.