An Exponential Lower Bound for the Latest Deterministic Strategy Iteration Algorithms

Introduction

In this paper, we study lower bounds for strategy improvement algorithms for solving parity games, mean payoff games, discounted payoff games as well as simple stochastic games. These are two-player games of perfect information played on directed graphs, and are related by a chain of polynomial-time reductions.

Parity games can be reduced to mean payoff games [Pur95], mean payoff games to discounted payoff games, and the latter ones to simple stochastic games [ZP96]. Solving games of any of these classes is one of the few combinatorial problems that belongs to the complexity class $\mathtt{NP}\cap\mathtt{coNP}$ and that is not (yet) known to belong to $\mathtt{P}$ [EJS93, Con92]. It has also been shown that solving parity games as well as mean and discounted payoff games belongs to $\mathtt{UP}\cap\mathtt{coUP}$ [Jur98].

We mainly consider parity games in this paper. They are played on a directed graph that is partitioned into two node sets associated with the two players; the nodes are labeled with natural numbers, called priorities. A play in a parity game is an infinite sequence of nodes whose winner is determined by the parity of the highest priority that occurs infinitely often, giving parity games their name.

The reason why parity games seem to be the most appropriate class of games, when trying to construct a worst-case family for one of the four classes, is that the effect of each node in a parity game is very clear: a higher priority dominates all lower priorities (in a play), no matter how many there are. By showing that the strategy iteration on our family of parity games directly corresponds to the strategy iteration that solves the other classes of games, we get the lower bounds for these by applying the standard reductions to our games.

Parity games occur in several fields of theoretical computer science, e.g. as solution to the problem of emptiness of tree automata [GTW02, EJ91] or as algorithmic backend to the model checking problem of the modal $\mu$-calculus [EJS93, Sti95].

There are many algorithms that solve parity games, such as the recursive decomposing algorithm due to Zielonka [Zie98] and its recent improvement by Jurdziński, Paterson and Zwick [JPZ06], the small progress measures algorithm due to Jurdziński [Jur00] with its recent improvement by Schewe [Sch07], the model-checking algorithm due to Stevens and Stirling [SS98] and finally the two strategy improvement algorithms by Vöge and Jurdziński [VJ00] and Schewe [Sch08].

All mentioned algorithms except for the two deterministic subexponential algorithms [JPZ06, Sch07] and except for the two strategy improvement algorithms have been shown to have a superpolynomial or exponential worst-case runtime complexity at best [Jur00, Fri10b, Fri10a]. The currently best known upper bound on the deterministic solution of parity games is $\mathcal{O}({|E|\cdot|V|^{\frac{1}{3}|\mathtt{ran}\Omega|}})$ due to Schewe’s big-step algorithm [Sch07].

The strategy improvement, strategy iteration or policy iteration technique is the most general approach that can be applied as a solving procedure for all of these game classes. It was introduced by Howard [How60] for solving problems on Markov decision processes and has been adapted by several other authors for solving nonterminating stochastic games [HK66], simple stochastic games [Con92], discounted and mean payoff games [Pur95, ZP96] as well as parity games [VJ00].

Strategy iteration is an algorithmic scheme that is parameterized by an improvement policy which basically defines how to select a successor strategy in the iteration process. There are two major kinds of improvement policies: deterministic and randomized approaches; we will investigate deterministic approaches in this paper.

For discounted payoff games, there is the deterministic algorithm due to Puri [Pur95] that can also be used to solve mean payoff games as well as parity games by reduction [ZP96, VJ00]. Vöge and Jurdziński’s improvement algorithm is a refined version of Puri’s on parity games that omits the use of high-precision rational numbers; there are at least two reasonable improvement policies for the Vöge-Jurdziński procedure appearing in the literature such as the standard locally optimizing policy and Schewe’s globally optimizing policy.

An example has been known for some time for which a sufficiently poor choice of a single-switch policy causes an exponential number of iterations of the strategy improvement algorithm [BV07], but there have been no games known so far on which the policies due to Vöge/Jurdziński or Schewe require more than linearly many iterations.

In this paper, we particularly investigate the locally optimizing policy – which is, by far, the most natural choice for a multi-switching improvement policy – for solving parity games as it is applied by default in the original paper of Vöge and Jurdziński. We present a family of games comprising a linear number of nodes and a quadratic number of edges such that the strategy improvement algorithm using this policy requires an exponential number of iterations on them. We explain how these games can be refined in such a way that they only comprise a linear number of edges resulting in an undeniable exponential lower bound. Additionally, we describe what parts of the games have to be altered in order to get a family that results in exponentially many iterations when solved by Schewe’s strategy improvement algorithm.

Finally, we show that the parity game strategy iteration on our games directly corresponds to the strategy iteration that solves the associated mean payoff, discounted payoff as well as simple stochastic games, resulting in an exponential lower bound for the standard strategy improvement algorithms for all of these game classes.

Section 2 defines the basic notions of parity games and some notations that are employed throughout the paper. Section 3 recaps the strategy improvement algorithm by Vöge and Jurdziński; we define the two considered improvement policies in Section 4. In Section 5, we define a subclass of parity games called sink games that allows us to relate the lower bounds for parity games to the other games classes. Section 6 presents a family of games on which the locally improving algorithm requires an exponential number of iterations. We discuss some improvements of the family in Section 7. In Section 8, we consider the modifications that have to be applied to our construction to obtain a lower bound for the globally optimizing policy. In Section 9, we show how to transfer the lower bounds to mean payoff, discounted payoff and simple stochastic games.

Parity Games

In the following we will restrict ourselves to finite parity games. W.l.o.g. we assume $\Omega$ to be injective, i.e. there are no two different nodes with the same priority.

We also use infix notation $vEw$ instead of $(v,w)\in E$ and define the set of all successors of $v$ as $vE:=\{w\mid vEw\}$. The size $|G|$ of a parity game $G=(V,\ V_{0},\ V_{1},\ E,\ \Omega)$ is defined to be the cardinality of $E$, i.e. $|G|:=|E|$; since we assume parity games to be total w.r.t. $E$, this is a reasonable way to measure the size.

The game is played between two players called and $1$: starting in a node $v_{0}\in V$, they construct an infinite path through the graph as follows. If the construction so far has yielded a finite sequence $v_{0}\ldots v_{n}$ and $v_{n}\in V_{i}$ then player $i$ selects a $w\in v_{n}E$ and the play continues with $v_{0}\ldots v_{n}w$.

We depict parity games as directed graphs where nodes owned by player 0 are drawn as circles and nodes owned by player 1 are drawn as rectangles; all nodes are labeled with their respective priority, and – if needed – with their name.

A strategy $\sigma$ for player $i$ is called positional if for all $v_{0}\ldots v_{n}\in V^{*}V_{i}$ and all $w_{0}\ldots w_{m}\in V^{*}V_{i}$ we have: if $v_{n}=w_{m}$ then $\sigma(v_{0}\ldots v_{n})=\sigma(w_{0}\ldots w_{m})$. That is, the choice of the strategy on a finite path only depends on the last node on that path.

