In Section <ref>, we give a formal definition of parity games, and
more specifically the one-sink games used by Friedmann that we also
use for our construction.
We then give a high-level overview of how works for one-sink
games, since it operates more simply for one-sink games than for general games;
a more detailed technical exposition of for one-sink games can be
found in the appendix.
Our main reduction starts with a iterated circuit evaluation problem.
In Section <ref>, we describe our main construction of a parity
game that will implement iterated circuit iteration when strategy improvement
is run on it.
In Section <ref>, we describe the sequence of strategies that will go through as it implements the iterated circuit evaluation.
In Section <ref> we show that the construction works as claimed
and thus prove that is -hard for parity games.
In Section <ref>, we show how this result for extends
to strategy improvement algorithms for other games.
In Section <ref>, we show how to augment our construction with an
extra gadget to give -hardness results for .
In Section <ref>, we state some open problems.

§ PRELIMINARIES

§.§ Parity games

A parity game is defined by a tuple $G = (V, \veven, \vodd, E, \pri)$, where
$(V, E)$ is a directed graph. The sets $\veven$ and $\vodd$ partition $V$ into
the vertices belonging to player Even, and the vertices belonging to player Odd,
respectively. The priority function $\pri : V \rightarrow \{1, 2,
\dots\}$ assigns a positive natural number to each vertex. We assume that there
are no terminal vertices, which means that every vertex is required to have at
least one outgoing edge. The strategy improvement algorithm of
Vöge and Jurdziński also requires that we assume, without loss of
generality, that every priority is assigned to at most one vertex.

A strategy for player Even is a function that picks one outgoing edge for each
Even vertex. More formally, a deterministic positional strategy for Even
is a function $\sigma : \veven \rightarrow V$ such that, for each $v \in \veven$
we have that $(v, \sigma(v)) \in E$. Deterministic positional strategies for
player Odd are defined analogously. Throughout this paper, we will only consider
deterministic positional strategies, and from this point onwards, we will refer
to them simply as strategies. We use $\seven$ and $\sodd$ to denote the
set of strategies for players Even and Odd, respectively.

A play of the game is an infinite path through the game. More precisely,
a play is a sequence $v_0, v_1, \dots $ such that for all $i\in
\nats$ we have $v_i \in V$ and $(v_i, v_{i+1}) \in E$.
Given a pair of strategies $\sigma \in \seven$ and $\tau \in \sodd$, and a
starting vertex $v_0$, there is a unique play that occurs when the
game starts at $v_0$ and both players follow their respective strategies.
So, we define $\play(v_0, \sigma, \tau) = v_0, v_1, \dots$,
where for each $i \in \nats$ we have
$v_{i+1} = \sigma(v_i)$ if $v_i \in \veven$, and
$v_{i+1} = \tau(v_i)$ if $v_i \in \vodd$.

Given a play $\pi = v_0, v_1, \dots$ we define

\begin{equation*}
\maxio(\pi) = \max \{ p \; : \; \exists \text{ infinitely many } i \in \nats \text{ s.t. }
\pri(v_i) = p\},
\end{equation*}

to be the maximum priority that occurs infinitely often along $\pi$. We
say that a play $\pi$ is winning for player Even if $\maxio(\pi)$ is
even, and we say that $\pi$ is winning for Odd if $\maxio(\pi)$ is odd.
A strategy $\sigma \in \seven$ is a winning strategy for a vertex $v \in
V$ if, for every strategy $\tau \in \sodd$, we have that $\play(v, \sigma,
\tau)$ is winning for player Even. Likewise, a strategy $\tau \in \sodd$ is a
winning strategy for $v$ if, for every strategy $\sigma \in \seven$, we have
that $\play(v, \sigma, \tau)$ is winning for player Odd. The following
fundamental theorem states that parity games are positionally determined.

In every parity game, the set of vertices $V$ can be partitioned into
winning sets $(W_\text{0}, W_\text{1})$, where Even has a positional
winning strategy for all $v \in W_\text{0}$, and Odd has a positional winning
strategy for all $v \in W_\text{1}$.

The computational problem that we are interested in is, given a parity game,
to determine the partition $(W_\text{0}, W_\text{1})$.

As we have mentioned, the strategy improvement algorithm that we consider
requires that every priority is assigned to at most one vertex. This is
unfortunately a rather cumbersome requirement when designing more complex
constructions. To help with this, we define a shorthand for specifying
priorities. Let $c \in \nats$, let $i,l \in \{1, \dots, |V|\}$, let $j \in \{0,
1, 2\}$, and let $e \in \{0,1\}$. We define $\pp(c, i, l, j, e) = 6 \cdot |V|^2
\cdot c + 6 \cdot |V| \cdot i + 6 \cdot l + 2 \cdot j + e$.

The first four parameters should be thought of as a lexicographic ordering,
which determines how large the priority is. The final number $e$ determines
whether the priority is odd or even. Note that $\pp(c, i, l, j, e)$ is an
injective function, so if we ensure that the same set of arguments are never
used twice, then we will never assign the same priority to two different
vertices. One thing to note is that, since this priority notation is rather
cumbersome, it is not possible to use it in our diagrams. Instead, when we draw
parts of the construction, we will use representative priorities, which
preserve the order and parity of the priorities used in the gadgets, but not
their actual values.

§.§ Strategy improvement

We now describe the strategy improvement algorithm of Vöge and
Jurdziński [38] for solving parity games, which will be the
primary focus of this paper.

The algorithm assigns a valuation to each vertex $v$ under every pair of
strategies $\sigma \in \seven$ and $\tau \in \sodd$. Let $p$ be the largest
priority that is seen infinitely often along $\play(v, \sigma, \tau)$. Since
every priority is assigned to at most one vertex, there is a unique vertex $u$
with $\pri(u) = p$. We use this vertex to decompose the play: let $P(v, \sigma,
\tau)$ be the finite simple path that starts at $v$ and ends at $u$, and let
$C(v, \sigma, \tau)$ be the infinitely-repeated cycle that starts at $u$ and
ends at $u$.
We can now define the valuation function $\val_{\text{VJ}}^{\sigma, \tau}(v) = (p, S, d)$
where $p$ is as above and:

* $S$ is the set of priorities on the finite path that are strictly greater
than $p$:

\begin{equation*}
S = \{\pri(u) \; : \; u \in P(v, \sigma, \tau) \text{ and } \pri(u) > p\}.
\end{equation*}

* $d$ is the length of the finite path: $d = |P(v, \sigma, \tau)|$.

We now define an order over valuations. First we define an order $\preceq$ over
priorities: we have that $p \prec q$ if one of the following holds:

* $p$ is odd and $q$ is even.

* $p$ and $q$ are both even and $p < q$.

* $p$ and $q$ are both odd and $p > q$.

Furthermore, we have that $p \preceq q$ if either $p \prec q$ or $p = q$.

Next we define an order of the sets of priorities that are used in the second
component of the valuation. Let $P, Q \subset \nats$. We first define:

\begin{equation*}
\maxdiff(P, Q) = \max\bigl((P \setminus Q) \cup (Q \setminus P)\bigr).
\end{equation*}

If $d = \maxdiff(P, Q)$ then we define $P \sqsubset Q$ to hold if one of the
following conditions holds:

* $d$ is even and $d \in Q$.

* $d$ is odd and $d \in P$.

Furthermore, we have that $P \sqsubseteq Q$ if either $P = Q$ or $P \sqsubset