With $G$ we associate two sets $W_{0},W_{1}\subseteq V$; $W_{i}$ is the set of all nodes $v$ s.t. player $i$ wins the game $G$ starting in $v$. Here we restrict ourselves to positional strategies because it is well-known that a player has a (general) winning strategy iff she has a positional winning strategy for a given game. In fact, parity games enjoy positional determinacy meaning that for every node $v$ in the game either $v\in W_{0}$ or $v\in W_{1}$ [EJ91]. Furthermore, it is not difficult to show that, whenever player $i$ has winning strategies $\sigma_{v}$ for all $v\in U$ for some $U\subseteq V$, then there is also a single strategy $\sigma$ that is winning for player $i$ from every node in $U$.

The problem of solving a parity game is to compute $W_{0}$ and $W_{1}$ as well as corresponding winning strategies $\sigma_{0}$ and $\sigma_{1}$ for the players on their respective winning regions.

A strategy $\sigma$ for player $i$ induces a strategy subgame $G|_{\sigma}:=(V,V_{0},V_{1},E|_{\sigma},\Omega)$ where $E|_{\sigma}:=\{(u,v)\in E\mid u\in dom(\sigma)\Rightarrow\sigma(u)=v\}$. Such a subgame $G|_{\sigma}$ is basically the same game as $G$ with the restriction that whenever $\sigma$ provides a strategy decision for a node $u\in V_{i}$, all transitions from $u$ but $\sigma(u)$ are no longer accessible. The set of strategies for player $i$ is denoted by $\mathcal{S}_{i}({G})$.

Strategy Improvement

We briefly recap the basic definitions of the strategy improvement algorithm. For a given parity game $G=(V,\ V_{0},\ V_{1},\ E,\ \Omega)$, the reward of node $v$ is defined as follows: $\mathtt{rew}_{G}(v):=\Omega(v)$ if $\Omega(v)\equiv_{2}0$ and $\mathtt{rew}_{G}(v):=-\Omega(v)$ otherwise. The set of even resp. odd priority nodes is defined to be $V_{\oplus}:=\{v\in V\mid\Omega(v)\equiv_{2}0\}$ resp. $V_{\ominus}:=\{v\in V\mid\Omega(v)\equiv_{2}1\}$.

The relevance ordering $<$ on $V$ is induced by $\Omega$: $v<u:\iff\Omega(v)<\Omega(u)$; additionally one defines the reward ordering $\prec$ on $V$ by $v\prec u:\iff\mathtt{rew}_{G}(v)<\mathtt{rew}_{G}(u)$. Note that both orderings are total due to injectivity of the priority function.

Let $\pi$ be a path $\sigma$ be a strategy for player $i$. We say that $\pi$ conforms to $\sigma$ iff for every $j$ with $\pi(j)\in V_{i}$ we have $\sigma(\pi(j))=\pi(j+1)$.

Let $v$ be a node, $\sigma$ be a positional player 0 strategy and $\tau$ be a positional player 1 strategy. Starting in $v$, there is exactly one path $\pi_{\sigma,\tau,v}$ that conforms to $\sigma$ and $\tau$. Since $\sigma$ and $\tau$ are positional strategies, this path can be uniquely written as follows.

with $v_{1}=v$, $v_{i}\not=w_{1}$ for all $1\leq i\leq k$ and $\Omega(w_{1})>\Omega(w_{j})$ for all $1<j\leq l$. Note that the uniqueness follows from the fact that all nodes on the cycle have different priorities and we choose $w_{1}$ to be the node with highest priority.

Discrete strategy improvement relies on a more abstract description of such a play $\pi_{\sigma,\tau,v}$. In fact, we only consider the dominating cycle node $w_{1}$, the set of more relevant nodes – i.e. all $v_{i}>w_{1}$ – on the path to the cycle node, and the length $k$ of the path leading to the cycle node. More formally, the node valuation of $v$ w.r.t. $\sigma$ and $\tau$ is defined as follows.

Given a node valuation $\vartheta$, we refer to $w_{1}$ as the cycle component, to $\{v_{i}>w_{1}\mid 1\leq i\leq k\}$ as the path component, and to $k$ as the length component of $\vartheta$.

In order to compare node valuations with each other, we introduce a total ordering on the set of node valuations. For that reason, we need to define a total ordering $\prec$ on the second component of node valuations – i.e. on subsets of $V$ – first. To compare two different sets $M$ and $N$ of nodes, we order all nodes lexicographically w.r.t. to their relevance and consider the first position in which the two lexicographically ordered sets differ, i.e. there is a node $v\in M$ and a node $w\in N$ with $v\not=w$ s.t. $u\in M$ iff $u\in N$ for all $u>v$ and all $u>w$. Now $N$ is better than $M$ iff $v\prec w$, i.e. the set which gives the higher reward in the first differing position is superior to the other set.

In other words, to determine which set of nodes is better w.r.t. $\prec$, one considers the node with the highest priority that occurs in only one of the two sets. The set owning that node is greater than the other if and only if that node has an even priority. More formally:

where $M\triangle N$ denotes the symmetric difference of both sets.

Now we are able to extend the total ordering on sets of nodes to node valuations The motivation behind this ordering is a lexicographic measurement of the profitability of a positional play w.r.t. player 0: the most prominent part of a positional play is the cycle in which the plays eventually stays, and here it is the reward ordering on the dominating cycle node that defines the profitability for player 0. The second important part is the loopless path that leads to the dominating cycle node. Here, we measure the profitability of a loopless path by a lexicographic ordering on the relevancy of the nodes on path, applying the reward ordering on each component in the lexicographic ordering. Finally, we consider the length, and the intuition behind the definition is that, assuming we have an even-priority dominating cycle node, it is better to reach the cycle fast whereas it is better to stay as long as possible out of the cycle otherwise. More formally:

Given a player 0 strategy $\sigma$, it is our goal to find a best response counterstrategy $\tau$ that minimizes the associated node valuations. A strategy $\tau$ is an optimal counterstrategy w.r.t. $\sigma$ iff for every opponent strategy $\tau^{\prime}$ and for every node $v$ we have: $\vartheta_{\sigma,\tau,v}\preceq\vartheta_{\sigma,\tau^{\prime},v}$.

It is well-known that an optimal counterstrategy always exists and that it is efficiently computable.

Let $G$ be a parity game and $\sigma$ be a player 0 strategy. An optimal counterstrategy for player 1 w.r.t. $\sigma$ exists and can be computed in polynomial time.

A fixed but arbitrary optimal counterstrategy will be denoted by $\tau_{\sigma}$ from now on. The associated game valuation $\Xi_{\sigma}$ is a map that assigns to each node the node valuation w.r.t. $\sigma$ and $\tau_{\sigma}$:

Game valuations are used to measure the performance of a strategy of player 0: for a fixed strategy $\sigma$ of player 0 and a node $v$, the associated valuation essentially states which is the worst cycle that can be reached from $v$ conforming to $\sigma$ as well as the worst loopless path leading to that cycle (also conforming to $\sigma$).

We also write $v\prec_{\sigma}u$ to compare the $\Xi_{\sigma}$-valuations of two nodes, i.e. to abbreviate $\Xi_{\sigma}(v)\prec\Xi_{\sigma}(u)$.

A run of the strategy improvement algorithm can be expressed by a sequence of improving game valuations; a partial ordering on game valuations is quite naturally defined as follows:

A valuation $\Xi_{\sigma}$ can be used to create a new strategy of player 0. The strategy improvement algorithm is only allowed to select new strategy decisions for player 0 occurring in the improvement arena $\mathcal{A}_{G,\sigma}:=(V,\ V_{0},\ V_{1},\ E^{\prime},\ \Omega)$ where

Thus all edges performing worse than the current strategy are removed from the game. A strategy $\sigma$ is improvable iff there is a node $v\in V_{0}$, a node $u\in V$ with $vEu$ s.t. $\sigma(v)\prec_{\sigma}u$.

An improvement policy now selects a strategy for player 0 in a given improvement arena. More formally: an improvement policy is a map $\mathcal{I}_{G}:\mathcal{S}_{0}({G})\rightarrow\mathcal{S}_{0}({G})$ fulfilling the following two conditions for every strategy $\sigma$.

For every node $v\in V_{0}$ it holds that $(v,\mathcal{I}_{G}(\sigma)(v))$ is an edge in $\mathcal{A}_{G,\sigma}$.

If $\sigma$ is improvable then there is a node $v\in V_{0}$ s.t. $\sigma(v)\prec_{\sigma}\mathcal{I}_{G}(\sigma)(v)$.

We say that an edge $(v,u)$ is an improving edge w.r.t. $\sigma$ iff $v\in V_{0}$, $u\in vE$, $\sigma(v)\not=u$ and $\sigma(v)\prec_{\sigma}u$.

Jurdziński and Vöge proved in their work that every strategy that is improved by an improvement policy can only result in strategies with valuations strictly better than the valuation of the original strategy.

Let $G$ be a parity game, $\sigma$ be an improvable strategy and $\mathcal{I}_{G}$ be an improvement policy. We have $\Xi_{\sigma}\lhd\Xi_{\mathcal{I}_{G}(\sigma)}$.

If a strategy is not improvable, the strategy iteration procedure comes to an end and the winning sets for both players as well as associated winning strategies can be easily derived from the given valuation.

Let $G$ be a parity game and $\sigma$ be a non-improvable strategy. Then the following holds:

$W_{0}=\{v\mid\Xi_{\sigma}(v)=(w,\_,\_)\textrm{ and }w\in V_{\oplus}\}$

$W_{1}=\{v\mid\Xi_{\sigma}(v)=(w,\_,\_)\textrm{ and }w\in V_{\ominus}\}$

$\sigma$ is a winning strategy for player 0 on $W_{0}$

$\tau_{\sigma}$ is a winning strategy for player 1 on $W_{1}$

The strategy iteration starts with an initial strategy $\iota_{G}$ and runs for a given improvement policy $\mathcal{I}_{G}$ as outlined in the pseudo-code of Algorithm 1.

Improvement Policies

There are two major deterministic improvement policies that we consider here, namely the locally optimizing policy due to Jurdziński and Vöge [VJ00] and the globally optimizing policy by Schewe [Sch08].

The locally optimizing policy $\mathcal{I}^{\mathtt{loc}}_{G}$ selects a most profitable strategy decision in every point with respect to the current valuation. More formally, it holds for every strategy $\sigma$, every player 0 node $v$ and every $w\in vE$ that $w\preceq_{\sigma}\mathcal{I}^{\mathtt{loc}}_{G}(\sigma)(v)$.

The locally optimizing policy can be computed in polynomial time.

This policy is generally considered to be the most natural choice, particularly because it directly corresponds to the canonical versions of strategy iteration in related parts of game theory like discounted payoff games or simple stochastic games. We will present a family of games on which the algorithm parameterized with this policy requires exponentially many iterations.

The globally optimizing policy $\mathcal{I}^{\mathtt{glo}}_{G}$ on the other hand computes a globally optimal successor strategy in the sense that the associated valuation is the best under all allowed successor strategies. More formally, given a parity game $G$, an improvable strategy $\sigma$ and the improved strategy $\sigma^{*}=\mathcal{I}^{\mathtt{glo}}_{G}(\sigma)$, we have for an arbitrary strategy $\sigma^{\prime}$ in the arena $\mathcal{A}_{G,\sigma}$ that $\Xi_{\sigma^{\prime}}\unlhd\Xi_{\sigma^{*}}$.

The policy can be interpreted as providing strategy improvement with a one-step lookahead; it computes the optimal strategy under all possible strategies that can be reached by a single improvement step.

The interested reader is pointed to Schewe’s paper [Sch08] for all the details on how to effectively compute the optimal strategy update.

The globally optimizing policy can be computed in polynomial time.

We will also explain how to adapt the presented family of games in order to enforce exponentially many strategy iterations on them when parameterized with the globally optimal policy.

Vöge mentions without proof in his thesis that there is an improvement policy that requires at most $|V|$ many iterations to find its fixed point. We find this fact to be quite remarkable and give a short proof of it in the following.

Let $G$ be a parity game. There is an improvement policy $\mathcal{I}^{\mathtt{lin}}_{G}$ s.t. the strategy improvement algorithm requires at most $|V|$ many iterations.

Let $G=(V,V_{0},V_{1},E,\Omega)$ be a parity game and let $\sigma^{*}$ be a $\unlhd$-optimal strategy. We define the improvement policy $\mathcal{I}^{\mathtt{lin}}_{G}$ as follows.

We will show that $\mathcal{I}^{\mathtt{lin}}_{G}$ is indeed an improvement policy and that the strategy iteration parameterized with $\mathcal{I}^{\mathtt{lin}}_{G}$ requires at most $|V_{0}|$ iterations on $G$ in one go by verifying that

for all $\sigma$ where $m(\sigma)=\{v\in V_{0}\mid\sigma(v)=\sigma^{*}(v)\}$.

Let $\sigma$ be a strategy s.t. $m(\sigma)\subsetneq V_{0}$. Since $m(\sigma)\subseteq m(\mathcal{I}^{\mathtt{lin}}_{G}(\sigma))$ holds by definition, we simply need to show that there is at least one node $v\in V_{0}$ with $\sigma(v)\not=\sigma^{*}(v)$ and $(v,\sigma^{*}(v))\in\mathcal{A}_{G,\sigma}$. Consider the game $G^{\prime}=(V,V_{0},V_{1},F,\Omega)$ where

It is easy to see that $\mathcal{A}_{G^{\prime},\sigma}\subseteq\mathcal{A}_{G,\sigma}$ and also that $\sigma^{*}$ is a $\unlhd$-optimal strategy w.r.t. $G^{\prime}$. As $\sigma$ is not optimal, there must be at least one proper improvement edge $(v,w)\in\mathcal{A}_{G^{\prime},\sigma}$. By definition of $G^{\prime}$, it follows that $\sigma(v)\not=w$ and $\sigma^{*}(v)=w$. ∎

One may be misled to combine the existence of an improvement policy $\mathcal{I}^{\mathtt{lin}}_{G}$ that enforces at most linearly many iterations with the existence of the improvement policy $\mathcal{I}^{\mathtt{glo}}_{G}$ that selects the optimal successor strategy in each iteration, in order to propose that $\mathcal{I}^{\mathtt{glo}}_{G}$ should also enforce linearly many iterations in the worst case.