Finally, we can provide an order over valuations. We have that $(p, S, d)
\prec (p', S', d')$ if one of the following conditions holds:

* $p \prec p'$.

* $p = p'$ and $S \sqsubset S'$.

* $p = p'$ and $S = S'$ and $p$ is odd and $d < d'$.

* $p = p'$ and $S = S'$ and $p$ is even and $d > d'$.

Furthermore, we have that $(p, S, d) \preceq (p', S', d')$ if either $(p, S, d)
\prec (p', S', d')$ or $(p, S, d) = (p', S', d')$.

Best responses.

Given a strategy $\sigma \in \seven$, a best response against $\sigma$
is a strategy $\tau^{*} \in \sodd$ such that, for every $\tau \in \sodd$ and
every vertex $v$ we have: $\val_{\text{VJ}}^{\sigma, \tau}(v) \preceq \val_{\text{VJ}}^{\sigma,
\tau^{*}}(v)$.
Vöge and
Jurdziński proved the following properties.

For every $\sigma \in \seven$ a best response $\tau^*$ can be computed in
polynomial time.

We define $\br(\sigma)$ to be an arbitrarily chosen best response
strategy against $\sigma$. Furthermore, we define $\val_{\text{VJ}}^{\sigma}(v) =
\val_{\text{VJ}}^{\sigma, \br(\sigma)}(v)$.

Switchable edges.

Let $\sigma$ be a strategy and $(v, u) \in E$ be an edge such that $\sigma(v)
\ne u$. We say that $(v, u)$ is switchable in $\sigma$ if
$\val_{\text{VJ}}^{\sigma}(\sigma(v)) \prec \val_{\text{VJ}}^{\sigma}(u)$. Furthermore, we define a
most appealing outgoing edge at a vertex $v$ to be an edge $(v, u)$ such
that, for all edges $(v, u')$ we have $\val_{\text{VJ}}^{\sigma}(u') \preceq
\val_{\text{VJ}}^{\sigma}(u)$.

There are two fundamental properties of switchable edges that underlie the
strategy improvement technique. The first property is that switching any subset
of the switchable edges will produce an improved strategy. Let $\sigma$ be a
strategy, and let $W \subseteq E$ be a set of switchable edges in $\sigma$ such
that, for each vertex $v$, there is at most one edge of the form $(v, u) \in W$.
Switching $W$ in $\sigma$ creates a new strategy $\sigma[W]$ where for
all $v$ we have:

\begin{equation*}
\sigma[W](v) = \begin{cases}
u & \text{ if $(v, u) \in W$,} \\
\sigma(v) & \text{otherwise.}
\end{cases}
\end{equation*}

We can now formally state the first property.

Let $\sigma$ be a strategy and let $W \subseteq E$ be a set of switchable edges
in $\sigma$ such that, for each vertex $v$, there is at most one edge of the
form $(v, u) \in W$. We have:

* For every vertex $v$ we have $\val_{\text{VJ}}^{\sigma}(v) \preceq \val_{\text{VJ}}^{\sigma[W]}(v)$.

* There exists a vertex $v$ for which
$\val_{\text{VJ}}^{\sigma}(v) \prec \val_{\text{VJ}}^{\sigma[W]}(v)$.

The second property concerns strategies with no switchable edges. A
strategy $\sigma \in \seven$ is optimal if for every vertex $v$ and every
strategy $\sigma' \in \seven$ we have $\val_{\text{VJ}}^{\sigma'}(v) \preceq
\val_{\text{VJ}}^{\sigma}(v)$.

A strategy with no switchable edges is optimal.

Vöge and Jurdziński also showed that winning sets for both players
can be extracted from an optimal strategy.  If $\sigma$ is an optimal strategy,
then $W_\text{0}$ contains every vertex $v$ for which the first component of
$\val_{\text{VJ}}^{\sigma}(v)$ is even, and $W_\text{1}$ contains every vertex $v$ for which
the first component of $\val_{\text{VJ}}^{\sigma}(v)$ is odd. Hence, to solve the parity
game problem, it is sufficient to find an optimal strategy.

The algorithm.
The two properties that we have just described give rise to an obvious
strategy improvement algorithm that finds an optimal strategy.
The algorithm begins by selecting an arbitrary strategy
$\sigma \in \seven$. In each iteration, the algorithm
performs the following steps:

* If there are no switchable edges, then terminate.

* Otherwise, select a set $W \subseteq E$ of switchable edges in $\sigma$
such that, for each vertex $v$, there is at most one edge of the form $(v, u)
\in W$.

* Set $\sigma := \sigma[W]$ and go to step 1.

By the first property, each iteration of this algorithm produces a strictly
better strategy according to the $\prec$ ordering, and therefore the algorithm
must eventually terminate. However, the algorithm can only terminate when there
are no switchable edges, and therefore the second property implies that the
algorithm will always find an optimal strategy.

The algorithm given above does not specify a complete algorithm, because it does
not specify which subset of switchable edges should be chosen in each
iteration. Indeed, there are many variants of the algorithm that use a variety
of different switching rules. In this paper, we focus on the greedy
all-switches switching rule. This rule switches every vertex that has a
switchable edge, and if there is more than one switchable edge, it arbitrarily
picks one of the most appealing edges.

One-sink games.

Friedmann observed that, for the purposes of showing lower bounds, it is
possible to simplify the Vöge-Jurdziński algorithm by restricting the input
to be a one-sink game [12].

A one-sink parity game contains a sink vertex $s$ such that $\pri(s) = 1$. An
even strategy $\sigma \in \seven$ is called a terminating strategy if,
for every vertex $v$, the first component of $\val_{\text{VJ}}^{\sigma}(v)$ is $1$.
Formally, a parity game is a one-sink parity game if:

* There is a vertex $s \in V$ such that $\pri(s) = 1$, and $(s, s)$ is the
only outgoing edge from $s$. Furthermore, there is no vertex $v$ with $\pri(v) =

* All optimal strategies are terminating.

Now, suppose that we apply Vöge-Jurdziński algorithm, and furthermore
suppose that the initial strategy is terminating. Since the initial and optimal
strategies are both terminating, we have that, for every strategy $\sigma$
visited by the algorithm and every vertex $v$, the first component of
$\val_{\text{VJ}}^{\sigma}(v) = 1$, and so it can be ignored. Furthermore, since there is no
vertex with priority $0$, the second component of $\val_{\text{VJ}}^{\sigma}(v)$ must be
different from the second component of $\val_{\text{VJ}}^{\sigma}(u)$, for every $v, u \in
V$. Therefore, the third component of the valuation can be ignored.

Thus, for a one-sink game, we can define a simplified version of the
Vöge-Jurdziński algorithm that only uses the second component. So, we define
$\val^{\sigma}(v)$ to be equal to the second component of
$\val_\text{VJ}^\sigma(v)$, and we carry out strategy improvement using the
definitions given above, but with $\val^{\sigma}(v)$ substituted for
$\val_\text{VJ}^\sigma(v)$. Note, in particular, that in this strategy
improvement algorithm, and edge $(v, u)$ is switchable in $\sigma$ if
$\val^{\sigma}(\sigma(v)) \sqsubset \val^{\sigma}(u)$.

In our proofs, we will frequently want to determine the maximum difference
between two valuations. For this reason, we introduce the following notation.
For every strategy $\sigma$, and every pair of vertices $v, u \in V$, we define
$\maxdiff^\sigma(v, u) = \maxdiff(\val^{\sigma}(v), \val^{\sigma}(u))$.

§.§ Circuit iteration problems

The problems.
To prove our -completeness results, we will reduce from circuit
iteration problems, which we now define. A circuit iteration instance is
a triple $(F, B, z)$, where:

* $F : \{0, 1\}^n \rightarrow \{0, 1\}^n$ is a function represented as a
boolean circuit $C$,

* $B \in \{0, 1\}^n$ is an initial bit-string, and

* $z$ is an integer such that $1 \le z \le n$.

We use standard notation for function iteration: given a bit-string $B \in
\{0,1\}^n$, we recursively define $F^{1}(B) = F(B)$, and $F^{i}(B) =
F(F^{i-1}(B))$ for all $i > 1$.

We now define two problems that will be used as the starting point for our
reduction. Both are decision problems that take as input a circuit iteration
instance $(F, B, z)$.

* $\bitswitch(F, B, z)$: decide whether there exists an even $i \le 2^n$
such that the $z$-th bit of $F^{i}(B)$ is $1$.

* $\circuitvalue(F, B, z)$: decide whether the $z$-th bit of $F^{2^n}(B)$ is $1$.

The requirement for $i$ to be even in $\bitswitch$ is a technical requirement
that is necessary in order to make our reduction to strategy improvement work.

The fact that these problems are -complete should not be too surprising,
because $F$ can simulate a single step of a space-bounded Turing machine, so
when $F$ is iterated, it simulates a run of the space-bounded Turing machine.
The following lemma was shown in [10].

$\bitswitch$ and $\circuitvalue$ are -complete.

For the purposes of our reduction, we must make some assumptions about the
format of the circuits that represent $F$. Let $C$ be a boolean circuit with $n$
input bits, $n$ output bits, and $k$ gates. We assume, w.l.o.g., that
all gates are or-gates or not-gates. The circuit will be represented as
a list of gates indexed $1$ through $n+k$. The indices $1$ through $n$
represent the $n$ inputs to the circuit. Then, for each $i > n$, we have:

* If gate $i$ is an or-gate, then we define $\inp_1(i)$ and $\inp_2(i)$ to
give the indices of its two inputs.

* If gate $i$ is a not-gate, then we define $\inp(i)$ to give the index of
its input.

The gates $k+1$ through $k + n$ correspond to the $n$ output bits of the
circuit, respectively. For the sake of convenience, for each input bit $i$, we
define $\inp(i) = k+i$, which indicates that, if the circuit is applied to its
own output, input bit $i$ should copy from output bit $\inp(i)$. Moreover, we
assume that the gate ordering is topological. That is, for each or-gate $i$ we
assume that $i > \inp_1(i)$ and $i > \inp_2(i)$, and we assume that for each
not-gate $i$ we have $i > \inp(i)$.

For each gate $i$, let $d(i)$ denote the depth of gate $i$, which is the
length of the longest path from $i$ to an input bit. So, in particular, the
input bits are at depth $0$. Observe that we can increase the depth of a gate by
inserting dummy or-gates: given a gate $i$, we can add an or-gate $j$ with
$\inp_1(j) = i$ and $\inp_2(j) = i$, so that $d(j) = d(i)+1$. We use this fact
in order to make the following assumptions about our circuits:

* For each or-gate $i$, we have $d(\inp_1(i)) = d(\inp_2(i))$.

* There is a constant $c$ such that, for every output bit $i \in \{k+1,
k+n\}$, we have $d(i) = c$.

From now on, we assume that all circuits that we consider satisfy these
properties. Note that, since all outputs gates have the same depth, we can
define $d(C) = d(k+1)$, which is the depth of all the output bits of the

Given an input bit-string $B \in \{0, 1\}^n$, the truth values of each of the
gates in $C$ are fixed. We define $\eval(B, i) = 1$ if gate $i$ is true for
input $B$, and $\eval(B, i) = 0$ if gate $i$ is false for input $B$.

Given a circuit $C'$, we define the negated form of $C'$ to be a
transformation of $C'$ in which each output bit is negated. More formally, we
transform $C'$ into a circuit $C$ using the following operation: for each output
bit $n+i$ in $C'$, we add a gate $n+k+i$ with $\inp(n+k+i) = n+i$.

§ THE CONSTRUCTION

Our goal is to show that $\edgeswitch$ is -complete by reducing from the
circuit iteration problem $\bitswitch$. Let $(F, B, z)$ be the input to the
circuit iteration problem, and let $C$ be the negated form of the circuit that
computes $F$. Throughout this section, we will use $n$ as the bit-length of $B$,
and $k = |C|$ as the number of gates used in $C$. We will use $\org$, $\notg$,
and $\inputg$ to denote the set of or-gates, not-gates, and input/output-gates,

We will force greedy all-switches strategy improvement to compute $F^i(B)$ for
each value of $i$. To do this, we will represent each gate in $C$ by a gadget,
and applying strategy improvement to these gadgets will cause the correct output
values for each gate to be computed. One complication is that, after computing
$F(B)$, the circuit must then copy the output values back to the input gates. To
resolve this issue, the construction contains two entire copies of the circuit,
numbered $0$ and $1$, which take turns in computing $F$. First
circuit $0$ computes $F(B)$, then circuit $1$ computes $F(F(B))$, then
circuit $0$ computes $F(F(F(B)))$, and so on.

There will be a specific edge $e$ in the construction that is switched if and
only if the $z$-th bit of $F^i(B)$ is $1$ for some even $i$. The technical
requirement for $i$ to be even is explained by the fact that there are two
copies of the circuit, and each copy only computes $F^i(B)$ for either the
case where $i$ is even or the case where $i$ is odd.

The construction also uses Friedmann's exponential-time examples as a
clock. Friedmann's examples are designed to force greedy all-switches
strategy improvement to mimic a binary counter. The construction contains two
entire copies of Friedmann's example, so that each copy of the circuit is
equipped with its own clock. The fundamental idea is that, each time the clock
ticks, i.e., each time the binary counter advances to the next bit-string, the
circuit will start computing $F$. Thus the two clocks must be out of phase
relative to one another, so that the two circuits correctly alternate.

In the rest of this section, we describe the construction. We begin by giving an
overview of Friedmann's example, both because it plays a key role in our
construction, and because the gate gadgets in our circuits are a
modification of the bit-gadget used by Friedmann. We then move on to describe
the gate gadgets, and how they compute the function $F$.

§.§ Friedmann's exponential-time example

In this section we give an overview of some important properties of Friedmann's
exponential-time examples. In particular, we focus on the properties that will
be important for our construction. A more detailed description of the example
can be found in Friedmann's original paper [12].

The example works by forcing greedy all-switches strategy improvement to
simulate an $n$ bit binary counter. It consists of two components: a bit
gadget that is used to store one of the bits of the counter, and a
deceleration lane that is used to ensure that the counter correctly moves
from one bit-string to the next.

The deceleration lane. Friedmann's example contains one copy of
the deceleration lane. The deceleration lane has a specified length $m$, and
Figure <ref> shows an example of a deceleration lane of length $4$.
Friedmann's construction contains one copy of the deceleration lane of
length $2n$. Figure <ref> shows a deceleration lane of length $4$.
Remember that our diagrams use representative priorities, which preserve the
order and parity of the priorities used, but not their values.

[node distance=1.8cm]
[even] (c) $t_0$
[even,left of=c] (t1) $t_1$
[even,left of=t1] (t2) $t_2$
[even,left of=t2] (t3) $t_3$

[even,left of=t3] (t5) $t_4$

[even,above of=t1] (a1) $a_1$
[even,above of=t2] (a2) $a_2$
[even,above of=t3] (a3) $a_3$
[even,above of=t5] (a5) $a_4$

(t5) edge (t3)

(t3) edge (t2)
(t2) edge (t1)
(t1) edge (c)

(a5) edge (t5)
(a3) edge (t3)
(a2) edge (t2)
(a1) edge (t1)

in c, t1, t2, t3, t5

[even,draw,minimum size=0.8cm] (1) at ($(\x) - (0.5,1.8)$) $r$;
[even,draw,minimum size=0.8cm] (2) at ($(\x) - (-0.5,1.8)$) $s$;

() edge (1)
() edge (2)

Friedmann's deceleration lane for length $4$.

A key property of the deceleration lane is that greedy all-switches strategy
improvement requires $m$ iterations to find the optimal strategy. Consider an
initial strategy in which each vertex $t_i$ uses the edge to $r$, and that the
valuation of $r$ is always larger than the valuation of $s$. First note that,
since there is a large even priority on $t_0$, the optimal strategy is for every
vertex $t_i$, with $i \ge 1$, to use the edge to $t_{i-1}$. However, since the
vertices $t_i$ with $i \ge 1$ are all assigned odd priorities, in the initial
strategy only the edge from $t_1$ to $t_0$ is switchable. Furthermore, once this
edge has been switched, only the edge from $t_2$ to $t_1$ is switchable. In this
way, the gadget ensures that $m$ iterations are required to move from the
initial strategy to the optimal strategy for this gadget.

Another important property is that the gadget can be reset. This is
achieved by having a single iteration in which the valuation of $s$ is much
larger than the valuation of $r$, followed by another iteration in which the
valuation of $r$ is much larger than the valuation of $s$. In the first
iteration all vertices $t_i$ switch to $s$, and in the second iteration all
vertices switch back to $r$. Note that after the second iteration, we have
arrived back at the initial strategy described above.

The bit gadget.

The bit gadget is designed to store one bit of a binary counter. The
construction will contain $n$ copies of this gadget, which will be indexed $1$
through $n$. Figure <ref> gives a depiction of a bit gadget with index

[node distance=3cm,font=]
[even,align=center] (d) $d_i$
[odd,right of=d,align=center] (e) $e_i$
[even,right of=e,align=center] (f) $f_i$
[even,above of=e,align=center] (h) $h_i$
[even,above of=f,align=center] (g) $g_i$
[even,above of=h,align=center] (k) $k_i$

[even,below right=2cm and 3.5cm of d] (a_1) $a_1$;
[even,left of=a_1] (a_2) $a_2$;
[left of=a_2] (a_3) $\dots$;
[even,left of=a_3] (a_4) [align=center] $a_{2i}$;

[even,above left=0.5cm and 2cm of k] (g_1) $g_{i+1}$;
[even,below left=0.5cm and 2cm of k] (g_2) $g_n$;
[even,below left=2.5cm and 2cm of k] (g_n) $x$;

[left=2.45cm of k] (dots2) $\vdots$;

[even,left=2cm of d] (r) $r$;
[even,above left=0.45cm and 2cm of d] (s) $s$;

(g) edge (f)
(g) edge (k)
(f) edge (e)
(e) edge (h)
(h) edge (k)
(e) edge [bend left] (d)
(d) edge [bend left] (e)

(d) edge (a_4)
(d) edge (a_2)
(d) edge (a_1)

(k) edge (g_1)
(k) edge (g_2)
(k) edge (g_n)

(d) edge (r)
(d) edge (s)

An example of Friedman's bit gadget.

The current value of the bit for index $i$ is represented by the choice that the current
strategy makes at $d_i$. More precisely, for every strategy $\sigma$ we have:

* If $\sigma(d_i) = e_i$, then bit $i$ is $1$ in $\sigma$.

* If $\sigma(d_i) \ne e_i$, then bit $i$ is $0$ in $\sigma$.

The Odd vertex $e_i$ plays a crucial role in this gadget. If
$\sigma(d_i) = e_i$, then Odd's best response is to use edge $(e_i,h_i)$, to
avoid creating the even cycle between $d_i$ and $e_i$. On the other hand, if
$\sigma(d_i) \ne e_i$, then Odd's best response is to use $(e_i,d_i)$, to avoid
seeing the large even priority at $h_i$.

One thing to note is that, in the case where $\sigma(d_i) \ne e_i$, the edge to
$e_i$ is always switchable. To prevent $d_i$ from immediately switching to
$e_i$, we must ensure that there is always a more appealing outgoing edge from
$e_i$, so that the greedy all-switches rule will switch that edge instead. The
edges from $d_i$ to the deceleration lane provide this. Once $t_1$ has switched
to $t_0$, the edge from $d_i$ to $a_{1}$ becomes more appealing than the edge to
$e_i$, once $t_2$ has switched to $t_1$, the edge from $d_i$ to $a_{2}$ becomes
more appealing than the edge to $e_i$, and so on. In this way, we are able to
prevent $d_i$ from switching to $e_i$ for $2i$ iterations by providing outgoing
edges to the first $2i$ vertices of the deceleration lane.

The vertices $s$ and $r$.

The vertex $s$ has outgoing edges to every vertex $f_i$ in the bit gadgets, and
the vertex $r$ has outgoing edges to every vertex $g_i$ in the bit gadgets. If
$i$ is the index of the least significant $1$ bit, then $s$ chooses the edge to
$f_i$ and $r$ chooses the edge to $g_i$. The priority assigned to $r$ is larger
than the priority assigned to $s$, which ensures that the valuation of $r$ is
usually larger than the valuation of $s$, as required to make the deceleration
lane work.

When the counter moves from one bit-string to the next, the index least
significant $1$ changes to some $i' \ne i$. The vertex $s$ switches to $f_{i'}$
one iteration before the vertex $r$ switches to $g_{i'}$. This creates the
single iteration in which the valuation of $s$ is larger than the valuation
of $r$, which resets the deceleration lane.

Simulating a binary counter.

To simulate a binary counter, we must do two things. Firstly, we must ensure
that if the counter is currently at some bit-string $\C \in \{0, 1\}^n$, then
the least significant zero in $\C$ must be flipped to a one. Secondly,
once this has been done, all bits whose index is smaller than the least
significant zero must be set to $0$. If these two operations are always
performed, then strategy improvement will indeed count through all binary

The least significant zero is always flipped because each bit $i$ has $2i$ edges
to the deceleration lane. Since the purpose of the deceleration lane is to
prevent the vertex $d_i$ switching to $e_i$, the vertex $d_{i'}$ where $i'$ is
the index of the least significant zero, is the first to run out of edges, and
subsequently switch to $e_{i'}$.

Once this has occurred, all bits with index smaller than the least significant
zero are set to $0$ due to the following chain of events. The vertex $s$
switches $f_{i'}$,  and then the vertex $d_{i''}$ in all bits with index $i'' <
i'$ will be switched to $s$. Since $d_{i''}$ no longer uses the edge to
$e_{i''}$, the bit has now been set to $0$.

Our modifications to Friedmann's example.

In order to use Friedmann's example as a clock, we make a few minor adjustments
to it. Firstly, we make the deceleration lane longer. Friedmann's example uses a
deceleration lane of length $2n$, but we use a deceleration lane of length
$\lale$. Furthermore, while the vertex $d_i$ has outgoing edges to each $a_j$
with $j \le 2i$ in Friedmann's version, in our modified version the vertex $d_i$
has outgoing edges to each $a_j$ with $j \le 2i + 2k + 2n + 6$.

The reason for this is that Friedmann's example can move from one bit-string to
the next in as little as four iterations, but we need more time in order to
compute the circuit $F$. By making the deceleration lane longer, we slow down
the construction, and ensure that there are at least $2k + 2n + 6$ iterations
before the clock moves from one bit-string to the next.

The second change that we make is to change the priorities, because we need to
make room for the gadgets that we add later. However, we have not made any
fundamental changes to the priorities: the ordering of priorities between the
vertices and their parity is maintained. We have simply added larger gaps
between them.

The following table specifies the version of the construction that we use.
Observe that two copies are specified: one for $j = 0$ and the other
for $j = 1$. Furthermore, observe that the vertex $x$ will be the sink in our
one-sink game.

Vertex     Conditions      Edges      Priority     Player

$t_0^j$     $j \in \{0, 1\}$     $r^j$, $s^j$     $\pp(2, 0, 2k+4n+4, j, 0)$     Even

$t_l^j$     $j \in \{0, 1\}$, $1 \le l \le \lale$     $r^j$, $s^j$, $t^j_{l-1}$
$\pp(2, 0, l, j, 1)$     Even

$a_l^j$     $j \in \{0, 1\}$, $1 \le l \le \lale$     $t^j_l$     $\pp(2, 0, l
+1, j,
0)$     Even

$d^j_i$     $j \in \{0, 1\}$, $1 \le i \le n$     $e^j_i$, $s^j$, $r^j$,     $\pp(1, i, 0, j, 1)$     Even

$a^j_l $ for $1 \le l \le \laletwo + 2i$

$e^j_i$     $j \in \{0, 1\}$, $1 \le i \le n$     $h^j_i$, $d_i$     $\pp(1, i, 1, j, 0)$

$g^j_i$     $j \in \{0, 1\}$, $1 \le i \le n$     $f^j_i$     $\pp(1, i, 2, j, 1)$

$k^j_i$     $j \in \{0, 1\}$, $1 \le i \le n$     $x$, $g^j_l$, for $i < l \le
n$     $\pp(8, i, 0, j, 1)$     Even

$f^j_i$     $j \in \{0, 1\}$, $1 \le i \le n$     $e^j_i$     $\pp(8, i, 1, j, 1)$

$h^j_i$     $j \in \{0, 1\}$, $1 \le i \le n$     $k^j_i$     $\pp(8, i, 2, j, 0)$

$s^j$     $j \in \{0, 1\}$     $x$, $f^j_l$ for $1 \le l \le n$     $\pp(7, 0, 0,
j, 0)$     Even

$r^j$     $j \in \{0, 1\}$     $x$, $g^j_l$ for $1 \le l \le n$     $\pp(7, 0, 1,
j, 0)$     Even

$x$          $x$     $\pp(0, 0, 0, 0, 1)$     Even

§.§ Our construction

For each gate in the construction, we design a gadget that computes the output
of that gate. The idea is that greedy all-switches strategy improvement will
compute these gates in depth order. Starting from an initial strategy, the first
iteration will compute the outputs for all gates of depth $1$, the next
iteration will use these outputs to compute the outputs for all gates of depth
$2$, and so on. In this way, after $k$ iterations of strategy improvement, the
outputs of the circuit will have been computed. We then use one additional
iteration to store these outputs in an input/output gadget.

Strategy improvement valuations will be used to represent the output of each
gate. Each gate $i$ has a state $o^j_i$, and the valuation of this state will
indicate whether the gate evaluates to true or false. In particular the
following rules will be followed.

In every strategy $\sigma$ we have the following properties.

* Before the gate has been evaluated, we will have $\val^\sigma(o^j_i)
\sqsubset \val^{\sigma}(r^j)$.

* If the gate has been evaluated to false, we will continue to have
$\val^\sigma(o^j_i) \sqsubset \val^{\sigma}(r^j)$.

* If the gate has been evaluated to true, then we will instead have
$\val^\sigma(r^j) \sqsubset \val^{\sigma}(o^j_i)$, and $\maxdiff^{\sigma}(r^j,
o^j_i)$ will be a large even priority.

The input/output gadgets are connected to both circuits, and these
gadgets have two modes.

* When circuit $j$ is computing, the gadget is in output mode, where
it reads the output of circuit $j$ and stores it.

* When circuit $1-j$ is computing, the gadget is in input mode, where
it outputs the value that was stored from the previous computation into circuit

Therefore, the gates of depth $1$ in circuit $j$ read their input from the
input/output gadgets in circuit $1-j$, while the input/output gadgets in circuit
$j$ read their input from the outputs of circuit $j$. To formalise this, we
introduce the following notation.
For every $\notg$-gate, we define $\inputstate(i,j)$ as follows:

\begin{equation*}
\inputstate(i,j) = \begin{cases}
o^{1-j}_{\inp(i)} & \text{if $d(i) = 1$,} \\
o^j_{\inp(i)} & \text{if $d(i) > 1$.}
\end{cases}
\end{equation*}

For every $\org$-gate, and every $l \in \{1, 2\}$, we define
$\inputstate(i,j,l)$ as follows:

\begin{equation*}
\inputstate(i,j,l) = \begin{cases}
o^{1-j}_{\inp_l(i)} & \text{if $d(i) = 1$,} \\
o^j_{\inp_l(i)} & \text{if $d(i) > 1$.}
\end{cases}
\end{equation*}

The clocks.
As we have mentioned, we use two copies of Friedmann's example to act as clocks
in our construction. These clocks will be used to drive the computation. In
particular, the vertices $r^j$ and $s^j$ will play a crucial role in
synchronising the two circuits. As described in the previous section, when the
clock advances, i.e., when it moves from one bit-string to the next, there
is a single iteration in which the valuation of $s^j$ is much larger than the
valuation of $r^j$. This event will trigger the computation.

* The iteration in which the valuation of $s^0$ is much larger than the
valuation of $r^0$ will trigger the start of computation in circuit $0$.

* The iteration in which the valuation of $s^1$ is much larger than the
valuation of $r^1$ will trigger the start of computation in circuit $1$.

In order for this approach to work, we must ensure that the two clocks are
properly synchronised. In particular, the gap between computation starting in
circuit $j$ and computation starting in circuit $1-j$ must be at least $k+3$, to
give enough time for circuit $j$ to compute the output values, and for these
values to be stored. We now define notation for this purpose. First we define
the number of iterations that it takes for a clock to move from bit-string $\C$
to $\C + 1$. For every bit-string $\C \in \{0, 1\}^n$, we define $\lsz(\C)$ to
be the index of the least significant zero in $\C$: that is, the smallest
index $i$ such that $\C_i = 0$. For each $\C \in \{0, 1\}^n$, we define:

\begin{equation*}
\length(\C) = \Bigl( \laletwo \Bigr) + 2\lsz(\C) + 5.
\end{equation*}

This term can be understood as the length of the deceleration lane to which all
bits in the clock have edges, plus the number of extra iterations it takes to
flip the least-significant zero, plus five extra iterations needed to transition
between the two bit-strings.

Next we introduce the following delay function, which gives the amount of
time each circuit spends computing. For each $j \in \{0, 1\}$ and each $\C \in
\{0, 1\}^n$, we define:

\begin{equation*}
\delay(j, \C) = \begin{cases}
\Bigl( d(C) + 3 \Bigr) + 2n & \text{if $j = 0$,} \\
\Bigl( d(C) + 3 \Bigr) + 2 \cdot \lsz(\C) + 5 & \text{if $j = 1$.}
\end{cases}
\end{equation*}

Circuit $1$ starts computing $\delay(0, \C)$ iterations after Circuit $0$
started computing, and Circuit $0$ starts computing $\delay(1, \C)$ iterations
after circuit $1$ started computing. Observe that $\delay(0, \C) + \delay(1, \C)
= \length(\C)$, which ensures that the two circuits do not drift relative to
each other. The term $d(C) + 3$ in each of the delays ensures that there is
always enough time to compute the circuit, before the next circuit begins the
subsequent computation.

Or gates.
The gadget for a gate $i \in \org$ is quite simple, and is shown in
Figure <ref>. It is not difficult to verify that the three rules given in
Property <ref> hold for this gate. Before both inputs have been
evaluated, the best strategy at $o^j_i$ is to move directly to $r^j$, since the
valuation of both inputs is lower than the valuation of $r^j$. Note that in this
configuration the valuation of $o^j_i$ is smaller than the valuation of $r^j$,
since $o^j_i$ has been assigned an odd priority.

Since, by assumption, both inputs have the same depth, they will both be
evaluated at the same time. If they both evaluate to false, then nothing changes
and the optimal strategy at $o^j_i$ will still be $r^j$. This satisfies the
second rule. On the other hand, if at least one input evaluates to true, then
the optimal strategy at $o^j_i$ is to switch to the corresponding input states.
Since the valuation of this input state is now bigger than $r^j$, the valuation
of $o^j_i$ will also be bigger than $r^j$, so the third rule is also satisfied.

[node distance=1cm,font=]
[even] (o) $o^j_i$
[even] (r) [left=1cm of o] $r^j$;
[even] (s) [above left=1cm and 1cm of o] $s^j$;
[even] (i1) [below left=1cm and 0.5cm of o] $o^j_{\inp_1(i)}$;
[even] (i2) [below right=1cm and 0.5cm of o] $o^j_{\inp_2(i)}$;

(o) edge (r)
(o) edge (s)
(o) edge (i1)
(o) edge (i2)

Vertex     Conditions      Edges      Priority     Player

$o^j_i$     $j \in \{0, 1\}$,     $s^j$, $r^j$,
$\pp(4, i, 0, j, 1)$     Even

$i \in \org$    $\inputstate(i,j,1)$

The gate.

Not gates. The construction for a gate $i \in \notg$ is more
involved. The gadget is quite similar to a bit-gadget from Friedmann's
construction. However, we use a special modified deceleration lane, which
is shown in Figure <ref>.

[node distance=1.8cm,font=]
[] (t1) $\dots$;
[even,left of=t1] (t2) $t^j_{i,d(i)-1}$;
[even,left of=t2] (t3) $t^j_{i,d(i)}$;
[even,left of=t3] (t4) $t^j_{i,d(i)+1}$;
[left of=t4] (t5) $\dots$;

[even,above of=t2] (a2) $a^j_{i,d(i)-1}$;
[even,above of=t3] (a3) $a^j_{i,d(i)}$;
[even,above of=t4] (a4) $a^j_{i,d(i)+1}$;

[even,below of=t3,node distance=2.1cm] (v) $o^j_{\inp(i)}$;

(t5) edge (t4)
(t4) edge (t3)
(t2) edge (t1)

(a4) edge (t4)
(a3) edge (t3)
(a2) edge (t2)

(t3) edge (v)

in t2, t4

[even,draw,minimum size=0.8cm] (1) at ($(\x) - (0.5,2.3)$) $r^j$;
[even,draw,minimum size=0.8cm] (2) at ($(\x) - (-0.5,2.3)$) $s^j$;

() edge (1)
() edge (2)

Modified deceleration lane for a gate $i$ in circuit $j$.

The modified deceleration lane is almost identical to Friedmann's deceleration
lane, except that state $t^j_{i, d(i)}$ is connected to the output state of the
input gate. The idea is that, for the first $d(i) - 1$ iterations the
deceleration lane behaves as normal. Then, in iteration $d(i)$, the input gate
is evaluated. If it evaluates to true then the valuation of $t^j_{i, d(i)}$ will
be large, and the deceleration lane continues switching as normal. If it evaluates to
false, then the valuation of $t^j_{i, d(i)}$ will be low, and the deceleration
lane will stop switching.

[node distance=2.5cm,font=]
[even,align=center] (d) $d^j_i$
[odd,right of=d,align=center] (e) $e^j_i$
[even,right of=e,align=center] (f) $o^j_i$
[even,above=1.5cm of e,align=center] (k) $h^j_i$

[even,below right=2.5cm and 2.5cm of d] (a_1) $a^j_{i,1}$;
[even,left of=a_1,node distance=2cm] (a_2) $a^j_{i,2}$;
[left of=a_2,node distance=2cm] (a_3) $\dots$;
[even,left of=a_3,node distance=2cm] (a_4) [align=center] $a^j_{i,m}$;

[even,left=2cm of d] (s) $s^j$;
[even,above left=1.5cm and 2cm of d] (r) $r^j$;

(f) edge (e)
(e) edge (k)
(e) edge [bend left] (d)
(d) edge [bend left] (e)

(d) edge (a_4.north)
(d) edge (a_2.north)
(d) edge (a_1.north)

(k) edge (r)

(d) edge (r)
(d) edge (s)

gate with index $i$ in circuit $j$.

The gate gadget, which is shown in Figure <ref> is a simplified
bit gadget that is connected to the modified deceleration lane. As in
Friedmann's construction, the strategy chosen at $d^j_i$ will represent the
output of the gate. In a strategy $\sigma$, the gate outputs $1$ if
$\sigma(d^j_i) = e^j_i$, and it outputs $0$ otherwise. As we know, Friedmann's
bit gadget is distracted from switching $d^j_i$ to $e^j_i$ by the deceleration
lane. By using the modified deceleration lane, we instead obtain a gate.
Since the deceleration lane keeps on switching if and only if the input gate
evaluates to true, the state $d^j_i$ will switch to $e^j_i$ in iteration $d(i)$
if and only if the input gate evaluates to false. This is the key property that
makes the gate work.

To see that the three rules specified in Property <ref> are
respected, observe that there is a large odd priority on the state $o^j_i$, and
an even larger even priority on the state $h^j_i$. This causes the valuation of
$o^j_i$ will only be larger than the valuation of $r^j$ if and only if $d^j_i$
chooses the edge to $e^j_i$, which only happens when the gate evaluates to true.

Finally, when the computation in circuit $j$ begins again, the -gate is
reset. This is ensured by giving the vertex $d^j_i$ edges to both $s^j$ and
$r^j$. So, when the clock for circuit $j$ advances, no matter what strategy is
currently chosen, the vertex $d^j_i$ first switches to $s^j$, and then to $r^j$,
and then begins switching to the deceleration lane.

The following table formally specifies the gate gadgets that we use in the

Vertex     Conditions      Edges      Priority     Player

$t^j_{i, 0}$     $j \in \{0, 1\}$, $i\in \notg$     $r^j$, $s^j$     $\pp(5, i,
2k+4n+4, j, 0)$     Even

$t_{i,l}^j$     $j \in \{0, 1\}$, $i\in \notg$,     $r^j$, $s^j$, $t^j_{i, l-1}$     $\pp(5, i, l, j, 1)$     Even

$1 \le l \le \lale$, and $l \ne d(i)$

$t_{i,d(i)}^j$     $j \in \{0, 1\}$, $i\in \notg$     $\inputstate(i,j)$     $\pp(5, i,
d(i), j, 1)$     Even

$a_{i,l}^j$     $j \in \{0, 1\}$, $i \in \notg$,      $t_{i,l}$     $\pp(5, i, l+1, j, 0)$     Even

$1 \le l \le \lale$, and $l \ne d(i)$

$a_{i,d(i)}^j$     $j \in \{0, 1\}$, $i \in \notg$
$t_{i,d(i)}$     $\pp(4, i, 0, j, 0)$     Even

$d^j_i$     $j \in \{0, 1\}$, $i \in \notg$     $s^j$, $r^j$, $e^j_i$, $a^j_{i,l}$
$\pp(4,i,0,j,1)$     Even

for $1 \le l \le \lale$

$e^j_i$     $j \in \{0, 1\}$, $i \in \notg$     $h^j_i$, $d^j_i$     $\pp(4,i,1,j,0)$

$o^j_i$     $j \in \{0, 1\}$, $i \in \notg$     $e^j_i$     $\pp(6,i,0,j,1)$     Even

$h^j_i$     $j \in \{0, 1\}$, $i \in \notg$     $r^j$     $\pp(6,i,1,j,0)$     Even

[node distance=1cm,font=]
[even] (orig) ;
[even] (origr) [below left=2cm and 0.5cm of orig] $r^j$;
[even] (origs) [below right=2cm and 0.5cm of orig] $s^j$;

(orig) edge (origr)
(orig) edge (origs)

[snake=snake,draw,thick,line after snake=0.2cm,->]
($(orig) + (3, -1.4)$) – ($(orig) + (6, -1.4)$)

[even] (new) [right=8cm of orig] ;
[even] (newy) [below left= 2cm and 0.5cm of new] $y^j: 4$;
[even] (newz) [below right= 2cm and 0.5cm of new] $z^j: 2$;
[even] (news) [below right= 2cm and 0.5cm of newz] $s^j$;
[even] (newr) [below left= 2cm and 0.5cm of newz] $r^j$;
[even] (newrtwo) [below left= 2cm and 0.5cm of newy] $r^{1-j}$;

(new) edge (newy)
(new) edge (newz)
(newy) edge (newrtwo)
(newy) edge (newr)
(newz) edge (news)
(newz) edge (newr)

Circuit mover gadget for circuit $j$. Left: the edges to $r^j$ and
$s^j$ in a vertex from a -gate. Right: the replacement for these outgoing

Input/output gates.
For each input-bit in each copy of the circuit, have an input/output gate.
Recall that these gadgets have two modes. When Circuit $j$ is computing, the
input/output gadgets in circuit $j$ are in output mode, in which they store the
output of the circuit, and the input/output gadgets in circuit $1-j$ are in
input mode, in which they output the value that was stored in the previous

At its core, the input/output gadget is simply another copy of the -gate
gadget that is connected to the $i$th output bit of circuit $j$. However, we
modify the -gate gadget by adding in extra vertices that allow it to be
moved between the two circuits. The most important part of this circuit
mover apparatus is shown in Figure <ref>: all of the vertices
in the -gate gadget that have edges to $r^j$ and $s^j$ are modified so that
they instead have edges to $y^j$ and $z^j$. Figures <ref>
and <ref> show the gadget and its associated modified
deceleration lane, respectively. There are three differences between this gadget
and the gate, which are the inclusion of the vertices $h^j_{i, \star}$,
the vertices $p^j_i$ and $p^j_{i, 1}$, and the vertices $q^j_{i, \star}$. All of
these vertices are involved in the operation of moving the gadget between the
two circuits.

[node distance=2.5cm,font=]
[even,align=center] (d) $d^j_i$
[odd,right of=d,align=center] (e) $e^j_i$
[even,right=3cm of e,align=center] (f) $o^j_i$
[odd,right=1.0cm of e,align=center] (q) $q^j_{i,0}$
[even,above=1.5cm of q,align=center] (q_1) $q^j_{i,1}$
[even,above=1cm of q_1,align=center] (romj) $r^{1-j}$
[even,above=1.5cm of e,align=center] (k) $h^j_{i,0}$

[even,above left=1.0cm and 1.5cm of k,align=center] (h_1) $h^j_{i,1}$
[even,left=1.5cm of k,align=center] (h_2) $h^j_{i,2}$

[even,below right=2.5cm and 2.5cm of d] (a_1) $a^j_{i,1}$;
[even,left of=a_1,node distance=2cm] (a_2) $a^j_{i,2}$;
[left of=a_2,node distance=2cm] (a_3) $\dots$;
[even,left of=a_3,node distance=2cm] (a_4) [align=center] $a^j_{i,m}$;

[even,left=2cm of d] (s) $z^j$;

[even,above left=.5cm and 2cm of d] (r) $y^j$;
[even,above=.5cm of r] (rone) $r^{1-j}$;
[even,above=.5cm of rone] (rtwo) $r^{j}$;

(f) edge (q)
(q) edge (e)
(q) edge (q_1)
(q_1) edge (romj)
(e) edge (k)
(e) edge [bend left] (d)
(d) edge [bend left] (e)

(d) edge (a_4.north)
(d) edge (a_2.north)
(d) edge (a_1.north)

(k) edge (h_1)
(k) edge (h_2)
(h_1) edge (rtwo)
(h_2) edge (rone)

(d) edge (r)
(d) edge (s)

gate with index $i$ in circuit $j$.

[node distance=1.8cm,font=]
[] (t1) $\dots$;
[even,left of=t1] (t2) $t^j_{i,d(C)-1}$;
[even,left of=t2] (t3) $t^j_{i,d(C)}$;
[even,left of=t3] (t4) $t^j_{i,d(C)+1}$;
[left of=t4] (t5) $\dots$;

[even,above of=t2] (a2) $a^j_{i,d(C)-1}$;
[even,above of=t3] (a3) $a^j_{i,d(C)}$;
[even,above of=t4] (a4) $a^j_{i,d(C)+1}$;

[even,below of=t3,node distance=4.1cm,align=center] (v) $p^j_{i}$
[even,right of=v,node distance=2.3cm] (o) $o^j_{\inp(i)}$;
[even,left of=v,node distance=2.3cm,align=center] (p) $p^j_{i,1}$
[even,left of=p,node distance=2.3cm] (romj) $r^{1-j}$;

(t5) edge (t4)
(t4) edge (t3)
(t2) edge (t1)

(a4) edge (t4)
(a3) edge (t3)
(a2) edge (t2)

(t3) edge (v)
(v) edge (o)
(v) edge (p)
(p) edge (romj)

in t2, t4

[even,draw,minimum size=0.8cm] (1) at ($(\x) - (0.5,2.3)$) $y^j$;
[even,draw,minimum size=0.8cm] (2) at ($(\x) - (-0.5,2.3)$) $z^j$;

() edge (1)
() edge (2)

Modified deceleration lane for an gate $i$ in circuit $j$.

When the gadget is in output mode, the vertex $y^j$ chooses the edge to $r^j$,
the vertex $h^j_{i, 0}$ chooses the edge to $h^j_{i, 1}$, and the vertex $p^j_i$
chooses the edge to $o^j_{\inp(i)}$. When these edges are chosen, the gadget is
essentially the same as a -gate at the top of the circuit. So, once the
circuit has finished computing, the vertex $d_i^j$ chooses the edge to $e_i^j$
(i.e., the stored bit is $1$) if and only if the $i$th output from the circuit was
a $0$. Since the circuit was given in negated form, the gadget has therefore
correctly stored the $i$th bit of $F(B)$.

Throughout the computation in circuit $j$, the valuation of $r^j$ is much larger
than the valuation of $r^{1-j}$. The computation in circuit $1-j$ begins when
the clock in circuit $1-j$ advances, which causes the valuation of $r^{1-j}$ to
become much larger than the valuation of $r^j$. When this occurs, the
input/output gate then transitions to input mode. The transition involves the
vertex $y^j$ switching to $r^{1-j}$, the vertex $h^j_{i, 0}$ switching to
$h^j_{i, 2}$, and the vertex $p^j_i$ switching to $p^j_{i, 1}$. Moreover, the
player Odd vertex $q^j_{i, 0}$ switches $e^j_i$. This vertex acts as a circuit
breaker, which makes sure that the output of the gadget is only transmitted to
circuit $1-j$ when the gadget is in input mode.

The key thing is that all of these switches occur simultaneously in the
same iteration. Since strategy improvement only cares about the relative
difference between the outgoing edges from the vertex, and since all edges
leaving the gadget switch at the same time, the operation of the -gate is
not interrupted. So, the strategy chosen at $d^j_i$ will continue to hold the
$i$th bit of $F(B)$, and the gadget has transitioned to input mode.

When the gadget is in input mode, it can be viewed as a at the bottom of
circuit $1-j$ that has already been computed. In particular, the switch from
$h^j_{i, 1}$ to $h^j_{i, 2}$ ensures that, if the output is $1$, then the gadget
has the correct output priority. Moreover, the deceleration lane has enough
states to ensure that, if the output is $0$, then output of the gadget will not
flip from $0$ to $1$ while circuit $1-j$ is computing.

Finally, once circuit $1-j$ has finished computing, the clock for circuit $j$
advances, and the input/output gadget moves back to output mode. This involves
resetting the gate gadget back to its initial state. This occurs because,
when the clock in circuit $j$ advances, there is a single iteration in which the
valuation of $s^j$ is higher than the valuation of $r^j$. This causes $z^j$ to
switch to $s^j$ which in turn causes a single iteration in which the valuation
of $z^j$ is higher than the valuation of $y^j$. Then, in the next iteration the
vertex $y^j$ switches to $r^j$, and so the valuation of $y^j$ is then larger
than the valuation of $z^j$. So, the valuations of $y^j$ and $z^j$ give exactly
the same sequence of events as $r^j$ and $s^j$, which allows the -gate to

The following table specifies the input/output gadget.

Vertex     Conditions      Edges      Priority     Player
$y^j$     $j \in \{0, 1\}$     $r^{1-j}$, $r^j$     $\pp(3, 0, 1, j, 0)$     Even

$z^j$     $j \in \{0, 1\}$     $r^j$, $s^j$     $\pp(3, 0, 0, j, 0)$     Even

$t^j_{i,0}$     $j \in \{0, 1\}$, $i\in \inputg$     $y^j$, $z^j$     $\pp(5, i,
2k+4n+4, j, 0)$     Even

$t_{i,l}^j$     $j \in \{0, 1\}$, $i\in \inputg$,     $y^j$, $z^j$, $t^j_{i, l-1}$     $\pp(5, i, l, j, 1)$     Even

$1 < l \le \lale$, and $l \ne d(C)$

$t_{i,d(C)}^j$     $j \in \{0, 1\}$, $i\in \inputg$     $p^j_{i}$     $\pp(5, i,
d(C), j, 1)$     Even

$p_{i}^j$     $j \in \{0, 1\}$, $i \in \inputg$     $o^j_{\inp(i)}$, $p^j_{i,1}$
$\pp(3, i, 2, j, 0)$     Even

$p_{i,1}^j$     $j \in \{0, 1\}$, $i \in \inputg$     $r^{1-j}$     $\pp(5, i, 2k+4n+5, j, 0)$     Even

$a_{i,l}^j$     $j \in \{0, 1\}$ $i \in \inputg$,     $t_{i,l}$     $\pp(5, i, l+1, j, 0)$     Even

$1 \le l \le \lale$

$d^j_i$     $j \in \{0, 1\}$, $i \in \inputg$     $y^j$, $z^j$, $e^j_i$,
$\pp(4,i,0,j,1)$     Even

$a^j_{i,l}$ for $1 \le l \le \lale $

$e^j_i$     $j \in \{0, 1\}$, $i \in \inputg$     $h^j_{i,0}$, $d^j_i$     $\pp(4,i,1,j,0)$

$q^j_{i,0}$     $j \in \{0, 1\}$, $i \in \inputg$     $e^j_i$, $q^j_{i,1}$     $\pp(4,
i, 2, j, 0)$     Odd

$q^j_{i,1}$     $j \in \{0, 1\}$, $i \in \inputg$     $r^{1-j}_i$     $\pp(6, d(C)+2,
0, j, 0)$     Even

$o^j_i$     $j \in \{0, 1\}$, $i \in \inputg$     $q^j_{i,0}$     $\pp(6,i,0,j,1)$     Even

$h_{i,0}^j$     $j \in \{0, 1\}$, $i \in \inputg$     $h_{i,1}^j$, $h_{i,2}^j$     $\pp(3, i, 3, j, 0)$

$h_{i,1}^j$     $j \in \{0, 1\}$, $i \in \inputg$     $r^j$     $\pp(6,d(C)+1,1,j,0)$     Even

$h_{i,2}^j$     $j \in \{0, 1\}$, $i \in \inputg$     $r^{1-j}$     $\pp(6,0,1,j,0)$     Even

One-sink game. If we are to use the simplified strategy
improvement algorithm, we must first show that this construction is a one-sink
game. We do so in the following lemma.

The construction is a one-sink game.

In order to show that the construction is a one-sink game, we must show that
the two required properties hold. Firstly, we must show that there is a
vertex the satisfies the required properties of a sink vertex. It is not
difficult to verify that vertex $x$ does indeed satisfy these properties: the
only outgoing edge from $x$ is the edge $(x, x)$, and we have $\pri(x) = \pp(0,
0, 0, 0, 0) = 1$. Furthermore, no vertex is assigned priority $0$.

Secondly, we must argue that all optimal strategies are terminating. Recall that
a terminating strategy has the property that the first component of the
Vöge-Jurdziński valuation is $1$, which implies that all paths starting at
all vertices eventually arrive at the sink $x$. So, consider a strategy $\sigma$
that is not terminating, and let $v$ be a vertex such that the first component
of  $\val^{\sigma}_{VJ}$ is strictly greater than 1. Let $C$ be the cycle that
is eventually reached by following $\sigma$ and $\br(\sigma)$ from $v$. There
are two cases to consider:

* If $C$ contains at least one vertex from a clock, then
$C$ must be entirely contained within that clock, because there are no edges
that leave either of the two clocks. In this case we have that $\sigma$ is not
optimal because Friedmann has shown that his construction is a one-sink game.

* If $C$ does not contain a vertex from a clock, then it is entirely
contained within the circuits. First observe that $C$ cannot be a two-vertex
cycle using the vertices $d^j_i$ and $e^j_i$, because it is not a best-response
for Odd allow a cycle with an even priority to be formed, since he can always
move to $r^j$, and from there eventually reach a cycle with priority $p \preceq
1$ (because the clock is a one-sink game). But, the only other way to form a
cycle in the circuits is to pass through both of the circuits. In this case, the
highest priority on the cycle will be an odd priority assigned to the state
$o^j_i$ in either a -gate (if there is one on the path), or an input/output
gate (otherwise.) Since this odd priority is strictly greater than $1$, and
since player Even can always assure a priority of $1$ by, for example, moving to
$r^j$ in every input/output state $d^j_i$, we have that $\sigma$ is not an
optimal strategy.

Therefore, we have shown that the construction is a one-sink game.

§ STRATEGIES

In this section, we define an initial strategy, and describe the sequence of
strategies that greedy all-switches strategy improvement switches through when
it is applied to this initial strategy. We will define strategies for each of
the gadgets in turn, and then combine these into a full strategy for the entire

It should be noted that we will only define partial strategies in this
section, which means that some states will have no strategy specified. This is
because our construction will work no matter which strategy is chosen at these

To deal with this, we must define what it means to apply strategy improvement to
a partial strategy. If $\chi$ is a partial strategy and $\sigma \in \seven$ is a
strategy, then we say that $\sigma$ agrees with $\chi$ if $\sigma(v) =
\chi(v)$ for every vertex $v \in V$ for which $\chi$ is defined. So, if $\chi_1$
and $\chi_2$ are partial strategies, then we say that greedy all-switches
strategy improvement switches $\chi_1$ to $\chi_2$ if, for every strategy
$\sigma_1 \in \seven$ that agrees with $\chi_1$, greedy all-switches strategy
improvement switches $\sigma$ to a strategy $\sigma_2$ that agrees with

We now describe the sequence of strategies. Each part of the construction will
be considered independently.

The clock.
We start by defining the sequence of strategies that occurs in the two clocks.
For each clock bit-string $\C \in \{0, 1\}^n$, we define a sequence of
strategies $\kappa^{\C}_1$, $\kappa^{\C}_2$, …, $\kappa^{\C}_{\length(\C)}$.
Greedy all-switches strategy improvement switches through each of these
strategies in turn, and then switches from $\kappa^{\C}_{\length(\C)}$ to
$\kappa^{\C+1}_1$, where $\C+1$ denotes the bit-string that results by adding
$1$ to the integer represented by $\C$. The sequence begins in the first
iteration after the valuation of $s^j$ is larger than the valuation of $r^j$.
We will first present the building blocks of this strategy, and the combine the
building blocks into the full sequence.

We begin by considering the vertices $t^j_l$ in the deceleration lane. Recall that
these states switch, in sequence,  from $r^j$ to $t^j_{l-1}$. This is formalised
in the following definition. For each $m \ge 1$, each $l$ in the range $1 \le l
\le \lale$, and each $j \in \{0, 1\}$,  we define:

\begin{align*}
\rho_m(t^j_0) &= \begin{cases}
s^j & \text{if $m = 1$,} \\
r^j & \text{if $m > 1$.}
\end{cases} \\
\rho_{m}(t^j_{l}) &= \begin{cases}
s^j & \text{if $m = 1$,} \\
r^j & \text{if $m > 1$ and $m \le l+1$,} \\
t^j_{l-1} & \text{if $m > l+1$.}
\end{cases}
\end{align*}

We now move on to consider the vertices $d^j_i$, which represent the bits in the
counter. We begin by defining a sequence of strategies for the bits that are
$0$. Recall that these vertices switch to the states $a^j_{i}$ along the
deceleration lane until they run out of edges, at which point they switch to the
vertex $e^j_i$. This is formalised in the following definition. For each $i$ in
the range $1 \le i \le n$, each $m \ge 1$, and each $j \in \{0, 1\}$, we define:

\begin{equation*}
\rho_{m}(d^j_i) = \begin{cases}
s^j & \text{if $m = 1$,} \\
r^j & \text{if $m = 2$,} \\
a^j_{\laletwo + 2i} & \text{if $m = 3$,} \\
a^j_{m-3} & \text{if $4 \le m \le \laletwo + 2i + 3$,} \\
e^j_{i} & \text{if $m > \laletwo + 2i + 3$.}
\end{cases}
\end{equation*}

Note that the first three iterations are special, because the edge to $a^j_{1}$
only becomes switchable in the third iteration. The edge to $r^j$
and the edge to $a^j_{\laletwo + 2i}$ prevent the edge to $e^j_i$ being switched
before this occurs.

We now give a full strategy definition for the vertices $d^j_i$. The bits that
are $0$ follow the strategy that we just defined, and the bits that are $1$
always choose the edge to $e^j_i$. For each bit-string $\C \in \{0, 1\}^n$, each
$i$ in the range $1 \le i \le n$, each $m \ge 1$, and each $j \in \{0, 1\}$, we

\begin{equation*}
\rho^\C_m(d^j_i) = \begin{cases}
\rho_m(d^j_i) & \text{if $\C_i = 0$,} \\
e^j_i & \text{if $\C_i = 1$.}
\end{cases}
\end{equation*}

Finally, we consider the other vertices in the clock. To define strategies for
these vertices, we must first define some notation. For each $i$ in the range $1
\le i \le n$, we define $\nexbit(\C, i)$ to be a partial function that gives the
index of the first $1$ that appears higher than index $i$: that is, the smallest
index $j > i$ such that $\C_j = 1$. We now define the strategies. These
strategies all depend on the current clock bit-string $\C$, and have no
dependence on how far the deceleration lane has switched, so the parameter $m$ is
ignored. For each bit-string $\C \in \{0, 1\}^n$, each $m \ge 1$, each $i$ in
the range $1 \le i \le n$, and each $j \in \{0, 1\}$, we define:

\begin{align*}
\rho^\C_m(g^j_i) &= \begin{cases}
k^j_i & \text{if $\C_i = 0$,} \\
f^j_i & \text{if $\C_i = 1$.}
\end{cases} \\
\rho^\C_m(k^j_i) &= \begin{cases}
g^j_{\nexbit(\C, i)} & \text{if $\nexbit(\C, i)$ is defined,} \\
x & \text{otherwise.}
\end{cases} \\
\rho^\C_m(r^j) &= \begin{cases}
g^j_{\nexbit(\C, 0)} & \text{if $\nexbit(\C, 0)$ is defined,} \\
x & \text{otherwise.}
\end{cases} \\
\rho^\C_m(s^j) &= \begin{cases}
f^j_{\nexbit(\C, 0)} & \text{if $\nexbit(\C, 0)$ is defined,} \\
x & \text{otherwise.}
\end{cases}
\end{align*}

When the clock transitions between two clock bit-strings, there is a single
iteration in which the strategies defined above are not followed. This occurs
one iteration after the vertex $d^j_{\lsz(\C)}$ switches to $e^j_{\lsz(\C)}$. In
this iteration, the vertices $g^j_{\lsz(\C)}$ and $s^j$ switch to
$f^j_{\lsz{\C}}$, while every other vertex continues to use the strategies that
were defined above. We now define a special reset strategy that captures
this. For each bit-string $\C \in \{0, 1\}^n$, and every vertex $v$ in either of
the two clocks we define:

\begin{equation*}
\rho^\C_{\text{Reset}}(v) = \begin{cases}
f^j_{\lsz(\C)} & \text{if $v = g^j_{\lsz(\C)}$ or $v = s^j$,} \\
\rho^\C_{\length(\C)}(v) & \text{otherwise.}
\end{cases}
\end{equation*}

We can now combine the strategies defined above in order to define the full
sequence of strategies that are used in the clocks. In the first $\length(\C)
-1$ iterations, we follow the sequence defined by the strategies
$\rho^{\C}_m(v)$, and in the final iteration we use the strategy
$\rho^{\C}_{\text{Reset}}(v)$. Formally, for each bit-string $\C \in \{0,
1\}^n$, each $m$ in the range $1 \le m \le \length(\C)$, and every vertex $v$ in
either of the two clocks, we define:

\begin{equation*}
\kappa^{\C}_m(v) = \begin{cases}
\rho^{\C}_m(v) & \text{if $m \le \length(\C) -1$,}\\
\rho^{\C}_{\text{Reset}}(v) & \text{if $m = \length(\C)$.}
\end{cases}
\end{equation*}

Friedmann showed the following lemma.

Let $\C \in \{0, 1\}^n$. If we start all-switches strategy improvement at
$\kappa^{\C}_1$ for clock $j$, then it will proceed by switching through the
sequence $\kappa^\C_1$, $\kappa^\C_2$, $\dots$, $\kappa^\C_{\length(\C)}, \kappa^{\C + 1}_1$.

The circuits.

For each bit-string $B \in \{0, 1\}^n$, we give a sequence of strategies
$\sigma^B_1$, $\sigma^B_2$, $\dots$, which describes the sequence of strategies
that occurs when $B$ is the input of the circuit. The sequence is indexed from the
point at which the circuit's clock advances to the next bit-string. That is,
$\sigma^B_1$ occurs one iteration after the valuation of $s^j$ exceeds the
valuation of $r^j$.

Recall that all of the gates with the same depth are evaluated in the same
iteration. We can now make this more precise: each gate $i$ will be evaluated in
the strategy $\sigma^B_{d(i) + 2}$. After this iteration, there will then be two
cases based on whether the gate evaluates to $1$ or $0$. To deal with this, we
require the following notation. For each bit-string $B$ and each gate $i$, we
define $\eval(B, i)$ to be $1$ if gate $i$ outputs true on input $B$, and $0$

Or gates.

Before the gate is evaluated, the state $o^j_i$ chooses the edge to $r^j$. Once
the gate has been evaluated, there are four possibilities. If both input gates
evaluate to false, then the state $o^j_i$ continues to use the edge to $r^j$. If
one of the two inputs is true, then $o^j_i$ will switch to the corresponding
input state. The case where both  inputs are true is the most complicated.
Obviously, $o^j_i$ will switch to one of the two input states, and in fact, it
switches to the one with the highest valuation. Since the overall correctness of
our construction does not care which successor is chosen in this case, we simply
define $\ornext(i)$ to be the successor with the highest valuation.

We can now formally define the sequence of strategies used by an -gate. For
every gate $i \in \org$, every pair of bit-strings $B \in \{0, 1\}^n$, and every
$m \ge 1$ we define:

\begin{equation}
\label{eqn:odef}
\sigma^{B}_m(o^j_i) = \begin{cases}
s^j_i & \text{if $m = 1$,} \\
r^j_i & \text{if $m > 1$ and $m \le d(i) + 2$,} \\
r^j_i & \text{if $m > d(i) + 2$ and $\eval(B, \inp_1(i)) = 0$ and
$\eval(B, \inp_2(i)) = 0$,} \\
\inputstate(i,j,1) & \text{if $m > d(i) + 2$ and $\eval(B, \inp_1(i)) = 1$ and
$\eval(B, \inp_2(i)) = 0$,} \\
\inputstate(i,j,2) & \text{if $m > d(i) + 2$ and $\eval(B, \inp_1(i)) = 0$ and
$\eval(B, \inp_2(i)) = 1$,} \\
\ornext(i) & \text{if $m > d(i) + 2$ and $\eval(B, \inp_1(i)) = 1$ and $\eval(B, \inp_2(i)) = 1$.}
\end{cases}
\end{equation}

Not gates.
There are two components of the -gate gadget: the modified deceleration
lane and the state $d^j_i$. We begin by considering the modified deceleration

We first define a strategy for the case where the gate evaluates to false. In
this case, the input gate evaluates to true, which causes the modified
deceleration lane to continue switching after iteration $d(i) + 2$. We formalise
this in the following definition, which is almost identical to the definition
given for the deceleration lane used in the clock. For each $i \in \notg$, each
$l$ in the range $1 \le l \le \lale$ with $l \ne d(i)$, each $j \in \{0, 1\}$,
and each $m \ge 1$, we define:

\begin{align}
\label{eqn:tnotdef}
\sigma_m(t^j_{i, 0}) &= \begin{cases}
s^j & \text{if $m = 1$,} \\
r^j & \text{if $m > 1$.}
\end{cases} \\
\sigma_m(t^j_{i,l}) &= \begin{cases}
s^j & \text{if $m = 1$,} \\
r^j & \text{if $m > 1$ and $m \le l+1$,} \\
t^j_{i, l-1} & \text{if $m > l+1$.}
\end{cases}
\end{align}

On the other hand, if the gate evaluates to false, then the deceleration lane
stops switching. This is formalised in the following definition, which uses the
previous definition to give the actual strategy used by the modified
deceleration lane. For each $i \in \notg$, each $B \in \{0, 1\}^n$, each $l$ in
the range $0 \le l \le \lale$ with $l \ne d(i)$, each $j \in \{0, 1\}$, and each
$m \ge 1$, we define:

\begin{equation*}
\sigma^{B}_m(t^j_{i,l}) = \begin{cases}
\sigma_m(t^j_{i,l}) & \text{if $l \le d(i)+1$, or $l > d(i) + 1$ and $\eval(B,
\inp(i)) = 1$,} \\
s^j & \text{if $l > d(i)+1$ and $m = 1$ and $\eval(B, \inp(i)) = 0$,} \\
r^j & \text{if $l > d(i)+1$ and $m > 1$ and $\eval(B, \inp(i)) = 0$.}
\end{cases}
\end{equation*}

We now turn out attention to the state $d^j_i$, where we again begin by
considering the case where the gate evaluates to false. In this case, the state
$d^j_i$ continues switching to the modified deceleration lane. This is
formalised in the following definition, which is almost identical to the
definition given for the corresponding states in the clock. For all $i \in \notg
\cup \inputg$, all $B \in \{0, 1\}^n$, for all $m \ge 1$, and all $j \in \{0,
1\}$, we define:

\begin{equation*}
\sigma_m(d^j_i) = \begin{cases}
s^j & \text{if $m = 1$,} \\
r^j & \text{if $m = 2$,} \\
a^j_{i, \lale} & \text{if $m = 3$,} \\
a^j_{i, m-3} & \text{if $4 \le m \le \lale+3$,} \\
e^j_i & \text{if $\lale + 3 < m$.}
\end{cases}
\end{equation*}

On the other hand, if the gate evaluates to true, then after iteration $d(i) +
2$, the state $d^j_i$ switches to $e^j_i$. This is formalised in the following
definition, where the previous definition is used in order to give the actual
sequence of strategies for the state $d^j_i$. For all $B \in \{0,1\}^n$, all $i
\in \notg$, all $j \in \{0, 1\}$, and all $m \ge 1$ we define:

\begin{equation}
\label{eqn:notd}
\sigma^B_m(d^j_i) = \begin{cases}
\sigma_m(d^j_i) & \text{if $m \le d(i) + 2$, or $m > d(i) + 2$ and $\eval(B, \inp(i)) = 1$,} \\
e^j_i & \text{if $m > d(i)+2$ and $\eval(B, \inp(i)) = 0$.}
\end{cases}
\end{equation}

Input/output gates. We now describe the sequence of strategies
used in the input/output gates. These strategies are almost identical to the
strategies that would be used in a -gates with depth $d(C)+1$, but with a
few key differences. Firstly, whereas the -gates used edges to $r^j$ and
$s^j$, these have instead been replaced with the edges to $y^j$ and $z^j$ from
the circuit movers. Secondly, the circuit movers cause a one iteration delay at
the start of the sequence. Note, however, that despite this delay, the
input/output gates are still evaluated on iteration $d(C) + 3$.

We begin by giving the strategies for the modified deceleration lane used in the
input/output gates. For each $i \in \notg$, each $l$ in the range $1 \le l \le
\lale$ with $l \ne d(C)$, each $j \in \{0, 1\}$, and each $m \ge 1$, we define:

\begin{align*}
\sigma_m(t^j_{i,l}) &= \begin{cases}
z^j & \text{if $m = 2$,} \\
y^j & \text{if $m = 1$ or $m > 1$ and $m \le l+2$,} \\
t^j_{i, l-1} & \text{if $m > l+2$.}
\end{cases} \\
\sigma_m(t^j_{i, 0}) &= \begin{cases}
z^j & \text{if $m = 2$,} \\
y^j & \text{if $m = 1$ or $m > 2$.}
\end{cases}
\end{align*}

Then, for each $i \in \notg$, each $B \in \{0, 1\}^n$, each $l$ in the range $0
\le l \le \lale$ with $l \ne d(C)$, each $j \in \{0, 1\}$, and each $m \ge 1$,
we define:

\begin{equation*}
\sigma^{B}_m(t^j_{i,l}) = \begin{cases}
\sigma_m(t^j_{i,l}) & \text{if $l < d(C) + 3$, or $l \ge d(C)+3$ and $B_i = 0$,} \\
z^j & \text{if $l > d(C)+ 3$ and $m = 2$ and $B_i = 1$,} \\
y^j & \text{if $l > d(C)+ 3$ and either $m = 1$ or $m > 2$ and $B_i = 1$.}
\end{cases}
\end{equation*}

Finally, we give the strategy for the state $d^j_i$. We reuse the
strategy $\sigma_{m-1}$ from the -gate definitions, but with a one
iteration delay. For all $B \in \{0,1\}^n$, all $i \in \inputg$, all $j \in \{0,
1\}$, and all $m
> 1$ we define:

\begin{equation}
\label{def:inputd}
\sigma^B_m(d^j_i) = \begin{cases}
\sigma_{m-1}(d^j_i) & \text{if $1 < m \le d(C) + 3$, or $m > d(C) + 3$ and $B_i = 0$,} \\
e^j_i & \text{if $m > d(i)+3$ and $B_i = 1$.}
\end{cases}
\end{equation}

The circuit mover states.
Finally, we describe the sequence of strategies used in the states that move the
input/output gates between the circuits. These strategies do not depend on the
current input bit-string to the circuit. Instead, they depend on the state of
both of the clocks, and are parameterized by the value of the delay function that we defined

Formally, for every $m \ge 1$, every $i \in \inputg$, and every clock-bit string $\C \in
\{0, 1\}^n$ we define:

\begin{align}
\label{eqn:zj}
\sigma^{\C}_m(z^j) &= \begin{cases}
s^j & \text{if $m = 1$,} \\
r^j & \text{if $m > 1$.} \\
\end{cases} \\
\label{eqn:yj}
\sigma^{\C}_m(y^j) &= \begin{cases}
r^{1-j} & \text{if $m = 1$ or $m \ge \delay(j,\C) + 1$} \\
r^j & \text{if $m > 1$ and $m < \delay(j,\C) + 1$.} \\
\end{cases} \\
\label{eqn:pj}
\sigma^{\C}_m(p^j_i) &= \begin{cases}
p^{j}_{i,1} & \text{if $m = 1$ or $m \ge \delay(j,\C) + 1$,} \\
o^j_{\inp(i)} & \text{if $1 < m \le \delay(j,\C) + 1$.} \\
\end{cases} \\
\label{eqn:hj}
\sigma^{\C}_m(h^j_{i,0}) &= \begin{cases}
h^{j}_{i,2} & \text{if $m = 1$ or $m \ge \delay(j,\C) + 1$,} \\
h^j_{i,1} & \text{if $1 < m < \delay(j,\C) + 1$.} \\
\end{cases}
\end{align}

Putting it all together.

We can now define a combined sequence of strategies for the entire construction.
We will defined a sequence of strategies
$\chi^{B,\C,j}_2$, …, which describes a computation in circuit $j$ under the
following conditions:

* The clock for circuit $j$ currently stores $\C$ in its binary counter.

* The input to circuit $j$ is $B$.

Before stating the strategies, we first define some necessary notation. For
every clock bit-string $\C \in \{0, 1\}$, and every $j \in \{0, 1\}$ we define:

\begin{equation*}
\OC(\C, j) = \begin{cases}
\C-1 & \text{if $j = 0$,} \\
\C & \text{if $j = 1$.}
\end{cases}
\end{equation*}

This gives the bit-string used in the other clock, when circuit $j$ is
computing. Since clock $0$ is ahead of clock $1$, we have that $\OC(\C, 0)$ is
the bit-string before $\C$, while $\OC(\C, 1)$ is the same as $\C$.

We can now define the sequence.
For each bit-string $B \in \{0, 1\}^n$, each bit-string $\C \in \{0, 1\}^n$,
each $m \ge 1$, and every vertex $v$ we define:

\begin{align*}
\chi^{B,\C,j}_m(v) &= \begin{cases}
\kappa^{\C}_m(v) & \text{if $v$ is in clock~$j$,} \\
\kappa^{\OC(\C, j)}_{m + \delay(1-j, \OC(\C, j))}(v) & \text{if $v$ is in
clock~$1-j$,} \\
\sigma^{B}_m(v)  & \text{if $v$ is in a $\notg$ or $\org$ gate in circuit~$j$,} \\
\sigma^{F(B)}_m(v) & \text{if $v$ is in an input/output gate in circuit~$j$,} \\
\sigma^{B}_{m+\delay(1-j, \OC(\C, j))}(v) & \text{if $v$ is an input/output gate in
circuit~$1-j$,} \\
\sigma^{\C}_m(v)  & \text{if $v$ is a circuit mover state in circuit~$j$,} \\
\sigma^{\OC(\C, j)}_{m+\delay(1-j, \OC(\C, j))}(v) & \text{if $v$ is a circuit
mover state in circuit~$1-j$.}
\end{cases} \\
\end{align*}

The first two cases of this definition deal with the clocks: the clock in
circuit $j$ follows the sequence for bit-string $\C$, while the clock in circuit
$1-j$ continues to follow the sequence for bit-string $\OC(\C, j)$. Observer
that the clock for circuit $1-j$ has already been running for $\delay(1-j,
\OC(\C, j)$ iterations, so the strategies for this clock start on iteration $1 +
\delay(1-j, \OC(\C, j)$. The next two cases deal with the gate gadgets in
circuit $j$: the and gates follow the sequence for bit-string $B$,
and then the input/output gates for circuit $j$, which are in output mode, store
$F(B)$. The next case deals with the input/output gates in circuit $1-j$ are in
input mode, and so follow the strategy for bit-string $B$. The final two cases
deal with the circuit mover states, which follow the strategies for the clock
bit-string used in their respective clocks. Observe that no strategy is
specified for the gate gadgets in circuit $1-j$, because the strategy chosen
here is irrelevant.

For technical convenience, we define:

\begin{align*}
\chi^{B, \C, 0}_{\delay(0,\C)} &= \chi^{F(B), \C, 1}_1 \\
\chi^{B, \C, 1}_{\delay(1,\C)} &= \chi^{F(B), \C+1, 0}_1
\end{align*}

Using this definition, we can now state the main technical claim of the paper.

Let $B \in \{0, 1\}^n$ be a bit-string, let $C \in \{0, 1\}^n$ be a
bit-string such that $C \ne (1,1,\dots,1)$, and let $j \in \{0, 1\}$.
If greedy all-switches strategy improvement is applied to $\chi^{B, \C,
0}_1$, then it will pass through the sequence:

\begin{equation*}
\chi^{B, \C, j}_1, \chi^{B, \C, j}_2, \dots, \chi^{B, \C, j}_{\delay(j,\C)}.
\end{equation*}

Unfortunately, the proof of this lemma is quite long, and the vast
majority of it is presented in the appendix. In Section <ref>, we give
an overview of the proof, and describe how each of the individual appendices fit
into the overall proof.

Best responses.
Recall that, for each strategy considered, strategy improvement computes a
best-response for the opponent. Now that we have defined the sequence of
strategies, we can also define the best-responses to these strategies. For each
strategy $\chi^{B, \C, j}_i$, we define a strategy $\mu^{B,\C,j}_i \in \sodd$
that is a best-response to $\chi^{B, \C, j}_i$. We will later prove that these
strategies are indeed best-responses.

We begin by considering the vertices $e^j_i$ for each -gate $i$. Recall
that these vertices only pick the edge to $h^j_{i,0}$ in the case where they are
forced to by $d^j_i$ selecting the edge to $e^j_i$. As defined above, this only
occurs in the case where the -gate evaluates to true. Formally, for each
bit-string $B \in \{0, 1\}^n$, each bit-string $\C \in \{0, 1\}^n$, each $m \ge
1$, and every $i \in \notg$ we define:

\begin{equation*}
\mu^{B,\C,j}_m(e^j_i) = \begin{cases}
h^j_{i,0} & \text{if $m > d(i)+2$ and $\eval(B, \inp(i)) = 0$,} \\
d^j_i & \text{otherwise.}
\end{cases}
\end{equation*}

For the input/output gadgets in circuit $1-j$, which will provide the input to
circuit $j$, the situation is the same. The vertex $e^{1-j}_i$ chooses the edge
to $h^{1-j}_{i, 0}$ if and only if $B_i$ is $1$. Formally, for each bit-string
$B \in \{0, 1\}^n$, each bit-string $\C \in \{0, 1\}^n$, each $m \ge 1$, and
every vertex $i \in \inputg$ we define:

\begin{equation*}
\mu^{B,\C,j}_m(e^{1-j}_i) = \begin{cases}
h^{1-j}_{i,0} & \text{if $B_i = 1$,} \\
d^{1-j}_i & \text{if $B_i = 0$.}
\end{cases}
\end{equation*}

For the input/output gadgets in circuit $1-j$, the situation is the largely the
same as for a -gate with depth $d(C) + 1$, and the edge chosen depends on
$F(B)_i$. However, one difference is that we do not define a best-response for
the case where $m = 1$, because the input/output gadget does not reset until the
second iteration, and our proof does not depend on the best response chosen in
iteration one. Formally, for each bit-string $B \in \{0, 1\}^n$, each bit-string
$\C \in \{0, 1\}^n$, each $m > 1$, and every vertex $i \in \inputg$ we define:

\begin{equation*}
\mu^{B,\C,j}_m(e^j_i) = \begin{cases}
%d^j_i & \text{if $m = 1$ and $B_i = 0$,} \\
%h^j_{i,0} & \text{if $m = 1$ and $B_i = 1$,} \\
h^j_{i,0} & \text{if $m > d(i)+3$ and $F(B)_i = 1$,} \\
d^j_i & \text{otherwise.}
\end{cases}
\end{equation*}

Finally, we define the best responses for the vertices $q^j$ as follows.  For
each bit-string $B \in \{0, 1\}^n$, each bit-string $\C \in \{0, 1\}^n$, each
$m$ in the range $1 \le m \le \delay(j, \C) -1$, and every vertex $i \in
\inputg$ we define:

\begin{align*}
\mu^{B,\C,j}_m(q^j_{i,0}) &= \begin{cases}
e^j_{i} & \text{if $m = 1$, } \\
q^j_{i,1} & \text{if $m > 1$. }
\end{cases} \\
\mu^{B,\C,j}_m(q^{1-j}_{i,0}) &= \begin{cases}
\end{cases}
\end{align*}

§ THE PROOF

In this section we give the proof for Lemma <ref>. Let $B, \C \in \{0,
1\}^n$ be two bit-strings, let  $j \in \{0, 1\}$, and let $m$ be in the range $1
\le m \le \delay(j, \C) - 1$. We must show that greedy all-switches strategy
improvement switches $\chi^{B, \C, j}_m$ to $\chi^{B, \C, j}_{m+1}$.

Let $\sigma$ be a strategy that agrees with $\chi^{B, \C, j}_m$. Since we are
using the all-switches switching rule, we can consider each vertex $v$
independently, and must show that the most appealing outgoing edge at $v$ is the
one specified by $\chi^{B, \C, j}_{m+1}$ (in our construction there will always
be exactly one most appealing edge, so we do not care how ties are broken by
the switching rule.) Hence, the majority of the proof boils down to calculating the
valuation of each outgoing edge of $v$, and then comparing these valuations.

To compare the valuation of two outgoing edges $(v, u)$ and $(v, w)$, we usually
use the following technique. First we consider the two paths $\pi_1$ and $\pi_2$
that start at $u$ and $w$, respectively, and follow $\sigma$ and $\br(\sigma)$.
Then we find the first vertex $x$ that is contained in both paths. Since the
$\sqsubseteq$ relation only cares about the maximum difference between the two
paths, all priorities that are visited after $x$ are irrelevant, since they
appear in both $\val^{\sigma}(u)$ and $\val^{\sigma}(w)$. On the other hand,
since each priority is assigned to at most one vertex, all of the priorities
visited by $p_1$ before reaching $x$ are contained in $\val^{\sigma}(u)$ and not
contained in $\val^{\sigma}(w)$, and all of the priorities visited by $p_2$
before reaching $x$ are contained in $\val^{\sigma}(w)$ and not contained in
$\val^{\sigma}(u)$. So it suffices to find the largest priority on the prefixes
of $p_1$ before $x$ and the prefix of $p_2$ before $x$. The parity of this
priority then determines whether $\val^{\sigma}(u) \sqsubseteq \val^{\sigma}(w)$
according to the rules laid out in the definition of $\sqsubseteq$.

We now give an outline of the proof.

* The fact that the two clocks switch through their respective strategies
follows from Lemma <ref>.

* The difference in valuation between the states $r^j$ and $s^j$ of the
clock are the driving force of the construction. In Appendix <ref>, we
give two lemmas that formalize this difference.

* Next, in Appendix <ref>, we prove that the best-response strategies
defined in Section <ref> are in fact the best responses. That is,
we show that $\mu^{B,\C,j}_m$ is a best response to every strategy $\sigma$ that
agrees with $\chi^{B, \C, j}_{m}$.

* In Appendix <ref>, we give two key lemmas that describe the
valuations of the output stats $o^j_i$. These lemmas show three important
properties. Firstly, if $m \le d(i) + 2$, then the valuation of $o^j_i$ is low,
so there is no incentive to switch to $o^j_i$ before gate $i$ is evaluated.
Secondly, if $m > d(i) + 2$ and the gate evaluates to $0$, then the valuation of
$o^j_i$ remains low. Finally, if $m > d(i) + 2$ and the gate evaluates to $1$,
then the valuation of $o^j_i$ is high. These final two properties allow the
gates with depth strictly greater than $i$ to compute their outputs correctly.

* The rest of the proof consists of proving that all vertices switch to the
correct outgoing edge. The states $o^j_i$ in the gate gadgets are dealt
with in Appendix <ref>. The states $t^j_{i, l}$ in the gates are
dealt with in Appendix <ref>. The states $d^j_{i}$ in the gates
are dealt with in Appendix <ref>. The states $z^j$ and $z^{1-j}$ are
dealt with in Appendix <ref>, and the states $y^j$ and $y^{1-j}$ are dealt
with in Appendix <ref>. The states $p^j$ and $p^{1-j}$ are dealt with in
Appendix <ref> and the states $h^j_{i, 0}$ are dealt with in
Appendix <ref>. Finally, the states in the gates, which behave in
a largely identical way to the gates, are dealt with in
Appendix <ref>.

All of the above combines to provide a proof for Lemma <ref>.

Having shown this Lemma, we can now give the reduction from $\bitswitch$ to
$\edgeswitch$. Given a circuit iteration instance $(F, B, z)$, we produce the
parity game $G$ corresponding to $F$, we use $\chi^{B, 1, 0}_2$ as the initial
strategy, and if $i \in \inputg$ is the input/output gate corresponding to index
$z$, then we will monitor whether the edge from $d^0_i$ to $e^0_i$ is ever
switched by greedy all-switches strategy improvement. We therefore produce the
instance $\edgeswitch(G, (d^0_i, e^0_i), \chi^{B, 1, 0}_2)$. We must take care
to ensure that $\chi^{B, 1, 0}_2$ is a terminating strategy, which is proved in
the following Lemma.

We have that $\chi^{B, 1, 0}_2$ is a terminating strategy.

Firstly, since we use the same strategies as Friedmann in the clock, we do not
need to prove that theses portions of the strategies are terminating, because
this has already been shown by Friedmann. In particular, this implies that all
paths starting at $s^j$ and $r^j$ for $j \in \{0, 1\}$ will eventually arrive at
the sink $x$. Therefore, it is sufficient to show that the first component of
$\val_{\text{VJ}}^{\chi^{B, 1, 0}_2}(v)$ is $1$ for every vertex $v$ in the

Observe that, in the strategy $\chi^{B, 1, 0}_2$, we have that the only possible
cycles that player Odd can form in the best response are two-vertex cycles of
the form $d^j_i$ and $e^j_i$, but these cycles have an even priority, so the
best response can not choose them. In particular, it is not possible to form a
cycle that passes through the input/output gadgets in both circuits, because the
path that starts at $o^0_i$ for every input/output gate $i$ must eventually
arrive at $s^j$. Thus, we have that all paths starting at all vertices in the
circuits that follow $\chi^{B, 1, 0}_2$ and its best response will eventually
arrive at this sink $x$.

Now all that remains is to argue that $\edgeswitch(G, (d^0_i, e^0_i), \chi^{B,
1, 0}_2)$ is true if and only if $\bitswitch(F, B, z)$ is true. To do this, we
simply observe that the sequence of strategies used in Lemma <ref> only
ever specify that $d^0_i$ must be switched to $e^0_z$ in the case where there is
some even $j$ such that $F^j(B)_z = 1$. At all other times, the vertex $d^0_i$
chooses an edge other that $e^j_i$. Hence, the reduction is correct, and we have
shown Theorem <ref>.

§ OTHER ALGORITHMS

Other strategy improvement algorithms.
As we mentioned in the introduction, Theorem <ref> implies several
results about other algorithms. In particular, discounted games and
simple-stochastic games both have natural strategy improvement algorithms given
by Puri [31], and Condon [3], respectively. Friedmann
showed that if you take a one-sink parity game, and apply the natural reduction
from parity games to either discounted or simple stochastic games, then the
greedy variants of Puri's and Condon's algorithms will switch exactly the same
edges as the algorithm of Vöge and Jurdziński <cit.>. Hence, Theorem <ref> also implies the discounted
and simple-stochastic cases of Corollary <ref>.

One case that was missed by Friedmann was mean-payoff games. There is a natural
strategy improvement algorithm [11] for mean-payoff games that adopts the
well-known gain-bias formulation from average-reward
MDPs [32]. In this algorithm, the valuations has two components:
the gain of a vertex gives the long-term average-reward that can be
obtained from that vertex under the current strategy, and the bias
measures the short term deviation from the long-term average.

We argue that, if we apply the standard reduction from parity games to
mean-payoff games, and then set the reward of $x$ to $0$, then the gain-bias
algorithm for mean-payoff games switches exactly the same edges as the algorithm
of Vöge and Jurdziński. The standard reduction from parity games to
mean-payoff games [31, 22] replaces each priority $p$ with the
weight $(-m)^{p}$, where $m$ denotes the number of vertices in the parity game.
By setting the weight of $x$ to $0$, we ensure that the long-term average reward
from each state is $0$. Previous work has observed [10], that if the gain
is $0$ at every vertex, then the bias represents the total reward that
can be obtained from each state. It is not difficult to prove that, after the
standard reduction has been applied, the total reward that can be obtained from
a vertex $v$ is larger than the total reward from a vertex $u$ if and only if
$\val^{\sigma}(u) \sqsubset \val^{\sigma}(v)$ in the original parity game. This
is because the rewards assigned by the standard reduction grow quickly enough so
that only the largest priority visited matters. Hence, we also have the
mean-payoff case of Corollary <ref>.

Björklund and Vorobyov have also devised a strategy improvement algorithm for
mean-payoff games. Their algorithm involves adding an extra sink vertex,
and then adding edges from every vertex of the maximizing player to the sink.
Their valuations are also the total reward obtained before reaching the sink. We
cannot show a similar result for their algorithm, but we can show a result for a
variant of their algorithm that only gives additional edges to a subset
of the vertices of the maximizing player. To do this, we do the same reduction
as we did for the gain-bias algorithm, and then we only add an edge from $x$ to
the new sink added the Björklund and Vorobyov. The same reasoning as above
then implies that the Björklund-Vorobyov algorithm will make the same switches
as the Vöge-Jurdziński algorithm.

Unique sink orientations.

As mentioned in the introduction, there is a relationship between strategy
improvement algorithms and sink-finding algorithms for unique sink orientations.
Our result already implies a similar lower bound for sink-finding algorithms
applied to unique sink orientations. However, since the vertices in our parity
game have more than two outgoing edges, these results only hold for unique sink
orientations of grids. The more commonly studied model is unique sink
orientations of hypercubes, which correspond to binary parity
games, where each vertex has at most two outgoing edges. We argue that our
construction can be formulated as a binary parity game.

Friedmann has already shown that his construction can be formulated as a binary
parity game [12], so we already have that the clocks can be transformed
so that they are binary. Furthermore, since our -gates and our
-gates are taken directly from Friedmann's bit gadget, we can apply
Friedmann's reduction to make these binary. In particular, note that all of the
extra states that we add to the input/output gate are binary, so these states do
not need any modification.

The only remaining part of the construction is the -gate, which has four
outgoing edges. We replace the existing gadget with a modified
gadget, shown in Figure <ref>.

Vertex     Conditions      Edges      Priority     Player

$o^j_i$     $j \in \{0, 1\}$, $i \in \org$     $s^j$, $o^j_{i,1}$
$\pp(4, i, 0, j, 1)$     Even

$o^j_{i,1}$     $j \in \{0, 1\}$, $i \in \org$     $r^j$, $o^j_{i,2}$    $\pp(4, i, 1,
j, 1)$     Even

$o^j_{i,2}$     $j \in \{0, 1\}$, $i \in \org$     $\inputstate(i,j,1)$,
$\inputstate(i,j,2)$    $\pp(4, i, 2, j, 1)$     Even

[node distance=1cm,font=]
[even] (o) $o^j_{i,2}$
[even] (i1) [below left=1cm and 0.5cm of o] $o^j_{\inp_1(i)}$;
[even] (i2) [below right=1cm and 0.5cm of o] $o^j_{\inp_2(i)}$;

[even] (o_2) [above=1cm of o] $o^j_{i,1}$
[even] (o_1) [above=1cm of o_2] $o^j_{i}$

[even] (r) [left=1cm of o_2] $r^j$;
[even] (s) [left=1cm of o_1] $s^j$;

(o_2) edge (r)
(o_2) edge (o)
(o_1) edge (s)
(o_1) edge (o_2)
(o) edge (i1)
(o) edge (i2)

The binary gate.

This gadget replaces the single vertex of the original -gate, with three
binary vertices. The only significant difference that this gadget makes to the
construction is that now it can take up to two strategy improvement iterations
for the -gate to compute its output. This is because, we may have to wait
for $o^j_{i,2}$ to switch before $o^j_{i, 1}$ can switch. The vertex $o^j_{i}$
always chooses the edge $o^j_{i, 1}$ during the computation, because the
valuation of $r^j$ is larger than the valuation of $s^j$.

To deal with this, we can redesign the construction so that each -gate $i$
is computed on iteration $2i$ rather than iteration $i$, and each -gate is
computed before iteration $2i$. This involved making the following changes:

* The length of the deceleration lane in the two clocks must be extended by
$2k$, to account for the $2k$ extra iterations it takes for the circuits to
compute ($k$ extra iterations for circuit $0$ and $k$ extra iterations for
circuit $1$.) Moreover, the delays for both of the clocks must be increased by

* For the same reason, the length of the modified deceleration lanes in the and gates must be increased by $2k$.

* Finally, the edge to $o^j_{\inputstate(i, j)}$ must be moved from $t_{i,
d(i)}$ to $t_{i, 2 d(i)}$.

Once these changes have been made, we have produced a binary parity game.

One final thing we must be aware of is that we only get a unique-sink
orientation if there is never a tie between the valuation of two vertices. This,
however, always holds in a one-sink game because every vertex has a distinct
priority, and therefore all paths necessarily contain a distinct set of
priorities, which prevents ties in the $\sqsubseteq$ ordering. Therefore, we
have the -completeness result for the BottomAntipodal algorithm
claimed in Corollary <ref>.

§ THE OPTIMAL STRATEGY RESULT

We are also able to prove a result about the complexity of determining which
optimal strategy is found by the Vöge-Jurdziński algorithm. However, we
cannot formulate this in the context of a one-sink game, because any result of
this nature must exploit ties in valuations. In a one-sink game, since
every vertex has a different priority, no two paths can have the same set of
priorities, so ties are not possible. Hence, for a one-sink game, there will be
a unique optimal strategy, and so the complexity of finding it can be no harder
than solving the parity game itself, and this problem is not -complete
unless = $\cap$ .

On the other hand, ties in valuations are possible in the original
Vöge-Jurdziński algorithm. This is because the first component of their
valuation is not necessarily $1$, and so the second component does not
necessarily contain every priority along the relevant path (recall that
priorities smaller than the first component are not included in the second
component.) These facts mean that it is possible to construct parity games that
have multiple optimal strategies under the Vöge-Jurdziński valuation.

Our construction.
We will use a slight modification of our construction to show that computing the
optimal strategy found by the Vöge-Jurdziński algorithm is -complete.
The key difference is the addition of a third clock with $n+1$ bits,
which will be indexed by $2$. We remove a single edge from this clock: the edge
from $e^2_{n+1}$ to $h^2_{n+1}$ is removed.

Recall that in the clock construction, the odd vertices $e^j_{i}$ do not use the
edge to $h^j_i$ unless they are forced to by the vertex $d^j_i$ selecting the
edge to $e^j_i$. Hence, until the $n+1$th bit is flipped, the third clock
behaves like any other clock. When the $n+1$th bit is flipped, after $2^n$
iterations have taken place, a new cycle is formed with a very large even

We also modify the edges that leave $d^1_z$. For each edge $e = (d^1_z, u)$ we
do the following:

* We delete $e$.

* We introduce a new vertex $v_u$ owned by player Even. This vertex is
assigned an insignificant priority that, in particular, is much smaller than the
priorities assigned to $e^2_{n+1}$ and $d^2_{n+1}$.

* We add the edges $(d^1_z, v_u)$, $(v_u, u)$, and $(v_u, f^2_{n+1})$.

The following table summarises the extra clock that we add to the construction,
and the new outgoing edges from $d^1_z$. For ease of notation, we define $U = \{
y^1, z^1, e^1_z\} \cup \{a^1_{z,l} \; : \; 1 \le l \le \lale\}$ to be the
original outgoing edges from $d^1_z$ that will now be replaced. Moreover, we
assume that each vertex $u$ is represented by a number in the range $1 \le u \le
|U|$, which will be used as part of the priority for $v_u$.

Vertex     Conditions      Edges      Priority     Player

$t_0^2$         $r^2$, $s^2$     $\pp(2, 0, 2k+4n+4, 2, 0)$     Even

$t_l^2$     $1 \le l \le \lale$     $r^2$, $s^2$, $t^2_{l-1}$
$\pp(2, 0, l, 2, 1)$     Even

$a_l^2$     $1 \le l \le \lale$     $t^2_l$     $\pp(2, 0, l
+1, 2, 0)$     Even

$d^2_i$     $1 \le i \le n$     $e^2_i$, $s^2$, $r^2$,     $\pp(1, i, 0, 2, 1)$     Even

$a^2_l $ for $1 \le l \le \laletwo + 2i$

$e^2_i$     $1 \le i \le n$     $d_i$     $\pp(1, i, 1, 2, 0)$

$g^2_i$     $1 \le i \le n$     $f^2_i$     $\pp(1, i, 2, 2, 1)$

$k^2_i$     $1 \le i \le n$     $x$, $g^2_l$, for $i < l \le
n$     $\pp(8, i, 0, 2, 1)$     Even

$f^2_i$     $1 \le i \le n$     $e^2_i$     $\pp(8, i, 1, 2, 1)$

$h^2_i$     $1 \le i \le n$     $k^2_i$     $\pp(8, i, 2, 2, 0)$

$s^2$         $x$, $f^2_l$ for $1 \le l \le n$     $\pp(7, 0, 0,
2, 0)$     Even

$r^2$         $x$, $g^2_l$ for $1 \le l \le n$     $\pp(7, 0, 1,
2, 0)$     Even

$v_u$     $u \in U$     $u$     $\pp(0, 0, 0, u, 0)$     Even

$d^1_z$         $v_u$ for all $u \in U$     $\pp(4,i,0,j,1)$     Even

-completeness. We now argue how this modified construction
provides a -hardness proof for the optimal strategy decision problem.
Before the $n+1$th bit of the third clock flips, the edge $(v_u, f^2_{n+1})$ is
never switchable due to the large odd priority assigned to $f^2_{n+1}$, so this
modification does not affect the computation of $F^{2^n}(B)$. On the other hand,
once the $n+1$th bit of the third clock flips, all edges of the form
$(v_u, f^2_{n+1})$ immediately become switchable, because the first component of
the valuation of $f^2_{n+1}$ is now a large even priority, and not $1$. So all
of these edges will be switched simultaneously.

The key thing to note is that, since the priorities assigned to the vertices
$v_u$ are insignificant, they do not appear in the second component of the
valuation, and so vertex $d^1_z$ is now indifferent between all of its outgoing
edges. Moreover, the vertices $v_u$ never switch away from
$f^2_{n+1}$ for the following reasons:

* The only even cycle that can be forced by player Even is the one that uses
$d^2_{n+1}$ and $e^2_{n+1}$. So, these vertices must select a strategy that
reaches this cycle eventually.

* All priorities used in the circuits are smaller than the priority of the
cycle between $d^2_{n+1}$ and $e^2_{n+1}$. So, the second component of the
valuation function is irrelevant, and the only way of improving the strategy
would be to find a shorter path to the cycle.

* The vertices $v_u$ are the only vertices that have edges to the third
clock, so the only way a vertex $v_u$ could reach the third clock would be to
travel through both circuits to reach $d^1_z$, and then use a different vertex
$v_{u'}$,  but this would be a much longer path, and therefore this would have a
lower valuation.

Hence, the vertices $v_u$ will never switch away from $f^2_{n+1}$.

Observe that, after $2^n$ iterations, the input/output gadgets in circuit $1-j$
store the value of $F^{2^n}(B)$, and therefore $d^1_z$ chooses the edge to
$e^j_z$ if and only if the $z$th bit of $F^{2^n}(B)$ is $1$. The above argument
implies that $d^1_z$ does not switch again, so in the optimal strategy found by
the algorithm, the vertex $d^1_z$ chooses the edge to $e^j_z$ if and only if the
$z$th bit of $F^{2^n}(B)$ is $1$. Thus, we have that computing the optimal
strategy found by the Vöge-Jurdziński strategy improvement algorithm is
-complete, as claimed in Theorem <ref>.

Other games.
We also get similar results for the gain-bias algorithm for mean-payoff games,
and the standard strategy improvement algorithms for discounted and simple
stochastic games. For the most part, we can still rely on the proof of Friedmann
for these results. This is because, although we do not have a one-sink game, the
game behaves as a one-sink game until the $n+1$th bit in the third clock is
flipped. An easy way to see this is to reinstate the edge between $e^2_{n+1}$
and $h^2_{n+1}$ to create a one-sink game, and observe that, since the edge is
not used in the best response until the $n+1$th bit is flipped, it cannot affect
the sequence of strategies visited by strategy improvement. Once the $n+1$th bit
has flipped, we only care about making $d^1_z$ indifferent between its outgoing
edges, and in this section we explain how this is achieved.

For mean-payoff games, we use the same reduction as we did in
Section <ref> to our altered construction. After doing this, we set
the weight of the vertices $v_u$ to $0$ to ensure that $d^1_z$ will be exactly
indifferent between all of its outgoing edges once these vertices switch to
$f^2_{n+1}$. This gives the result for the gain-bias algorithm in mean-payoff

For discounted games, once the standard reduction from mean-payoff to discounted
games has been applied, the proof of Friedmann already implies that the
discounted game algorithm makes the same decisions as the Vöge-Jurdziński
algorithm for the vertices other than $d^1_z$. The only worry is that the
discount factor may make the vertex $d^1_z$ not indifferent between some of its
outgoing edges. However, it is enough to note that all paths from $d^1_z$ to
$f^2_{n+1}$ have length $2$, and therefore the vertex will be indifferent no
matter what discount factor is chosen. This gives the result for the standard
strategy improvement algorithm for discounted games.

Finally, after applying the standard reduction from discounted to
simple-stochastic games, the proof of Friedmann can be applied to argue that the
valuations in the simple stochastic game are related to the valuations in the
discounted game by a linear transformation. Hence, $d^1_z$ will still be
indifferent between its outgoing edges after the $n+1$th bit is flipped. This
gives the result for the standard strategy improvement algorithm for simple
stochastic games. Thus, we have the claimed results from
Corollary <ref>.

§ OPEN PROBLEMS

Strategy improvement generalizes policy iteration which solves mean-payoff and
discounted-payoff Markov decision processes [32]. The exponential
lower bounds for greedy all-switches have been extended to MDPs. Fearnley showed
that the second player in Friedmann's construction [12] can be
simulated by a probabilistic action, and used this to show an exponential lower
bound for the all-switches variant of policy iteration of average-reward
MDPs [7].  This technique cannot be applied to the construction in this
paper, because we use additional Odd player states (in particular the vertices
$q^j_{i,1}$) that cannot be translated in this way. Can our -hardness
results be extended to for MDPs?

Also, there are other pivoting algorithms for parity games that deserve
attention. It has been shown that Lemke's algorithm and the Cottle-Dantzig
algorithm for the P-matrix linear complementarity problem (LCP) can be applied
to parity, mean-payoff, and discounted games [24, 9]. It would be
interesting to come up with similar -completeness results for these
algorithms, which would also then apply to the more general P-matrix LCP

[1]
I. Adler, C. H. Papadimitriou, and A. Rubinstein.
On simplex pivoting rules and complexity theory.
In Proc. of IPCO, pages 13–24, 2014.

[2]
A. Condon.
The complexity of stochastic games.
Information and Computation, 96(2):203–224, 1992.

[3]
A. Condon.
On algorithms for simple stochastic games.
In Advances in Computational Complexity Theory, volume 13 of
DIMACS Series in Discrete Mathematics and Theoretical Computer Science,
pages 51–73. American Mathematical Society, 1993.

[4]
Y. Disser and M. Skutella.
The simplex algorithm is np-mighty.
In Proc. of SODA, pages 858–872, 2015.

[5]
E. A. Emerson and C. S. Jutla.
Tree automata, mu-calculus and determinacy.
In Proc. of FOCS, pages 368–377, 1991.

[6]
E. A. Emerson, C. S. Jutla, and A. P. Sistla.
On model-checking for fragments of $\mu$-calculus.
In Proc. of CAV, 1993.

[7]
J. Fearnley.
Exponential lower bounds for policy iteration.
In Proc. of ICALP, pages 551–562, 2010.

[8]
J. Fearnley.
Non-oblivious strategy improvement.
In Proc. of LPAR, 2010.

[9]
J. Fearnley, M. Jurdziński, and R. Savani.
Linear complementarity algorithms for infinite games.
In Proc. of SOFSEM, pages 382–393, 2010.

[10]
J. Fearnley and R. Savani.
The complexity of the simplex method.
In Proc. of STOC, pages 201–208, 2015.

[11]
J. Filar and K. Vrieze.
Competitive Markov Decision Processes.
Springer, 1997.

[12]
O. Friedmann.
An exponential lower bound for the latest deterministic strategy
iteration algorithms.
Logical Methods in Computer Science, 7(3), 2011.

[13]
O. Friedmann, T. D. Hansen, and U. Zwick.
A subexponential lower bound for the random facet algorithm for
parity games.
In Proc. of SODA, pages 202–216, 2011.

[14]
O. Friedmann, T. D. Hansen, and U. Zwick.
Subexponential lower bounds for randomized pivoting rules for the
simplex algorithm.
In Proc. of STOC, pages 283–292, 2011.

[15]
B. Gärtner, W. D. J. Morris, and L. Rüst.
Unique sink orientations of grids.
Algorithmica, 51(2):200–235, 2008.

[16]
B. Gärtner and I. Schurr.
Linear programming and unique sink orientations.
In Proc. of SODA, pages 749–757, 2006.

[17]
P. W. Goldberg, C. H. Papadimitriou, and R. Savani.
The complexity of the homotopy method, equilibrium selection, and
Lemke-Howson solutions.
ACM Trans. Economics and Comput., 1(2):9, 2013.

[18]
E. Grädel, W. Thomas, and T. Wilke, editors.
Automata, Logics, and Infinite Games. A Guide to Current
Research, volume 2500 of LNCS.
Springer, 2002.

[19]
T. D. Hansen, M. Paterson, and U. Zwick.
Improved upper bounds for random-edge and random-jump on abstract
In Proc. of SODA, pages 874–881, 2014.

[20]
A. J. Hoffman and R. M. Karp.
On nonterminating stochastic games.
Management Science, 12(5):359–370, 1966.

[21]
D. S. Johnson, C. H. Papadimitriou, and M. Yannakakis.
How easy is local search?
J. Comput. Syst. Sci., 37(1):79–100, 1988.

[22]
M. Jurdziński.
Deciding the winner in parity games is in UP $\cap$ co-UP.
Information Processing Letters, 68(3):119–124, 1998.

[23]
M. Jurdziński, M. Paterson, and U. Zwick.
A deterministic subexponential algorithm for solving parity games.
In Proc. of SODA, pages 117–123, 2006.

[24]
M. Jurdziński and R. Savani.
A simple P-matrix linear complementarity problem for discounted
In Proc. of CiE, pages 283–293, 2008.

[25]
G. Kalai.
A subexponential randomized simplex algorithm.
In Proc. of STOC, pages 475–482, 1992.

[26]
W. Ludwig.
A subexponential randomized algorithm for the simple stochastic game
Information and Computation, 117(1):151–155, 1995.

[27]
J. Matoušek, M. Sharir, and E. Welzl.
A subexponential bound for linear programming.
Algorithmica, 16(4–5):498–516, 1996.

[28]
J. Matoušek and T. Szabó.
Random edge can be exponential on abstract cubes.
In Proc. of FOCS, pages 92–100, 2004.

[29]
A. W. Mostowski.
Games with forbidden positions.
Technical Report 78, University of Gdańsk, 1991.

[30]
C. H. Papadimitriou.
On the complexity of the parity argument and other inefficient proofs
of existence.
Journal of Computer and System Sciences, 48(3):498–532, 1994.

[31]
A. Puri.
Theory of Hybrid Systems and Discrete Event Systems.
PhD thesis, University of California, Berkeley, 1995.

[32]
M. L. Puterman.
Markov Decision Processes: Discrete Stochastic Dynamic
John Wiley & Sons, Inc. New York, NY, USA, 2005.

[33]
S. Schewe.
An optimal strategy improvement algorithm for solving parity and
payoff games.
In Proc. of CSL, pages 369–384, 2008.

[34]
I. Schurr and T. Szabó.
Jumping doesn't help in abstract cubes.
In Proc. of IPCO, pages 225–235, 2005.

[35]
S. Smale.
Mathematical problems for the next century.
The Mathematical Intelligencer, 20(2):7–15, 1998.

[36]
C. Stirling.
Local model checking games.
In Proc. of CONCUR, pages 1–11, 1995.

[37]
T. Szabó and E. Welzl.
Unique sink orientations of cubes.
In Proc. of FOCS, pages 547–555, 2001.

[38]
J. Vöge and M. Jurdziński.
A discrete strategy improvement algorithm for solving parity games.
In Proc. of CAV, pages 202–215, 2000.

[39]
U. Zwick and M. S. Paterson.
The complexity of mean payoff games on graphs.
Theoretical Computer Science, 158(1–2):343–359, 1996.

§ FACTS ABOUT THE CLOCK

In this section we prove two important lemmas about the clocks. The first lemma
shows an important property about the difference in valuation between $r^j$ and
$s^j$ for the clock used by circuit $j$. The second lemma considers the
difference in valuation across the two clocks, by  comparing the
valuations of $r^j$, $s^j$, $r^{1-j}$, and $s^{1-j}$.

Let $\sigma$ be a strategy that agrees with $\kappa^\C_m$ for
some $m$ in the range $1 \le m \le \length(\C)$, some clock-value $\C
\in \{0, 1\}^n$, and some $j \in \{0, 1\}$. We have:

*  If $m = \length(\C) -1$ then $\val^{\sigma}(r^j)
\sqsubset \val^{\sigma}(s^j)$.

*  If $m < \length(\C) - 1$ then $\val^{\sigma}(s^j)
\sqsubset \val^{\sigma}(r^j)$.

In both cases, we have that $\maxdiff^{\sigma}(s^j, r^j) \ge \pp(7, 0, 0, 0,

We begin with the first case. In this case, by definition, we have that the path
that starts at $s^j$ and follows $\sigma$ moves to $f^j_i$ for some $i$, whereas
the path that starts at $r^j$ and follows $\sigma$ moves to $g^j_{i'}$ for some
$i' \ne i$. There are two possibilities.

* If $i > i'$, then since $i$ is the least significant zero in $\C$, we must
have that $i' = \nexbit(\C, 0) = 1$. Hence, the path that starts at $g^j_{i'}$
passes through the bit gadgets for all bits strictly smaller than $i$ before
eventually arriving at $g^j_{\nexbit(\C, i)}$ (or $x$ if $\nexbit(\C, i)$ is not
defined.) In particular, since the path does not pass through $h^j_i$ the
largest priority on the path is strictly smaller than $\pp(8, i, 2, j, 0)$.

On the other hand, the path that starts at $f^j_i$ eventually arrives at
$g^j_{\nexbit(\C, i)}$ (or $x$ if $\nexbit(\C, i)$ is not defined) and it
does pass through $h^j_i$. The largest priority on this path is  $\pp(8,
i, 2, j, 0)$, and since the priority is even, we can conclude that
$\val^{\sigma}(r^j) \sqsubset \val^{\sigma}(s^j)$.

* If $i < i'$, then since $i'$ is the least significant one in $\C$, we must
have that $i = 1$. Hence, the path that starts at $f^j_i$ eventually moves to
$k^j_i$ and then directly to $g^j_{i'}$. The largest priority on this path is
$\pp(8, i', 2, j, 0)$, and since this is even, we can conclude that
$\val^{\sigma}(r^j) \sqsubset \val^{\sigma}(s^j)$.

We now move on to the second case. In this case, by definition, we have that the
path that starts at $s^j$ moves to $f^j_i$ for some $i$, whereas the path that
starts at $r^j$ moves to $g^j_i$ and then to $f^j_i$. Since the priority on
$g^j_i$ is strictly smaller than $\pp(7, 0, 1, j, 0)$, we have that
$\maxdiff^{\sigma}(r^j, s^j) = \pp(7, 0, 1, j, 0)$, which the priority assigned
to $r^j$. Since this priority is even, we have that $\val^{\sigma}(s^j)
\sqsubset \val^{\sigma}(r^j)$, as required.

Observe that in all cases considered above, we have shown that
$\maxdiff^{\sigma}(r^j, s^j) \ge \pp(7, 0, 0, 0, 0)$ as required. Hence, we have
completed the proof of this lemma.

Let $\sigma$ be a strategy that agrees with $\chi^{B, \C, j}_m$ for some $m \ge
1$, some bit-strings $B, \C \in \{0, 1\}^n$, and some $j \in \{0, 1\}$. We have:

*  If $m = \delay(j, \C) - 1$, then $\val^{\sigma}(r^{1-j})
\sqsubset \val^{\sigma}(r^{j}) \sqsubset \val^{\sigma}(s^{1-j})$ and
$\maxdiff^\sigma(r^{1-j}, s^j) \ge \pp(7, 0, 0, 0, 0)$ and
$\maxdiff^\sigma(r^{1-j}, r^j) \ge \pp(7, 0, 0, 0, 0)$.

*  If $m < \delay(j, \C) - 1$, then
$\val^{\sigma}(r^{1-j}) \sqsubset \val^{\sigma}(s^j) \sqsubset \val^{\sigma}(r^{j})$ and $\maxdiff^\sigma(r^{1-j}, s^{j}) \ge \pp(7, 0, 0,
0, 0)$
and $\maxdiff^\sigma(s^{j}, r^{1-j}) \ge \pp(7, 0, 0, 0, 0)$.

We begin with the second claim. The fact that $\val^{\sigma}(s^j) \sqsubset
\val^{\sigma}(r^j)$ follows from part <ref> of
Lemma <ref>, so it is sufficient to show that
$\val^{\sigma}(r^{1-j}) \sqsubset \val^{\sigma}(s^j)$. There are two cases to
consider, based on whether $j = 0$ or $j = 1$.

* If $j = 0$, then clock $j$ uses bit-string $\C$, and clock $1-j$ uses
bit-string $\C - 1$. Observe that the clock strategies specify that the path
starting at $s^{j}$ visits $h^j_i$ if and only if $\C_i = 1$. Similarly, the
path starting at $r^{1-j}$ visits $h^{1-j}_i$ if and only if $(\C - 1)_i = 1$.
If $i'$ is the index of the least significant $1$ in $\C$, then we have that the
path that starts at $s^j$ visits $h^j_{i'}$ and $k^j_{i'}$, and the path that
starts at $s^{1-j}$ does not visit these vertices. Moreover, these two paths are
the same after this point. Hence, we have that $\maxdiff(s^j, r^{1-j})$ is
$\pp(8, i', 2, j, 0)$, and since this priority is even, we can conclude that
$\val^{\sigma}(r^{1-j}) \sqsubset \val^{\sigma}(s^j)$.

* If $j = 1$, then both clocks use bit-string $\C$. Hence, the paths
starting at $s^j$ and $r^{1-j}$ use the same path through their respective
clocks. So, if $i'$ is the index of the most significant $1$ in $\C$, then we
have that
$\pp(8, i', 2, 0, 0)$ is the largest priority on the path starting at $r^{1-j} =
r^0$, and
$\pp(8, i', 2, 1, 0)$ is the largest priority on the path starting at $s^{j} =
s^1$. Thus, $\maxdiff^{\sigma}(s^j, r^{1-j}) = \pp(8, i', 2, 1, 0)$, and since
this priority is even and contained in $\val^{\sigma}(s^j)$ we can conclude that
$\val^{\sigma}(r^{1-j}) \sqsubset \val^{\sigma}(s^j)$.

We now move on to the first claim. Here the same reasoning as we gave for the
second case can be used to prove that $\val^{\sigma}(r^{1-j}) \sqsubset
\val^{\sigma}(s^j)$, and therefore Lemma <ref> implies that
$\val^{\sigma}(r^{1-j}) \sqsubset \val^{\sigma}(r^j)$. What remains is to prove
$\val^{\sigma}(r^j) \sqsubset \val^{\sigma}(s^{1-j})$. Again there are two cases
to consider.

* If $j = 0$, then clock $j$ uses bit-string $\C$, and clock $1-j$ is about
to transition from bit-string $\C-1$ to bit-string $\C$. In fact, the path from
$s^{1-j}$ is already the path for bit-string $\C$, so the proof from item $2$
above can be reused.

* If $j = 1$, then clock $j$ uses bit-string $\C$, and clock $1-j$ is about
to transition from bit-string $\C$ to bit-string $\C+1$. In fact, the path from
$s^{1-j}$ is already the path for bit-string $\C+1$, so the proof from item $1$
above can be reused.

Finally, we observe that all of the maximum difference priorities used in the
proof are strictly larger than $\pp(7, 0, 0, 0, 0)$, which completes the proof.

§ BEST RESPONSES

In this section, we prove that the best responses defined in
Section <ref> are indeed best responses to $\chi^{B, \C, j}_m$.
There are two types of odd vertices used in the construction: the vertices
$e^j_i$ used in the and gates, and the vertices $q^j_{i, 0}$ used
in the gates. We begin by proving a general lemma concerning the
vertices $e^j_i$ used in the and gates.

Let $\sigma $ be a strategy that agrees with $\chi^{B, \C, j}_m$ for some
bit-strings $B, \C \in \{0, 1\}^n$, some $m$ in the range $1 \le m \le \delay(j,
\C) - 1$,  and some $j \in \{0, 1\}$. For every $i \in \notg \cup \inputg$, and
every $l \in \{0, 1\}$, we have that if $\sigma(d^l_{i}) = e^l_i$, then
$\br(\sigma)(e^l_i) \ne d^l_i$.

Note that if player Odd uses the edge from $e^l_i$ to $d^l_i$, then this would
create a cycle with largest priority $\pp(1, i, 1, j, 0)$, which is even. Since
the game is a one-sink game, and since the initial strategy is terminating, we
have that Odd can eventually reach the odd cycle at $x^j$ from the vertices
$r^j$, $r^{1-j}$, $s^j$, and $s^{1-j}$. Furthermore, Odd can reach one of these
four vertices by moving to $h^l_i$. Since the odd cycle at $x^j$ has priority
smaller than $\pp(1, i, 1, j, 0)$, we can conclude that $\br(\sigma)(e^j_i) \ne

We now proceed to prove individual lemma for each of the vertices that belong to
player Odd. Each type of Odd vertex will be considered in a different

§.§ The vertices $q^l_{i, 0}$

We now consider the vertices $q^l_{i,
0}$ for $i \in \inputg$. The first lemma considers the case where $l = j$, and
the second lemma considers the case where $l = 1-j$.

Let $\sigma $ be a strategy that agrees with $\chi^{B, \C, j}_m$ for some
bit-strings $B, \C \in \{0, 1\}^n$, some $m$ in the range $1 \le m \le \delay(j,
\C) - 1$,  and some $j \in \{0, 1\}$.
For every $i \in \inputg$, we have that $\br(\sigma)(q^{j}_{i,0}) = \mu^{B,
\C, j}_m(q^j_{i,0})$.

There are two cases to consider.

* If $m = 1$, then then we must show that the edge to $e^j_{i}$ is chosen by
Odd in the best response.
Consider a strategy $\tau$
$\tau(e^j_i) = h^j_{i,0}$, and
$\tau(q^j_{i,0}) = e^j_i$. When $\tau$ is played against $\sigma$, the path that
starts at $e^j_i$ eventually arrives at $r^{1-j}$, and the largest priority on this path is
strictly smaller than
$\pp(6, d(C) + 2, 0, j, 0)$.
On the other hand, taking the edge to $q^j_{i, 1}$ leads directly to $r^{1-j}$
while visiting the priority
$\pp(6, d(C) + 2, 0, j, 0)$. Since this priority is even, we can conclude that
Odd would prefer to play $\tau$ than to use the edge from $q^j_{i, 0}$ to
$q^j_{i, 1}$ in his best response. Therefore, we must have that
$\br(\sigma)(q^j_{i, 0}) = e^j_i$, as required.

* If $m > 1$, then we must show that the edge to $q^{j}_{i,1}$ is the least
appealing edge at $q^{j}_{i, 0}$. Observe that the path that starts at $e^{j}_i$
and follows $\sigma$ eventually arrives at $r^j$, and every priority on this
path that is strictly smaller than $\pp(7, 0, 0, 0, 0)$. On the other hand, the
path that starts at $q^j_{i, 1}$ moves directly to $r^{1-j}$. Hence, we can
apply Lemma <ref> (both parts) to argue that
$\val^{\sigma}(q^{j}_{i, 1}) \sqsubset \val^{\sigma}(e^j_i)$, as required.

Let $\sigma $ be a strategy that agrees with $\chi^{B, \C, j}_m$ for some
bit-strings $B, \C \in \{0, 1\}^n$, some $m$ in the range $1 \le m \le \delay(j,
\C) - 1$,  and some $j \in \{0, 1\}$.
For every $i \in \inputg$, we have that $\br(\sigma)(q^{1-j}_{i,0}) = \mu^{B,
\C, j}_m(q^{1-j}_{i,0}$.

We must show that the edge to $e^{1-j}_i$ is the least
appealing edge at $q^{1-j}_{i, 0}$. Observe that the path that starts at
$e^{1-j}_i$ and follows $\sigma$ will eventually arrive at either $r^j$ or
$r^{1-j}$. In either case, the largest priority on this path will be strictly
smaller than
$\pp(6, d(C) + 2, 0, j, 0)$. On the other hand, the path that starts at
$q^{1-j}_{i, 1}$ moves directly to $r^j$, and the largest priority on this path
$\pp(6, d(C) + 2, 0, j, 0)$. Since this priority is even, we can conclude that
$\val^{\sigma}(e^{1-j}_i) \sqsubset \val^{\sigma}(q^{1-j}_{i, 0})$, as required.

§.§ The vertices $e^l_i$ in gates

The following lemma considers the vertices $e^l_i$ for $l = j$ and $i \in
\notg$. We do not need to prove a lemma for the case where $l = 1-j$ and $i \in
\notg$, because these vertices are in the non-computing circuit, and we do not
specify strategies for the and gadgets in the non-computing circuits.

Let $\sigma$ be a strategy that agrees with $\chi^{B, \C, j}_m$ for some
bit-strings $B, \C \in \{0, 1\}^n$, some $m$ in the range $1 \le m \le \delay(j,
\C) - 1$,  and some $j \in \{0, 1\}$.
For every $i \in \notg$, we have that $\br(\sigma)(e^{j}_{i}) = \mu^{B,
\C, j}_m(e^j_i)$.

There are three cases to consider.

* If $m = 1$ then, the path that starts at $d^j_i$ and follows $\sigma$
moves directly to $s^j$. On the other hand, the path that starts at
$h^j_i$ moves directly to $r^j$.
All of the priorities on these paths are strictly
smaller than $\pp(7, 0, 0, 0, 0)$, so we can apply Lemma <ref>
part <ref> to argue that $\val^{\sigma}(d^j_i) \sqsubset
\val^{\sigma}(d^j_i)$, so therefore we have $\br(\sigma)(e^j_i) = d^j_i$.

* If $m > 1$ and either $m \le d(i) + 2$, or $m > d(i) + 2$ and $\eval(B,
\inp(i)) = 1$, then observe that the path that starts at $d^j_i$ and follows
$\sigma$ eventually arrives at $r^j$, and that the largest priority on this path
is strictly smaller than $\pp(6,i,1,j,0)$. On the other hand, the path that
starts at $h^j_i$ and follows $\sigma$ moved directly to $r^j$, and the largest
priority on this path is $\pp(6,i,1,j,0)$. Since this priority is even, we can
conclude that $\val^{\sigma}(d^j_i) \sqsubset \val^{\sigma}(e^j_i)$, so
therefore we have $\br(\sigma)(e^j_i) = d^j_i$.

* If $m > d(i) + 2$ and $\eval(B, \inp(i)) = 0$, then we have
$\sigma(d^j_i) = e^j_i$, so we can apply Lemma <ref> to prove that
$\br(\sigma)(e^j_i) = h^j_i$.

§.§ The vertices $e^j_i$ in input/output gates

The following lemmas consider the vertices $e^l_i$ when $i \in \inputg$. The
first lemma considers the case where $l = j$, and the second lemma considers the
case where $l = 1-j$.

Let $\sigma$ be a strategy that agrees with $\chi^{B, \C, j}_m$ for some
bit-strings $B, \C \in \{0, 1\}^n$, some $m$ in the range $1 \le m \le \delay(j,
\C) - 1$,  and some $j \in \{0, 1\}$.
For every $i \in \inputg$, we have that $\br(\sigma)(e^{j}_{i}) = \mu^{B,
\C, j}_m(e^j_i)$.

There are a number of cases to consider.

* If $m > 1$ and $F^2(B)_i = 0$ and either $m \le d(i)+3$, or $m > d(i) +3$
and $F^2(B)_i = 0$, then the path that starts at $d^j_i$ eventually arrives at
$r^j$, and the largest priority on this path is strictly smaller than
$\pp(6,d(C)+1,1,j,0)$. On the other hand, the path that starts at $h^j_{i, 0}$
and follows $\sigma$ passes through $h^j_{i, 1}$ and then arrives at $r^j$. The
largest priority on this path is
$\pp(6,d(C)+1,1,j,0)$, and since this priority is even, we can conclude that
$\val^{\sigma}(d^j_i) \sqsubset \val^{\sigma}(h^j_{i, 0})$. Therefore, we have
$\br(\sigma)(e^j_i) = d^j_{i}$.

* If $m > 1$ and $m > d(i) + 3$ and $F^2(B)_i = 1$, then $\sigma(d^j_i) =
e^j_i$, and so we can apply Lemma <ref> to argue that
$\br(\sigma)(e^j_i) = h^j_{i,0}$.

Let $\sigma$ be a strategy that agrees with $\chi^{B, \C, j}_m$ for some
bit-strings $B, \C \in \{0, 1\}^n$, some $m$ in the range $1 \le m \le \delay(j,
\C) - 1$,  and some $j \in \{0, 1\}$.
For every $i \in \inputg$, we have that $\br(\sigma)(e^{1-j}_{i}) = \mu^{B,
\C, j}_m(e^{1-j}_i)$.

There are a number of cases to consider.

* If $m = 1$ and $B_i = 0$, then the path that starts at $d^{1-j}_i$ and
follows $\sigma$ will eventually reach $r^{1-j}$, and the largest priority on
this path is strictly smaller than $\pp(6,d(C)+1,1,j,0)$. On the other hand, the path that starts at
$h^{1-j}_{i, 0}$ moves to $h^{1-j}_{i, 1}$ and then arrives at $r^{1-j}$, and
the largest priority on this path is $\pp(6,d(C)+1,1,j,0)$. Since this priority
is even, we have that $\val^{\sigma}(d^{1-j}_i) \sqsubset
\val^{\sigma}(h^{1-j}_{i,0})$ and therefore $\br(\sigma)(e^{1-j}_i) =

* $m > 1$ and $B_i = 0$, then the path that starts at $d^{1-j}_i$ moves
to $r^j$, and the largest priority on this path is strictly smaller than $\pp(6,
0, 1, j, 0)$. On the other hand, the path that starts at $h^{1-j}_{i, 0}$ moves
to $h^{1-j}_{i, 2}$ and then arrives at $r^{j}$, and the largest priority on
this path is $\pp(6, 0, 1, j, 0)$. Since this priority is even, we have that
$\val^{\sigma}(d^{1-j}_i) \sqsubset \val^{\sigma}(h^{1-j}_{i,0})$ and therefore
$\br(\sigma)(e^{1-j}_i) = d^{1-j}_{i}$.

* If $B_i = 1$, then we have $\sigma(d^{1-j}_i) = e^{1-j}_i$, and we can
apply Lemma <ref> to argue that $\br(\sigma)(e^{1-j}_i) =

§.§ Gate outputs

In this section we give two key lemmas that describe the valuation of the output
states $o^j_i$. The first lemma considers the case where $m = 1$ or $m = 2$, and
the second lemma considers the case where $m \ge 3$.

Let $\sigma$ be a strategy that agrees with $\chi^{B, \C, j}_m$ for some $\C, B
\in \{0, 1\}^n$, some $j \in \{0, 1\}^n$, and for $m = 1$ or $m = 2$. For every
gate $i$, we have $\val^{\sigma}(o^j_i) \sqsubset \val^{\sigma}(r^j)$.

There are four cases to consider

* We begin by showing the claim for an input/output gate $i$ from circuit $1-j$ in
the case where $m = 1$. Note that
Lemma <ref> implies that $\br(\sigma)(e^{1-j}_i) = d^{1-j}_i$.
Observe that by definition, the path that starts at $d^j_i$ and follows $\sigma$
will trace a path through the gadgets for circuit $1-j$, and will eventually
reach $r^{1-j}$. Furthermore, the largest priority possible that can be seen
along this path is $\pp(6, d(C)+1, 1, j, 0) < \pp(7, 0, 0, 0, 0)$. Hence, we can
apply Lemma <ref> to argue that $\val^{\sigma}(o^{1-j}_i)
\sqsubset \val^{\sigma}(r^j)$.

* Now we consider an input/output gate $i$ from circuit $1-j$ in the case where $m =
2$. Again, Lemma <ref> implies that
$\br(\sigma)(e^{1-j}_i) = d^{1-j}_i$, but in this case
since $m = 2$, we have that the vertices $y^{1-j}$ and $p^{1-j}_i$ have both switched to $r^j$. Hence,
the path that starts at $o^{1-j}_i$
will eventually arrive at $r^j$.
It can be verified that, whatever path is taken from $o^{1-j}_{i}$ to $r^j$, the largest priority
along this path is $\pp(6, i, 0, j, 1)$ on the vertex $o^{1-j}_{i}$. Since this
priority is odd, we have that $\val^{\sigma}(o^{1-j}_i) \sqsubset
\val^{\sigma}(r^j)$.

* Next we consider the case where $i$ is a -gate. If $m = 1$ then we
have that $\sigma(o^j_i) = s^j$, and if $m = 2$ then $\sigma(o^j_i) = r^j$. In
both cases,  we can use Lemma <ref> and the fact that the priority
assigned to $o^j_i$ is odd, to conclude that $\val^{\sigma}(o^{j}_i) \sqsubset
\val^{\sigma}(r^j)$.

* Finally, we consider the case where $i$ is a -gate. We can apply
Lemma <ref> to argue that $\br(\sigma)(e^j_i) = d^j_i$. If $m = 1$
then we have that $\sigma(d^j_i) = s^j$, and if $m = 2$ then $\sigma(d^j_i) =
r^j$. In both cases, the  highest priority on the path from $o^j_i$ to either
$s^j$ or $r^j$ is the odd priority from $o^j_i$, so we can use this fact, along
with Lemma <ref> to conclude that $\val^{\sigma}(o^{j}_i) \sqsubset
\val^{\sigma}(r^j)$.

Let $\sigma$ be a strategy that agrees with $\chi^{B, \C, j}_m$ for some $\C, B
\in \{0, 1\}^n$, some $j \in \{0, 1\}^n$, and some $m$ in the range $3 \le m \le
\delay(j, \C$. For every gate $i$, we have:

*  If $m \le d(i) + 2$, then $\val^{\sigma}(o^j_i) \sqsubset
\val^{\sigma}(r^j)$.

*  If $m > d(i) + 2$ and $\eval(B, i) = 0$, then
$\val^{\sigma}(o^j_i) \sqsubset \val^{\sigma}(r^j)$.

*  If $m > d(i) + 2$ and $\eval(B, i) = 1$, then
$\val^{\sigma}(r^j)  \sqsubset \val^{\sigma}(o^j_i)$ and:

\begin{equation*}
\pp(6,0,0,0,0) \le \maxdiff^{\sigma}(r^j, o^j_i) \le \pp(6, i, 1, j, 0).
\end{equation*}

We will prove this claim by induction over the depth of the gates. For the base
case we consider an input/output gate $i$ from circuit $1-j$, which provide the input
values for circuit $j$. Since we consider these gates to have depth $0$, we
always have $m > d(i) + 2$, so there are two cases to prove based on whether
$B_i$ is zero or one. First, observe that since $m \ge 3$, the circuit mover
gadgets attached to the input/output gadget for bit $i$ in circuit $1-j$ have
$\sigma(y^{1-j}) = r^{j}$. Since $\delay(1-j,\C) \ge d(C) + 3$, the definition
given in (<ref>) implies that the strategy at $d^{1-j}_i$ is
determined by $B_i$. So we have the following two cases.

* If $B_i = 0$, then $\sigma(d^{1-j}_i) = a^{1-j}_{i,l}$ for some $l$. By
definition, in the strategy $\sigma$, all paths from $a^{1-j}_{i,l}$ eventually
arrive at $r^j$, and the maximum priority on any of these paths is smaller than
$\pp(6,0,0,j,1)$. Hence, the largest priority on the path from $o^{1-j}_i$ to
$r^j$ is the priority $\pp(6,0,0,j,1)$ on the vertex $o^{1-j}_i$, and since this
is an odd priority, we have $\val^{\sigma}(o^{1-j}_i) \sqsubset
\val^{\sigma}(r^{j})$.

* If $B_i = 1$, then $\sigma(d^{1-j}_i) = e^{1-j}_i$ and
Lemma <ref> then implies $\br(\sigma)(e^{1-j}_i) = h^{1-j}_i$. So, the
path that starts at $o^{1-j}_i$ and follows $\sigma$ passes through $e^{1-j}_i$,
$h^{1-j}_{i,0}$, $h^{1-j}_{i,2}$, and then arrives at $r^j$. The largest
priority on this path is $\pp(6,0,1,j,0) > \pp(6, 0, 0, j, 1)$ on the state
$h^{1-j}_{i,2}$, so we have $\val^{\sigma}(r^j) \sqsubset
\val^{\sigma}(o^{1-j}_i)$

Hence, the base case of the induction has been shown. The inductive step will be
split into two cases, based on whether $i$ is a -gate or an -gate.

Suppose that the inductive hypothesis holds for all gates $i$ with $d(i) < k$,
and let $i$ be a -gate with $d(i) = k$. We must prove three cases.

* The first two cases use the same proof. If $m \le d(i)+2$,
or if $m > d(i) + 2$ and $\eval(B, i) = 0$, then by definition we have
$\sigma(o^j_i) = r^j$. Since the priority assigned to $o^j_i$ is odd, we have
$\val^{\sigma}(o^j_i) \sqsubset \val^{\sigma}(r^j)$, as required.

* If $m > d(i) + 2$ and $\eval(B, i) = 1$, then by definition we have that
$\sigma(o^j_i) = \inputstate(i, j, l)$ for some gate $l$ with $l \in \{1, 2\}$,
and we know that $\eval(B, \inp_l(i)) = 1$. Hence, we can apply
the inductive hypothesis to argue that $\maxdiff^{\sigma}(r^j,
\inputstate(i,j,l))$ is even,
and it satisfies:

\begin{equation*}
\pp(6,0,0,0,0) \le \maxdiff^{\sigma}(r^j, \inputstate(i,j,l)) \le \pp(6, l, 1, j, 0).
\end{equation*}

Since the priority assigned to $o^j_i$ is smaller than $\pp(6,0,0,0,0)$, we have
that the same two properties apply to $\maxdiff^{\sigma}(r^j, o^j_i)$. Hence,
$\val^{\sigma}(r^j)  \sqsubset \val^{\sigma}(o^j_i)$, and the required bounds on
$\maxdiff^{\sigma}(r^j, o^j_i)$ hold because $\pp(6, l, 1, j, 0) < \pp(6, i, 1,
j, 0)$.

Now suppose that the inductive hypothesis holds for all gates $i$ with $d(i) <
k$, and let $i$ be a -gate with $d(i) = k$. We must prove three cases.

* If $m \le d(i) + 2$, then by definition, the path that starts at $o^j_i$ and follows
$\sigma$ passes through $e^j_i$, and Lemma <ref> implies that it then
moves to $d^j_i$, a vertex of the form $a^j_{i,l}$, a number of vertices
of the form $t^j_{i,l}$, before finally arriving at $r^j$. It can easily be
verified that the largest priority on this path is $\pp(6, i, 0, j, 1)$ from the
vertex $o^j_i$. So, we have $\maxdiff^{\sigma}(r^j, o^j_i) = \pp(6, i, 0, j,
1)$, and since this priority is odd, we have $\val^{\sigma}(o^j_i) \sqsubset
\val^{\sigma}(r^j)$, as required.

* If $m > d(i) + 2$ and $\eval(B, i) = 0$, then we must have $\eval(B,
\inp(i)) = 1$. Hence, by definition, the path that starts at $o^j_i$ and follows
$\sigma$ first passes through $e^j_i$, and then Lemma <ref> implies that
it then passes through $d^j_i$, and then some vertex of the form $a^j_{i,l}$,
followed by a number of vertices of the form $t^j_{i,l}$, before finally
arriving at $t^j_{i, d(i)}$ and then moving to $\inputstate(i,j)$. The largest
priority on this path is $\pp(6, i, 0, j, 1)$ from the vertex $o^j_i$. By the
inductive hypothesis, we have $\maxdiff^{\sigma}(r^j, \inputstate(i,j)) < \pp(6,
\inp(i), 1, j, 0)$, and since $\inp(i) < i$ we have that $\pp(6, i, 0, j, 1) >
\pp(6, \inp(i), 1, j, 0)$. Hence, we have that $\maxdiff^{\sigma}(r^j,
o^j_{\inp(i)}) = \pp(6, i, 0, j, 1)$, and since this is odd, we have that
$\val^{\sigma}(o^j_i) \sqsubset \val^{\sigma}(r^j)$, as required.

* If $m > d(i) + 2$ and $\eval(B, i) = 1$, then by definition we have
that the path that starts at $o^j_i$ and follows $\sigma$ passes through
$e^j_i$, and then Lemma <ref> implies that it passes through $h^j_i$, and