The reason why this proposition is incorrect lies in the intransitivity of optimality of strategy updates. Although it is true that $\mathcal{I}^{\mathtt{lin}}_{G}(\sigma)\unlhd\mathcal{I}^{\mathtt{glo}}_{G}(\sigma)$ for every strategy $\sigma$, this is not necessarily the case for iterated applications, i.e. $\mathcal{I}^{\mathtt{lin}}_{G}(\mathcal{I}^{\mathtt{lin}}_{G}(\sigma))\unlhd\mathcal{I}^{\mathtt{glo}}_{G}(\mathcal{I}^{\mathtt{glo}}_{G}(\sigma))$ does not necessarily hold for all strategies $\sigma$.

Sink Games

Every approach trying to construct a game family of polynomial size that requires super-polynomially many iterations to be solved by strategy iteration (no matter which policy the algorithm is parameterized with), needs to focus on the second component of game valuations: there are only linearly many different values for the first and third component while there are exponentially many for the second.

Particularly, as there are at most linearly many different cycle nodes that can occur in valuations during a run, there is no real benefit in actually using different cycle nodes. Hence our basic layout of a game exploiting exponential behavior consists of a complex structure leading to one single loop – the only cycle node that will occur in valuations (such structures can easily be identified by preprocessing, but obviously it is not very difficult to obfuscate the whole construction without really altering its effect on the strategy iteration). In this setting, the strategy iteration algorithm is just improving the paths leading to the cycle node.

More formally: we call a parity game $G$ (in combination with an initial strategy $\iota_{G}$) a 1-sink game iff the following two properties hold:

Sink Existence: there is a node $v^{*}$ (called the 1-sink of $G$) with $v^{*}Ev^{*}$ and $\Omega(v^{*})=1$ reachable from all nodes; also, there is no other node $w$ with $\Omega(w)\leq\Omega(v^{*})$.

Sink Seeking: for each player 0 strategy $\sigma$ with $\Xi_{\iota_{G}}\unlhd\Xi_{\sigma}$ and each node $w$ it holds that the cycle component of $\Xi_{\sigma}(w)$ equals $v^{*}$.

Obviously, a 1-sink game is won by player 1. Note that comparing node valuations in a 1-sink game can be reduced to comparing the path components of the respective node valuations, for two reasons. First, the cycle component remains constant. Second, the path-length component equals the cardinality of the path component, because all nodes except the sink node are more relevant than the cycle node itself. In the case of a 1-sink game, we will therefore identify node valuations with their path component.

It is fairly easy to prove that a game is a 1-sink game indeed. One simply has to check that the sink existence property holds by looking at the graph, that the game is completely won by player 1, and that the 1-sink is the cycle component of all nodes of the initial strategy.

Let $G$ be a parity game fulfilling the sink existence property w.r.t. $v^{*}$. $G$ is a 1-sink game iff $G$ is completely won by player 1 (i.e. $W_{1}=V$) and for each node $w$ it holds that the cycle component of $\Xi_{\iota_{G}}(w)$ equals $v^{*}$.

The “only-if”-part is trivial. For the “if”-part, we need to show that the sink seeking-property holds. Let $\sigma$ be a player 0 strategy with $\Xi_{\iota_{G}}\unlhd\Xi_{\sigma}$, $w$ be an arbitrary node and $u$ be the cycle component of $\Xi_{\sigma}(w)$. Due to the fact that $G$ is completely won by player 1, $u$ has to be of odd priority. Also, since $\Xi_{\iota_{G}}\unlhd\Xi_{\sigma}$, it holds that $\Omega(u)\leq\Omega(v^{*})$ implying $u=v^{*}$ by the sink existence-property. ∎

There is another reason why 1-sink games are an interesting subclass of parity games: we will see later that the strategy iteration on a discounted payoff game that has been induced by the canonic reduction from a 1-sink parity game, directly corresponds to the strategy iteration on the original 1-sink parity game. This connection between discounted payoff games and 1-sink parity games allows us to directly transfer the lower bound to discounted payoff games.

Lower Bound for the Locally Optimizing Policy

The lower bound construction for the locally optimizing policy is a family of 1-sink parity games that implement a binary counter. In order to reduce the overall complexity of the games, our construction relies on unbounded edge outdegree, yielding a quadratic number of edges in total. We will discuss in the next section how the number of edges can be reduced to a linear number and even how to get binary outdegree.

The implementation of the binary counter is based on a structure called simple cycles that allows us to encode a single bit state in a given strategy $\sigma$. By having $n$ such simple cycles, we can represent every state of an $n$-bit binary counter. In order to allow strategy improvement the transitions of the binary counter, we need to embed the simple cycles in a more complicated structure called cycle gadget, connect the cycle gadgets of the different bits with each other, and with an additional structure called deceleration lane.

This section is organized as follows. First, we consider the three gadgets that will be used in our lower bound construction, namely simple cycles, the deceleration lane and cycle gates. Then, we present the full construction of our lower bound family and give a high-level description of strategy iteration on these games. Finally, we prove that strategy iteration on the games indeed follows the high-level description.

For the presentation of the gadgets, we assume the context of a 1-sink parity game. The labelings and priorities of the gadgets will match the final priorities of the lower bound family.

Gadgets consist of three kinds of nodes: input nodes, output nodes and internal nodes. Input nodes are nodes that will have incoming edges from outside of the gadget, output nodes will have outgoing edges to the outside of the gadget and internal nodes will not be directly connected to the outside of the gadget.

In the context of 1-sink game $G$ and a strategy $\sigma$, we will sometimes say that a node $v$ reaches a node $w$ to denote the fact that $w$ lies on the path $\pi_{\sigma,\tau_{\sigma},v}$.

The binary counter will contain a representation of $n$ bits that are realized by $n$ instances of a gadget called a cycle gate. The most important part of a cycle gate is the simple cycle that we will introduce first. We fix some index $i$ for the simple cycle gadget for the sake of this subsection in order to have consistent node labelings.

A simple cycle consists of one player 0 controlled internal node $d_{i}$ that is connected to a set of external nodes $D_{i}$ in the rest of the graph, and one player 1 controlled input node $e_{i}$. The node $e_{i}$ itself is connected to $d_{i}$ (therefore the name simple cycle) and to one output node $h_{i}\not\in D_{i}$. We note that all $e_{i}$ nodes are the only player 1 controlled nodes with real choices in the complete lower bound construction.

All priorities of the simple cycle are based on an odd priority $p_{i}$. Intuitively, the $p_{i}$ is considered to be a very small priority compared to the priorities of the other nodes in the external graph that the simple cycle is connected to. We will implicitly assume this in the following.

See Figure 1 for a simple cycle of index $1$ with $p_{1}=3$. The players, priorities and edges are described in Table 1.

Given a strategy $\sigma$, we say that the cycle is closed iff $\sigma(d_{i})=e_{i}$ and open otherwise. A closed cycle corresponds to a bit which is set while an open cycle corresponds to an unset bit.

The main idea now is to assign priorities to the simple cycle in such a way that the simple cycle is won by player 0, i.e. the most relevant node on the cycle needs to have an even priority. This has important consequences for the behaviour of the player 1 controlled node.

First, assume that $\sigma(d_{i})=e_{i}$. The optimal counter-strategy here is $\tau_{\sigma}(e_{i})=h_{i}$, since otherwise player 0 would win the cycle which is impossible with $G$ being a 1-sink game. Player 0 is therefore able to force player 1 to move out of the cycle; in other words, setting a bit corresponds to forcing player 1 out of the cycle. In a set bit, the valuation of $d_{i}$ is essentially the valuation of $h_{i}$, i.e. $\Xi_{\sigma}(d_{i})=\Xi_{\sigma}(h_{i})\cup\{d_{i},e_{i}\}$.

Second, assume that $\sigma(d_{i})=w$ for some $w\in D_{i}$, and that $w\prec_{\sigma}h_{i}$. It follows that $d_{i}\prec_{\sigma}h_{i}$, hence $\tau_{\sigma}(e_{i})=d_{i}$. The interesting part is now that $\Xi_{\sigma}(e_{i})=\Xi_{\sigma}(w)\cup\{d_{i},e_{i}\}$, i.e. $e_{i}$ is an improving node for $d_{i}$ (since $\Xi_{\sigma}(w)\triangle\Xi_{\sigma}(e_{i})=\{d_{i},e_{i}\}$), but updating to $e_{i}$ would yield a much greater reward than just $\Xi_{\sigma}(e_{i})$ (namely $\Xi_{\sigma}(h_{i})\cup\{e_{i}\}$ by forcing player 1 to leave the cycle).

Assume now that $w^{\prime}\in D_{i}$ with $w\prec_{\sigma}w^{\prime}$ but $w^{\prime}\prec_{\sigma}h_{i}$. Obviously, $w^{\prime}$ and $e_{i}$ are improving nodes for $d_{i}$, but $e_{i}\prec_{\sigma}w^{\prime}$, hence by the locally improving policy, player 0 switches to $w^{\prime}$ although $e_{i}$ might give a much better valuation. In other words, by moving to $d_{i}$, the player 1 node hides the fact that there is a highly profitable node on the other side.

We formalize the behaviour of the simple cycle in two lemmas. The first describes the valuation of $e_{i}$ depending on the state of the simple cycle and the second explains the switching behaviour of the player 0 controlled node. The claimed result can easily be obtained by tracing the paths that the strategies take through the gadget, and then comparing valuations.

Let $\sigma$ be a strategy. The following holds:

If cycle $i$ is closed, we have $\tau_{\sigma}(e_{i})=h_{i}$.

If cycle $i$ is open and $h_{i}\prec_{\sigma}\sigma(d_{i})$, we have $\tau_{\sigma}(e_{i})=h_{i}$.

If cycle $i$ is open and $\sigma(d_{i})\prec_{\sigma}h_{i}$, we have $\tau_{\sigma}(e_{i})=d_{i}$.

Let $\sigma$ be a strategy and $w=\max_{\prec_{\sigma}}D_{i}$. Let $\sigma^{\prime}=\mathcal{I}^{\mathtt{loc}}(\sigma)$. The following holds:

If cycle $i$ is closed and $w\prec_{\sigma}h_{i}$, we have cycle $i$ $\sigma^{\prime}$-closed (“closed cycle remains closed”).

If cycle $i$ is open, $\sigma(d_{i})\not=w$ or $h_{i}\prec_{\sigma}w$, we have $\sigma^{\prime}(d_{i})=w$ (“open cycle remains open”).

If cycle $i$ is open, $\sigma(d_{i})=w$ and $w\prec_{\sigma}h_{i}$, then cycle $i$ is $\sigma^{\prime}$-closed (“open cycle closes”).

If cycle $i$ is closed and $h_{i}\prec_{\sigma}w$, we have $\sigma^{\prime}(d_{i})=w$ (“closed cycle opens”).

Open simple cycles have the important property that we can postpone closing them by supplying them with new nodes $w\in D_{i}$ in each iteration s.t. $\sigma(d_{i})\prec_{\sigma}w$. We will use this property in the construction of our binary counter. Since we do not want to set all bits at the same time, rather one by one, we need to make sure that unset bits which are not supposed to be set remain unset for some time (more precisely, until the respective bit represents the least unset bit), and this will be realized by this property. The device that supplies us with new best-valued external nodes in each iteration is called deceleration lane and will be described next.

2. Deceleration Lane

A deceleration lane has several, say $m$, input nodes and some output nodes, called roots. The lower bound construction will only require a deceleration lane with two roots $s$ and $r$, however, it would be easy to generalize the construction of deceleration lanes to an arbitrary number of roots.

More formally, a deceleration lane consists of $m$ internal nodes $t_{1}$, $\ldots$, $t_{m}$, one additional internal node $c$, $m$ input nodes $a_{1}$, $\ldots$, $a_{m}$ and two output nodes $s$ and $r$, called roots of the deceleration lane.

All priorities of the deceleration lane are based on some odd priority $p$. We assume that all root nodes have a priority greater than $p+2m+1$. See Figure 2 for a deceleration lane with $m=6$ and $p=15$. The players, priorities and edges are described in Table 2.

A deceleration lane serves the following purpose. Assume that one of the output nodes, say $r$, has the better valuation compared to the other root node, and assume further that this setting sustains for some iterations.

The input nodes, say $a_{1},\ldots,a_{m}$, now serve as an entry point, and all reach the best valued root – $r$ – by some internal nodes. The valuation ordering of all input nodes depends on the iteration: at first, $a_{1}$ has a better valuation than all other input nodes. Then, $a_{2}$ has a better valuation than all other input nodes and so on.

This process continues until the other output node, say $s$, has a better valuation than $r$. Within the next iteration, the internal nodes perform a resetting step s.t. all input nodes eventually reach the new root node. One iteration after that, $a_{1}$ has the best valuation compared to all other input nodes again.

In other words, by giving one of the roots, say $s$, a better valuation than another root, say $r$, it is possible to reset and therefore reuse the lane again. In fact, the lower bound construction will use a deceleration lane with two roots $s$ and $r$, and will employ $s$ only for resetting, i.e. after some iterations with $r\succ_{\sigma}s$, there will be one iteration with $s\succ_{\sigma}r$ and right after that again $r\succ_{\sigma}s$.

From an abstract point of view, we describe the state of a deceleration lane by which of the two roots is chosen and by how many $t_{i}$ nodes are already moving down to $c$. Formally, we say that $\sigma$ is in deceleration state $(x,j)$ (where $x\in\{s,r\}$ and $0<j\leq m+1$ a natural number) iff

$\sigma(t_{i})=t_{i-1}$ for all $1<i<j$, and

We say that the deceleration lane is rooted in $x$ if $\sigma$ is in state $(x,*)$, and that the index is $i$ if $\sigma$ is in state $(*,i)$. Whenever a strategy $\sigma$ is in state $(x,i)$, we define $\mathit{root}(\sigma)=x$ and $\mathit{ind}(\sigma)=i$. In this case, we say that the strategy is well-behaved.

We formalize the behaviour of the deceleration lane in two lemmas. The first describes the ordering of the valuations of the input nodes depending on the state $(x,i)$ of the deceleration lane: (1) if the ordering of the root nodes changes, all input nodes have a worse valuation than the better root, and (2) otherwise the best valued input node is $a_{i-1}$. The second explains the switching behaviour of the player 0 controlled nodes: (1) if the ordering of the root node changes, than the whole lane resets, and (2) otherwise the lane assembles further, providing a new best-valued input node.

Let $\sigma$ be a strategy in deceleration state $(x,i)$. Let $\bar{x}$ denote the other root. Then

$x\prec_{\sigma}\bar{x}$ implies $a_{j}\prec_{\sigma}\bar{x}$ for all $j$ (“resetting results in unprofitable lane”).

$\bar{x}\prec_{\sigma}x$ implies $x\prec_{\sigma}a_{i}\prec_{\sigma}\ldots\prec_{\sigma}a_{m}\prec_{\sigma}c\prec_{\sigma}a_{1}\prec_{\sigma}\ldots\prec_{\sigma}a_{i-1}$ (“new best-valued node in each iteration”).

Let $\sigma$ be a strategy that is in deceleration state $(x,i)$. Let $\bar{x}$ denote the other root. Let $\sigma^{\prime}=\mathcal{I}^{\mathtt{loc}}(\sigma)$. Then

$x\prec_{\sigma}\bar{x}$ implies that $\sigma^{\prime}$ is in state $(\bar{x},1)$ (“lane resets”).

$\bar{x}\prec_{\sigma}x$ implies that $\sigma^{\prime}$ is in state $(x,\min(i,m)+1)$ (“lane assembles one step at a time”).

$\sigma^{\prime}$ is well-behaved (“always ending up with well-behaved strategies”).

The main purpose of a deceleration lane is to absorb the update activity of other nodes in such a way that wise (i.e. edges that will result in much better valuations after switching and reevaluating) strategy updates are postponed. Consider a node for instance that has more than one proper improving switch; the locally optimizing policy will select the edge with the best valuation to be switched. In order to prevent that one particular improving switch is applied for some iterations, one can connect the node to the input nodes of the deceleration lane.

The particular scenario in which we will use the deceleration lane are simple cycles as described in the previous subsection. We will connect the simple cycles encoding the bits of our counter to the deceleration lane in such a way, that lower cycles have less edges entering the deceleration lane. This construction ensures that lower open cycles (representing unset bits) will close (i.e. set the corresponding bit) before higher open cycles (representing higher unset bits) have their turn to close.

3. Cycle Gate

The simple cycles will appear in a more complicated gadget, called cycle gate. We will have $n$ different cycle gates in the game number $n$ of the lower bound family, hence we fix some index $i$ for the cycle gate gadget for the sake of this subsection in order to have consistent node labelings.

Formally, a cycle gate consists of two internal nodes $e_{i}$ and $h_{i}$, two input nodes $f_{i}$ and $g_{i}$, and two output nodes $d_{i}$ and $k_{i}$. The output node $d_{i}$ will be connected to a set of other nodes $D_{i}$ in the game graph, and $k_{i}$ to some other set $K_{i}$ as well. The two nodes $d_{i}$ and $e_{i}$ form a simple cycle as described earlier.

All priorities of the cycle gate are based on two odd priorities $p_{i}$ and $p_{i}^{\prime}$. See Figure 3 for a cycle gate of index $1$ with $p_{1}^{\prime}=3$ and $p_{1}=33$. The players, priorities and edges are described in Table 3.

The main idea behind a cycle gate is to have a pass-through structure controlled by the simple cycle that is either very profitable or quite unprofitable. The pass-through structure of the cycle gate has one major input node, named $g_{i}$, and one major output node, named $k_{i}$. The input node is controlled by player 0 and connected via two paths with the output node; there is a direct edge and a longer path leading through the interior of the cycle gate.

However, the longer path only leads to the output node if the simple cycle, consisting of one player 0 node $d_{i}$ and one player 1 node $e_{i}$, is closed. In this case, it is possible and profitable to reach the output node via the internal path; otherwise, this path is not accessible, and hence, the input node has to select the unprofitable direct way to reach the output node.

We will have one additional input node, named $f_{i}$, that can only access the path leading through the interior of the cycle gate, for the following purpose. Assume that the simple cycle has just been closed and now the path leading through the interior becomes highly profitable. Hence, the next switching event to happen will be the node $g_{i}$ switching from the direct path to the path through the interior. However, it will be useful to be able to reach the highly profitable path from some parts of the outside graph one iteration before it is accessible via $g_{i}$. For this reason, we include an additional input node $f_{i}$ that immediately accesses the interior path.

We say that a cycle gate is closed resp. open iff the interior simple cycle is closed resp. open. Similarly, we say that a cycle gate is accessed resp. skipped iff the access control node $g_{i}$ moves through the interior ($\sigma(g_{i})=f_{i}$) resp. directly to $k_{i}$.

From an abstract point of view, we describe the state of a cycle gate by a pair $(\beta_{i}(\sigma),\alpha_{i}(\sigma))\in\{0,1\}^{2}$. The first component describes the state of the simple cycle, and the second component gives the state of the access control node. Formally, we have the following.

$\beta_{i}(\sigma)=1$ iff the $i$-th cycle gate is closed, and

$\alpha_{i}(\sigma)=1$ iff the $i$-th cycle gate is accessed.

We formalize the behaviour of the cycle gate in two lemmas. The first describes the valuation of all important nodes of the cycle gate, using our knowledge of simple cycles of Lemma 6.1. The second explains the switching behaviour of the access control node. The behaviour of the simple cycle contained in the cycle gate is described by Lemma 6.2.

If gate $i$ is open, we have $f_{i}\prec_{\sigma}\sigma(d_{i})$.

If gate $i$ is closed, we have $\sigma(k_{i})\prec_{\sigma}f_{i}$.

If gate $i$ is closed and skipped, we have $g_{i}\prec_{\sigma}f_{i}$.

If gate $i$ is accessed, we have $f_{i}\prec_{\sigma}g_{i}$.

If gate $i$ is skipped, we have $\sigma(k_{i})\prec_{\sigma}g_{i}$.

Let $\sigma$ be a strategy and $\sigma^{\prime}=\mathcal{I}^{\mathtt{loc}}(\sigma)$.

If gate $i$ is $\sigma$-closed, then gate $i$ is $\sigma^{\prime}$-accessed (“closed gates will be accessed”).

If gate $i$ is $\sigma$-open and $\sigma(d_{i})\prec_{\sigma}h_{i}$, then gate $i$ is $\sigma^{\prime}$-skipped (“open gates with unprofitable exit nodes will be skipped”).

If gate $i$ is $\sigma$-open and $h_{i}\prec_{\sigma}\sigma(d_{i})$, then gate $i$ is $\sigma^{\prime}$-accessed (“open gates with profitable exit nodes will be accessed”).

The last two items of Lemma 6.6 are based on the uniqueness of priorities in the game, implying that there are no priorities between $f_{i}$ and $h_{i}$.

We will use cycle gates to represent the bit states of a binary counter: unset bits will correspond to cycle gates with the state $(0,0)$, set bits to the state $(1,1)$. Setting and resetting bits therefore traverses more than one phase, more precisely, from $(0,0)$ over $(1,0)$ to $(1,1)$, and from the latter again over $(0,1)$ to $(0,0)$. Particularly, it can be observed that the second component of the cycle gate states switches one iteration after the first component in both cases.

4. Lower Bound Construction

In this subsection, we provide the complete construction of the lower bound family. It essentially consists of a 1-sink $x$, a deceleration lane of length $2n$ that is connected to the two roots $s$ and $r$, and $n$ cycle gates. The simple cycles of the cycle gates are connected to the roots and to the deceleration lane with the important detail, that lower cycle gates have less edges to the deceleration lane. This construction ensures that lower open cycle gates will close before higher open cycle gates.

The output node of a cycle gate is connected to the 1-sink and to the $g_{*}$-input nodes of all higher cycle gates. The $s$ root node is connected to all $f_{*}$-input nodes, the $r$ root node is connected to all $g_{*}$-input nodes.

We now give the formal construction. The games are denoted by $G_{n}=(V_{n},V_{n,0},V_{n,1},E_{n},\Omega_{n})$. The sets of nodes are

The players, priorities and edges are described in Table 4. The game $G_{3}$ is depicted in Figure 4.

The game $G_{n}$ has $10\cdot n+4$ nodes, $1.5\cdot n^{2}+20.5\cdot n+5$ edges and $12\cdot n+8$ as highest priority. In particular, $|G_{n}|=\mathcal{O}({n^{2}})$.

As an initial strategy we select the following $\iota_{G_{n}}$. It will correspond to the global counter state in which no bit has been set.

Note that $\iota_{G_{n}}$ particularly is well-behaved. Hence, by Lemma 6.4(3) we know that all strategies that will occur in a run of the strategy improvement algorithm will be well-behaved.

We will see in the next section, how the family $G_{n}$ can be refined in such a way that it only comprises a linear number of edges. The reason why we present the games with a quadratic number of edges first is that the refined family looks even more confusing and obfuscates the general principle.

The game $G_{n}$ is completely won by player 1.

$x$ is the 1-sink of $G_{n}$ and the cycle component of $\Xi_{\iota_{G_{n}}}(w)$ equals $x$ for all $w$.

Note that the only nodes owned by player 1 with an outdegree greater than 1 are $e_{1}$,$\ldots$,$e_{n}$. Consider the player 1 strategy $\tau$ which selects to move to $h_{i}$ from $e_{i}$ for all $i$. Now it is the case that $G_{n}|_{\tau}$ contains exactly one cycle that is eventually reached no matter what player 0 does, namely the self-cycle at $x$ which is won by player 1.

The self-cycle at $x$ obviously is the $1$-sink since it can be reached from all other nodes and has the smallest priority $1$. Since $xEx$ is the only cycle won by player 1 in $G_{n}|_{\iota_{G_{n}}}$, $x$ must be the cycle component of each node valuation w.r.t. $\iota_{G_{n}}$.∎

By Lemma 5.1 it follows that $G_{n}$ is a 1-sink game, hence it is safe to identify the valuation of a node with its path component from now on.

5. Lower Bound Description and Phases

Here, we describe how the binary counter performs the task of counting by strategy improvement. Our games implement a full binary counter in which every bit is represented by a simple cycle encapsulated in a cycle gate. An unset bit $i$ corresponds to an open simple cycle in cycle gate $i$, a set bit $i$ corresponds to a closed simple cycle in cycle gate $i$.

Formally, we represent the bit state of the counter by elements from $B_{n}=\{0,1\}^{n}$. For $b=(b_{n},\ldots,b_{1})\in B_{n}$, let $b_{i}$ denote the $i$-th component in $b$ for every $i\leq n$, where $b_{n}$ denotes the most and $b_{1}$ denotes the least significant bit. By $b\oplus 1$, we denote the increment of the number represented by $b$ by $1$. The least resp. greatest bit states are denoted by $\mathbf{0}_{n}$ resp. $\mathbf{1}_{n}$. We refer to the least unset bit by $\mu b:=\min(\{n+1\}\cup\{i\leq n\mid b_{i}=0\})$, and similarly to the least set bit by $\nu b:=\min(\{n+1\}\cup\{i\leq n\mid b_{i}=1\})$.

From the most abstract point of view, our lower bound construction performs counting on $B_{n}$. However, the increment of a global bit state requires more than one strategy iteration, more precisely four different phases that will be described next (with one phase of dynamic length).

Every phase is defined w.r.t. a given global counter state $b\in B_{n}$. Let $b\in B_{n}$ be a global bit state different from $\mathbf{1}_{n}$.

An abstract counter performs the increment from $b$ to $b\oplus 1$ by computing $b[\mu b\mapsto 1][j{<}\mu b\mapsto 0]$, i.e. by setting bit $\mu b$ and by resetting all lower bits $j{<}\mu b$. In the context of the games, we start in phase 1 corresponding to $b$, and then proceed to phase 2 and phase 3 corresponding to $b[\mu b\mapsto 1]$, from phase 3 to phase 4 corresponding to $b[\mu b\mapsto 1][j<\mu b\mapsto 0]$, and finally from phase 4 to phase 1 again. The transition from phase 2 to phase 3 and from phase 4 to phase 1 handles the correction of the internal structure connecting the cycles with each other.

For the sake of this subsection, let $\sigma$ be a strategy and $b\in B_{n}$ be a global counter state. All phases will be defined w.r.t. $\sigma$ and $b\in B_{n}$. Let $\sigma^{\prime}=\mathcal{I}^{\mathtt{loc}}(\sigma)$.

To keep everything as simple as possible and to be able to prove all the lemmas without considering special cases, we will assume that $b$ is different from $\mathbf{0}_{n}$ and that the two highest bits in $b$ are zero and remain zero, i.e. we will only use the first $n-2$ bits for counting. Note however, that every bit works as intended in the counter.

Given a strategy $\sigma$, we denote the associated simple cycle state $(\beta_{n}(\sigma),\ldots,\beta_{1}(\sigma))$ by $b_{\sigma}$, and the associated access state $(\alpha_{n}(\sigma),\ldots,\alpha_{1}(\sigma))$ by $a_{\sigma}$.

Recall that every strategy $\sigma$ occurring will be well-behaved. In addition to the deceleration lane and the cycle gates, we have two more structures that are controlled by a strategy $\sigma$, namely the two roots $r$ and $s$, and the cycle gate output nodes $k_{i}$. We write $\sigma(r)=i$ to denote that $\sigma(r)=g_{i}$, and $\sigma(r)=n+1$ if $\sigma(r)=x$; we write $\sigma(s)=i$ to denote that $\sigma(s)=f_{i}$, and $\sigma(s)=n+1$ if $\sigma(s)=x$; we write $\sigma(k_{i})=j$ to denote that $\sigma(k_{i})=g_{j}$, and $\sigma(k_{i})=n+1$ if $\sigma(k_{i})=x$. We also use a more compact notation for the strategy decision of $d_{i}$-nodes of open cycles. We write $\sigma(d_{i})=j$ if $\sigma(d_{i})=a_{j}$.

Recall that we say that a strategy $\sigma$ is rooted in $s$ or $r$, if every path in the deceleration lane conforming to $\sigma$ eventually exits to $s$ resp. $r$. Likewise, we say that $\sigma$ has index $i$ if all nodes of the deceleration lane with smaller index $j<i$ are moving down the lane by $\sigma$, and that $i$ is the first index which is directly exiting through the root.

The first phase, called the waiting phase, corresponds to a stable strategy $\sigma$ in which open cycles are busy waiting to be closed while the deceleration lane is assembling. Cycle gates that correspond to set bits are closed and accessed, while cycle gates of unset bits are open and skipped, i.e. $b=b_{\sigma}=a_{\sigma}$. The selector nodes $k_{i}$ move to the next higher cycle gate corresponding to a set bit, and both roots are connected to the least set bit $\nu b$.

More formally, we say that $\sigma$ is a $b$-phase 1 strategy iff all the following conditions hold:

$b=b_{\sigma}=a_{\sigma}$, i.e. set bits correspond to closed and accessed cycle gates, while unset bits correspond to open and skipped cycle gates,

$\mathit{root}(\sigma)=r$, i.e. the strategy is rooted in $r$,

$\sigma(s)=\sigma(r)=\nu b$, i.e. both roots are connected to the least set bit,

$\sigma(k_{i})=\min(\{j>i\mid b_{j}=1\}\cup\{n+1\})$, i.e. the selector nodes move to the next set bit,

$\mathit{ind}(\sigma)\leq 2\mu b+2$, i.e. the deceleration lane has not passed the least unset bit, and

$\sigma(d_{j})\not=\mathit{ind}(\sigma)-1$ for all $j$ with $b_{j}=0$, i.e. every open cycle node is not connected to the best-valued node of the lane.

The only improving switches in the first phase are edges of open simple cycles and edges of the deceleration lane.

Let $\sigma$ be a $b$-phase 1 strategy with $\mathit{ind}(\sigma)<2\mu b+2$. Then $\sigma^{\prime}$ is a $b$-phase 1 strategy with $\mathit{ind}(\sigma^{\prime})=\mathit{ind}(\sigma)+1$, and if $\mathit{ind}(\sigma)>1$, then $\sigma^{\prime}(d_{\mu b})=\mathit{ind}(\sigma)-1$.

Let $\sigma$ be a $b$-phase 1 strategy, $\Xi:=\Xi_{\sigma}$ and $\mathit{ind}(\sigma)<2\mu b+2$.

We first compute the valuations for all those nodes directly that do not involve any complicated strategy decision of player 1. Obviously, $\Xi(x)=\emptyset$. By Lemma 6.1(1) we know that for all set bits $i$ (i.e. $b_{i}=1$) we have the following.

Using these equations, we are able to compute many other valuations that do not involve any complicated strategy decision of player 1. Let $U_{j}=\{g_{j},f_{j},e_{j},h_{j},k_{j}\}$. The following holds (by $\mathtt{CF}_{p}(A)$ we denote the function that returns $A$ if $p$ holds and $\emptyset$ otherwise):

It is easy to see that we have the following orderings on the nodes specified above.

By Lemma 6.1(2), it follows from (a) that $\tau_{\sigma}(e_{i})=d_{i}$ for all unset bits $i$ (i.e. $b_{i}=0$), hence we are able to compute the valuations of the remaining nodes.

This completes the valuation of $\Xi$ for all nodes.

It is easy to see that for every $i$ with $b_{i}=0$ and every $j$ with $b_{j}=1$ s.t. there is no $i<i^{\prime}<j$ with $b_{i^{\prime}}=1$, the following holds:

Also, for $i>j$ with $b_{i}=1$ and $b_{j}=1$ we have

By (a) and Lemma 6.3(2) we obtain that the following holds:

We are now ready to prove that $\sigma^{\prime}$ is of the desired form.

By Lemma 6.2(1) and (a) we derive that closed cycles remain closed. By Lemma 6.6(1) we derive that closed cycles remain accessed. By (a) and Lemma 6.6(2) we derive that open cycles remain skipped.

By phase 1 condition (5), phase 1 condition (6), (d), it follows that for every $j$ with $b_{j}=0$, there is an improving node $a_{*}$ for $d_{j}$. By Lemma 6.2(2), we conclude that open cycles remain open.

By Lemma 6.4(2) it follows that $\mathit{ind}(\sigma^{\prime})=\mathit{ind}(\sigma)+1$.

If $\mathit{ind}(\sigma)>1$, then we have by (a) and (d) that $\sigma^{\prime}(d_{\mu b})=\mathit{ind}(\sigma)-1)$.

The first phase ends, when a simple cycle corresponding to an unset bit has no more edges leading to the deceleration lane that keeps it busy waiting, and closes. Since lower bits have less edges going to the lane, it is clear that this will be the least unset bit $\mu b$.

The second phase, called the set phase, corresponds to a strategy $\sigma$ in which the least unset bit has just been set, i.e. to the global state $b[\mu b\mapsto 1]=b_{\sigma}$. The selector nodes and roots are as in phase 1 and also the access states, i.e. $b=a_{\sigma}$.

More formally, we say that $\sigma$ is a $b$-phase 2 strategy iff all the following conditions hold:

$b[\mu b\mapsto 1]=b_{\sigma}$ and $b=a_{\sigma}$, i.e. set bits correspond to closed and accessed (for all set bits except for $\mu b$) cycle gates, while unset bits correspond to open and skipped cycle gates,

$\mathit{root}(\sigma)=r$, i.e. the strategy is rooted in $r$,

$\sigma(s)=\sigma(r)=\nu b$, i.e. both roots are connected to the former least set bit,

$\sigma(k_{i})=\min(\{j>i\mid b_{j}=1\}\cup\{n+1\})$, i.e. the selector nodes move to the next set bit,

$\mathit{ind}(\sigma)\leq 2\mu b+3$, i.e. the deceleration lane has not passed the next bit, and

$\sigma(d_{j})\not=\mathit{ind}(\sigma)-1$ for all $j>\mu b$ with $b_{j}=0$, i.e. every higher open cycle node is not connected to the best-valued node of the lane.

Let $\sigma$ be a $b$-phase 1 strategy with $\mathit{ind}(\sigma)=2\mu b+2$ and $\sigma(d_{\mu b})=\mathit{ind}(\sigma)$. Then $\sigma^{\prime}$ is a $b$-phase 2 strategy.

This can be shown essentially the same way as Lemma 6.9. The only difference now is that $d_{\mu b}$ has no more improving switches to the deceleration lane and hence, by Lemma 6.2(3), we learn that the $\mu b$-cycle has to close.

In phase 2, the deceleration lane is still assembling, and the improving switches again include edges of open simple cycles and edges of the deceleration lane. Additionally, it is improving for the cycle gate $\mu b$ to be accessed and for the root $s$ to update to cycle gate $\mu b$. By performing all these switches, we enter phase three.

The third phase, called the access phase, is defined by a renewed correspondence of the cycle gate structure again, i.e. $b[\mu b\mapsto 1]=b_{\sigma}=a_{\sigma}$. The $s$ root is connected to $\mu b$ while $r$ is still connected to $\nu b$. This implies that $s$ now has a much better valuation than $r$.