Université Paris-Saclay, CNRS, ENS Paris-Saclay, LMF, 91190, Gif-sur-Yvette,
<EMAIL_ADDRESS>Paris-Saclay, CNRS, ENS Paris-Saclay, LMF,
91190, Gif-sur-Yvette<EMAIL_ADDRESS>Université Paris-Saclay, CNRS, ENS
Paris-Saclay, LMF, 91190, Gif-sur-Yvette<EMAIL_ADDRESS>John Q. Public
and Joan R. Public [500]Theory of computation Verification by model checking
John Q. Open and Joan R. Access 2 Computer Science Logic 2022 CSL’22 CSL 2022
February 14–19, 2022 Göttingen, Germany 42 80

# Finite-memory strategies in two-player infinite games

Patricia Bouyer  Stéphane Le Roux  Nathan Thomasset

###### Abstract

We study infinite two-player win/lose games $(A,B,W)$ where $A,B$ are finite
and $W\subseteq(A\times B)^{\omega}$. At each round Player 1 and Player 2
concurrently choose one action in $A$ and $B$, respectively. Player 1 wins iff
the generated sequence is in $W$. Each history $h\in(A\times B)^{*}$ induces a
game $(A,B,W_{h})$ with $W_{h}:=\\{\rho\in(A\times B)^{\omega}\mid h\rho\in
W\\}$. We show the following: if $W$ is in $\Delta^{0}_{2}$ (for the usual
topology), if the inclusion relation induces a well partial order on the
$W_{h}$’s, and if Player 1 has a winning strategy, then she has a finite-
memory winning strategy. Our proof relies on inductive descriptions of set
complexity, such as the Hausdorff difference hierarchy of the open sets.

Examples in $\Sigma^{0}_{2}$ and $\Pi^{0}_{2}$ show some tightness of our
result. Our result can be translated to games on finite graphs: e.g. finite-
memory determinacy of multi-energy games is a direct corollary, whereas it
does not follow from recent general results on finite memory strategies.

###### keywords:

Two-player win/lose games, Infinite trees, Finite-memory winning strategies,
Well partial orders, Hausdorff difference hierarchy

###### category:

##  1 Introduction

Two-player win/lose games have been a useful tool in various areas of logic
and computer science. The two-player win/lose games in this article consist of
infinitely many rounds. At each round $i$, Player 1 and Player 2 concurrently
choose one _action_ each, i.e. $a_{i}$ and $b_{i}$ in there respective sets
$A$ and $B$. Player 1 wins and Player 2 loses if the play
$(a_{0},b_{0})(a_{1},b_{1})\dots$ belongs to a fixed $W\subseteq(A\times
B)^{\omega}$. Otherwise Player 2 wins and Player 1 loses. We call $W$ the
_winning set_ of Player 1, or the winning condition for Player 1. A _strategy_
is a map that tells a player how to play after any finite _history_ of actions
played: a Player 1 (resp. 2) strategy is a map from $(A\times B)^{*}$ to $A$
(resp. $B$). A strategy is _finite-memory_ (FM) if the map can be implemented
by a finite-state machine. Also, each history $h\in(A\times B)^{*}$ induces a
game starting at $h$ and taking the past into account, i.e. with winning set
$W_{h}:=\\{\rho\in(A\times B)^{\omega}\mid h\rho\in W\\}$.

For now we state a slightly weaker version of our main result: if $A$ and $B$
are finite, if the $(W_{h})_{h\in(A\times B)^{*}}$ constitute a well partial
order (wpo) for the inclusion, if $W\in\Delta^{0}_{2}$, i.e. in the usual
cylinder topology $W$ is a countable union of closed sets and a countable
intersection of open sets, and if Player 1 has a winning strategy, then she
has a finite-memory winning strategy. Of course, our result also applies to
the turn-based version of such games.

On the proof of the main result: The proof of our main result relies on
descriptive set theory. The Hausdorff-Kuratowski theorem (see, e.g., [4])
states that each set in $\Delta^{0}_{2}$ can be expressed as an ordinal
difference of open sets, and conversely. In general, this implies that
properties of sets in $\Delta^{0}_{2}$ may be proved by induction over the
countable ordinals. Accordingly, we prove our main result by induction on $W$,
but the inductive step suggested by the Hausdorff-Kuratowski theorem does not
suit us completely. Instead, we mix it with a folklore alternative way of
describing $\Delta^{0}_{2}$ by induction. After this mix, our base case
consists of the open sets, the first inductive step consists of _union with a
closed set_ , and the second inductive step of _open union_.

To prove our result, the base case, where $W$ is open, amounts to reachability
games, and the wpo assumption is not needed. The case where $W$ is closed is
easy, and it includes the multi-energy games (where Player 1 keeps all energy
levels positive). Just above these, the case where $W$ is the union of an open
set and a closed set is harder to prove. It includes disjunctions of a
reachability condition and a multi-energy condition. We will present this
harder case in details because it shows part of the complexity of the full
result.

A fourth representation of $\Delta^{0}_{2}$: Above, we mentioned two
hierarchies that describe $\Delta^{0}_{2}$. In addition, this paper (re-)prove
the folklore result that $\Pi^{0}_{2}$ corresponds to Büchi winning conditions
and $\Sigma^{0}_{2}$ to co-Büchi. If labeling each history with $0$ or $1$,
the Büchi (co-Büchi) condition requires that infinitely (only finitely) many
$1$’s be seen on a branch/play. The $\Delta^{0}_{2}$ sets are therefore the
sets that can be expressed both by Büchi and co-Büchi conditions. This is
possible exactly if on every

Tightness of the result: The collection of the countable unions of closed sets
is called $\Sigma^{0}_{2}$, and the collection of their complements, i.e. the
countable intersections of open sets, is called $\Pi^{0}_{2}$. So
$\Delta^{0}_{2}=\Sigma^{0}_{2}\cap\Pi^{0}_{2}$. In this article we provide one
example of a winning set $W$ in $\Sigma^{0}_{2}$ and one example in
$\Pi^{0}_{2}$ that satisfy the wpo assumption but not the FM-strategy
sufficiency. Hence tightness.

Note that without the wpo assumption, even Turing-computable strategies may
not suffice to win for closed winning sets: take a non-computable binary
sequence $\rho$ and a game where Player 1 wins iff she plays $\rho$. She has a
winning strategy, but no computable ones.

Connections with graph games: Our game $\langle A,B,W\rangle$ can be seen as a
one-state concurrent graph game where the winning condition is defined via the
actions rather than the visited states. Winning strategies and FM strategies
coincide in both models.

Alternatively, we can unfold any concurrent graph game into an infinite tree
game $\langle A,B,W\rangle$ whose nodes are the histories of pairs of actions.
Winning strategies coincide in both models. Moreover, an FM strategy in the
tree game is, up to isomorphism, also an FM strategy in the graph game. The
converse may not hold since, informally, the player may observe the current
state only in the graph model. Nevertheless for finite graphs, the observation
of the state can be simulated by an additional finite memory, i.e. the graph
itself. To sum up, any FM result in our tree games can be translated into an
FM result in graph games. Almost conversely, FM results in finite-graph games
can be obtained from our tree games, possibly with non-optimal memory.

Related works and applications: The two articles [6] and [2] provide abstract
criteria to show finite-memory determinacy in finite-graph games: [6] by
Boolean combination of complex FM winning conditions with simple winning
conditions defined via regular languages; [2] by characterizing, for a fixed
memory, the winning conditions that yield, in all finite-graph games, FM
determinacy via this fixed memory. The FM determinacy of multi-energy games is
a corollary of neither, but as mentioned above, it is a direct corollary of
our result.

More generally on a finite-graph game, consider the conjunction or disjunction
of a multi-energy winning condition and a Boolean combination of reachability
conditions. This is in $\Delta^{0}_{2}$ (actually low at some finite level of
the hierarchy), this induces a wpo, so if Player 1 has a winning strategy she
has a FM one.

However, the FM determinacy of Büchi games in finite-graph games is not a
corollary of our result, because the Büchi conditions may not be in
$\Delta^{0}_{2}$. We mention three things about this. First, this determinacy
does not contradict our tightness results: in $\Pi^{0}_{2}$ or
$\Sigma^{0}_{2}$, FM determinacy holds when the corresponding labeling is
regular. Second, in future work we plan to seek a general theorem having both
this determinacy and our main result as special cases. Third, in finite-graph
games, many winning conditions that yield memoryless or FM determinacy can be
simulated by finite games, and therefore clopen winning conditions, i.e.
$\Delta^{0}_{1}$ instead of our more general $\Delta^{0}_{2}$. For instance,
see [1], [7], [3]. This suggests that our work could be used to prove more FM
sufficiency results by reduction of finite-graph games to tree games with wpo
winning condition in $\Delta^{0}_{2}$.

Structure of the article: Section 2 defines our games and finite-memory
strategies; Section 3 presents the related descriptive set theory; Section 4
presents our main result; Section 5 discusses tightness of our main result;
Section 6 mentions possible future work.

##  2 Setting and definitions

We study two-player games, which consist in a tuple $(A,B,W)$: $A$ is the
action set for Player $1$, $B$ is the action set for Player $2$ and
$W\subseteq(A\times B)^{\omega}$ is the winning set. Here we only consider
finitely branching games, where $A$ and $B$ are both finite. Such a game is
played in the following way: at each round, each player chooses an action from
their respective action set in a concurrent way, thus producing a pair of
actions in $A\times B$. The game then continues for infinitely many rounds,
generating a play which consists in an infinite word in $(A\times
B)^{\omega}$. Player $1$ then wins if the generated play belongs to the
winning set $W$, while Player $2$ wins if it does not. In the following we
will focus on Player $1$.

To describe the Players’ behavior in such a game, we use the concepts of
histories and strategies. A history is a finite word in $(A\times B)^{*}$ and
represents the state of the game after finitely many rounds. We call
$\mathcal{H}$ the set of histories. A strategy $s:\mathcal{H}\to A$ for Player
$1$ is a function that maps histories to actions and represents a behavior for
Player $1$: in history $h$, she will play action $s(h)$. Given a strategy $s$,
a history $h$ and a word $\beta\in B^{\omega}$, we call
$\text{out}(h,s,\beta)$ the only play where both players first play $h$, then
Player $1$ plays according to $s$ and Player $2$ plays the actions of $\beta$
in order. This play is defined inductively as follows:

  * •

for $k\leq|h|$, $\text{out}(h,s,\beta)_{<k}=h_{<k}$;

  * •

for $k>|h|$,
$\text{out}(h,s,\beta)_{<k}=\text{out}(h,s,\beta)_{<k-1}(s(\text{out}(h,s,\beta)_{<k-1}),\beta_{k-|h|-1})$.

We say that a play $\rho$ is compatible with a given strategy $s$ if there
exists $\beta\in B^{\omega}$ such that $\rho=\text{out}(\varepsilon,s,\beta)$,
where $\varepsilon$ is the empty history. Similarly, a history is compatible
with $s$ if it is the finite prefix of a compatible play. We say that a
strategy is winning if all the plays compatible with it belong to $W$: if
Player $1$ plays according to such a strategy, she is guaranteed to win. We
can extend this concept to say that a strategy $s$ is winning from a history
$h$ when for all $\beta\in B^{\omega}$ we have $\text{out}(h,s,\beta)\in W$
(if in history $h$ Player $1$ starts playing according to $s$ then she will
win). We call a winning history a history from which there exists a winning
strategy.

We call a tree any subset of $(A\times B)^{*}$ which is closed by prefix, and
a branch any (finite or infinite) sequence of elements
$e_{0}=\varepsilon\sqsubset e_{1}\sqsubset e_{2}\sqsubset...$ of a tree. In
particular, all histories compatible with a given strategy form a tree, which
we call the strategic tree induced by the strategy. We makes extensive use of
Kőnig’s lemma [5], which states that if a tree has no infinite branch then it
is a finite tree. Specifically, we often use the derived result that if some
family in a tree intersects all infinte branches of the tree then it has a
finite subset that also does.

Given a history $h\in\Gamma$, we say that an action $a\in A$ is non-losing for
$h$ if for any action $b\in B$, $h(a,b)$ is a winning history. Among all
histories, we are particularly interested in the set of histories along which
Player $1$ has only played non-losing actions: we call $\Gamma$ this
particular set. Notice that Player $1$ has a winning strategy from any history
$h\in\Gamma$, but that playing only non-losing for Player $1$ might be a
losing strategy.

A history $h\in\mathcal{H}$ induces a winning set $W_{h}$ defined as
$W_{h}=\\{\rho\in(A\times B)^{\omega}\mid h\rho\in W\\}$. The set $W_{h}$
contains all the infinite continuations $\rho$ such that $h\rho$ is a winning
play.

Recall that we introduced strategies for Player $1$ as functions mapping
histories to actions in $A$. Among these strategies, we are particularly
interested in those that can be described as finite machines: we call them
finite-memory strategies. Let us introduce first the concept of finite-memory
decision machines. A finite-memory decision machine is a tuple
$(M,\sigma,\mu,m_{0})$ such that:

  * •

$M$ is a finite set (the memory);

  * •

$\sigma:M\to A$ is the decision function;

  * •

$\mu:M\times(A\times B)\to M$ is the memory update function;

  * •

$m_{0}\in M$ is the initial memory state.

Given a finite-memory decision machine $(M,\sigma,\mu,m_{0})$, we extend $\mu$
by defining $\mu(m,h)$ for $h\in\mathcal{H}$ in the following inductive way:

  * •

$\mu(m,\varepsilon)=m$

  * •

for all $h$ in $\mathcal{H}$ and $(a,b)\in A\times B$,
$\mu(m,h(a,b))=\mu(\mu(m,h),(a,b))$.

For readability’s sake, in case $m=m_{0}$ and the context is clear, we write
$\mu(h)$ for $\mu(m,h)$.

A finite-memory decision machine $(M,\sigma,\mu,m_{0})$ induces a strategy $s$
for Player $1$ defined for all $h\in\mathcal{H}$ as
$s(h)=\sigma(\mu(m_{0},h))$. We say that a strategy $s$ is a finite-memory
strategy if it is induced by some finite-memory decision machine, and
abusively write $s=(M,\sigma,\mu,m_{0})$ (identifying the finite-memory
decision machine with the strategy it induces) when it is the case.

We often describe a finite-memory decision machine by only defining $\mu$ for
the action pairs that are compatible with $\sigma$ (i.e. for $m\in M$ we only
define $\mu(m,(a,b))$ when $a=\sigma(m)$). Such a partial machine can be
easily extended to a complete one, and contains all the relevant information
to decide on the winning aspect of the strategy (or rather, strategies, as
many different extensions are possible) it induces as it describes all plays
compatible with itself.

##  3 Descriptive set theory

###  3.1 Open sets and the Borel hierarchy

Given a set $C$ and a finite word $w\in C^{*}$, we call cylinder of $w$ the
set $\textnormal{cyl}(w)=\\{w\rho\mid\rho\in C^{\omega}\\}$. This set contains
all the infinite words that start with $w$. In concordance with the usual
cylinder topology on $C^{\omega}$, the cylinders serve as the basis for the
open sets, in the sense that we define as an open set any set that can be
written as an arbitrary union of cylinders. We say that a family of words
$\mathcal{F}$ is a generating family for an open set $O$ if we have
$O=\cup_{f\in\mathcal{F}}\textnormal{cyl}(f)$, that is, $O$ is the set of all
plays that have at least one finite prefix in $\mathcal{F}$.

These open sets allow to define a Borel algebra on $C^{\omega}$ as the
smallest $\sigma$-algebra that contains all open sets. More precisely, the
Borel algebra is the smallest collection of sets that contains the open sets
and is closed under both countable union and complement (for more information
about Borel sets, see [4]). This collection of sets can be organized into what
is called the Borel hierarchy, which is defined for countable ordinals in the
following way:

  * •

$\Sigma_{1}^{0}$ is the collection of all the open sets;

  * •

for all countable ordinals $\theta$, $\Pi_{\theta}^{0}$ is the collection of
sets whose complements are in $\Sigma_{\theta}^{0}$;

  * •

for all countable ordinals $\theta$, $\Sigma_{\theta}^{0}$ is the collection
of sets that can be defined as a countable union of sets belonging to lower
levels of the hierarchy;

  * •

finally, for all countable ordinals $\theta$, $\Delta_{\theta}^{0}$ is the
collection of sets that are in both $\Sigma_{\theta}^{0}$ and
$\Pi_{\theta}^{0}$.

To illustrate, let us detail the lowest levels of the hierarchy:

  * •

as per the definition, $\Sigma_{1}^{0}$ is the collection of all the open
sets;

  * •

the sets in $\Pi_{1}^{0}$ are the sets whose complement is an open set, we
call them the closed sets;

  * •

$\Sigma_{2}^{0}$ contains the sets which can be written as a countable union
of closed sets;

  * •

$\Pi_{2}^{0}$ contains the sets which complement can be written as a countable
union of closed sets: by properties of the complement, these are the sets that
can be written as a countable intersection of open sets;

  * •

finally, $\Delta_{2}^{0}$ is the collection of sets that can be written both
as a countable union of closed sets and as a countable intersection of open
sets.

In the following we will focus on the collection of sets $\Delta_{2}^{0}$.

###  3.2 The Hausdorff difference hierarchy

The Hausdorff difference hierarchy (see for instance [4]) provides us with a
way of defining inductively all the sets in $\Delta_{2}^{0}$. Formally, given
an ordinal $\theta$ and an increasing sequence of open sets
$(O_{\eta})_{\eta<\theta}$, the set $D_{\theta}((O_{\eta})_{\eta<\theta})$ is
defined by:

$\rho\in
D_{\theta}((O_{\eta})_{\eta<\theta})\quad\Leftrightarrow\quad\begin{array}[]{@{}l}\rho\in\cup_{\eta<\theta}O_{\eta}\
\text{and the least}\ \eta\ \text{such that}\ \rho\in O_{\eta}\\\ \text{has
parity opposite to that of}\ \theta.\end{array}$

For any ordinal $\theta$, we call $\mathcal{D}_{\theta}$ the collection of
sets $S$ such that there exists an increasing family of open sets
$(O_{\eta})_{\eta<\theta}$ such that $S=D_{\theta}((O_{\eta})_{\eta<\theta})$.
To illustrate, $\mathcal{D}_{1}$ is the collection of all the open sets,
$\mathcal{D}_{2}$ is the collections of the sets that can be written as
$O_{1}\setminus O_{0}$ where $O_{1}$ and $O_{0}$ are two open sets (and hence
contains the closed sets), $\mathcal{D}_{3}$ is the collection of the sets
that can be written as $O_{2}\setminus(O_{1}\setminus O_{0})$ where $O_{2}$,
$O_{1}$ and $O_{0}$ are three open sets, etc.

The Hausdorff-Kuratowski theorem [4] then states that a set $S$ belongs to
$\Delta_{2}^{0}$ if and only if there exists an ordinal $\theta$ such that
$S\in\mathcal{D}_{\theta}$.

###  3.3 The fine Hausdorff hierarchy

In the spirit of the Hausdorff difference hierarchy, we propose another
inductive way of defining the sets in $\Delta_{2}^{0}$. This other hierarchy
was already introduced in [8], and might have appeared earlier in the
literature but to our knowledge has never been studied in similar depth. First
we introduce the concept of open union: we say that the union of a family of
sets $(S_{i})_{i\in I}$ is an open union if there exists a family of disjoint
open sets $(O_{i})_{i\in I}$ such that for all $i\in I$ have $S_{i}\subseteq
O_{i}$. We denote such a union by $\Cup_{i\in I}S_{i}$.

We then define inductively collections of sets $\Lambda_{\theta}$ and
$K_{\theta}$, with $\theta$ a positive ordinal, in the following way:

  * •

a set $S$ is in $\Lambda_{1}$ if and only if it is an open set;

  * •

a set $S$ is in $K_{\theta}$ if and only if its complement is in
$\Lambda_{\theta}$;

  * •

a set $S$ is in $\Lambda_{\theta}$ with $\theta>1$ if and only if there exists
a family of sets $(S_{i})_{i\in I}$ such that for each $i$ there exists
$\eta_{i}<\theta$ such that $S_{i}\in\Lambda_{\eta_{i}}\cup K_{\eta_{i}}$ and
we have $S=\Cup_{i\in I}S_{i}$.

This definition is akin to the definition of the Borel hierarchy, with the
exception that the union operation is replaced with an open union. We then
prove the following theorem, which shows our hierarchy is a refinement of the
Hausdorff difference hierarchy (and hence justifies its name):

######  Theorem 3.1.

For all ordinals $\theta$, we have $\mathcal{D}_{\theta}=\Lambda_{\theta}$.

This theorem is naturally proven by induction on $\theta$ and requires
intermediate results which help understand the nature of the two hierarchies.
In particular, we have: (i) for all ordinals $\theta$ the collection
$\mathcal{D}_{\theta}$ is closed under open union, (ii) for all ordinals
$\theta$ the collection $\Lambda_{\theta}$ is closed by intersection with an
open set, (iii) for all ordinals $\theta$ the two collections
$\Lambda_{\theta}$ and $K_{\theta}$ are closed under intersection with a
cylinder and (iv) for all limit ordinals $\theta$ the collection
$\mathcal{D}_{\theta}$ is the collection of sets that can be written as the
open unions of sets in $\cup_{\eta<\theta}\mathcal{D}_{\eta}$. One observation
which proves pivotal for proving our main result on the existence of finite-
memory strategies is that for all ordinals $\theta$, all sets in $K_{\theta}$
can be written as the union of a closed set and a set that belongs to
$\Lambda_{\theta}$ (if $\theta$ is a successor odinal, we can be even more
precise as $K_{\theta}$ is the collection of all sets that can be written as
the union of a closed set and a set in $\Lambda_{\theta-1}$). All the details
surrounding these two views and the proof of theorem 3.1 can be found in
appendix A.

###  3.4 The 0-1 eventually constant labelling

A third possible view of sets in $\Delta_{2}^{0}$ is given via eventually
constant labelling functions. We say that a labelling function
$l:C^{*}\to\\{0,1\\}$ is eventually constant if for all infinite words $\rho$
in $C^{\omega}$, the sequence $(l(w_{<n}))_{n\in\mathcal{N}}$ is eventually
constant, which means that there exists a finite $k\in\mathcal{N}$ and
$i\in\\{0,1\\}$ such that for all $n\geq k$ we have $l(w_{<n})=i$. We then
call $1_{l}$ the set of infinite words $w\in C$ such that the set $\\{n\mid
l(w_{<n})=1\\}$ is infinite. As we will see, the sets $S$ that belong to
$\Delta_{2}^{0}$ are the sets such that there exists an eventually constant
labelling function $l$ such that $S=1_{l}$.

###  3.5 Equivalence of representations

####  3.5.1 Representations of sets in $\Delta_{2}^{0}$

As expressed by the following theorem, the Hausdorff difference hierarchy,
fine Hausdorff hierarchy and eventually constant labelling functions actually
define the same sets, which are exactly the sets that belong to
$\Delta_{2}^{0}$.

######  Theorem 3.2.

Given a subset $S$ of $C^{\omega}$, the following propositions are equivalent:

  * $(1)$

$S\in\Delta_{2}^{0}$;

  * $(2)$

$S$ belongs to the Hausdorff difference hierarchy;

  * $(3)$

$S$ belongs to the fine Hausdorff hierarchy;

  * $(4)$

there exists an eventually constant labelling function $l$ such that
$S=1_{l}$.

The detailed proof can be found in Appendix A.4, but we give some elements
here: the Hausdorff-Kuratowski theorem [4] shows that $(1)\Leftrightarrow(2)$,
and Theorem 3.1 shows that $(2)\Leftrightarrow(3)$. We prove that
$(3)\Rightarrow(4)$ by showing that the collection of sets of the form $1_{l}$
where $l$ is an eventually constant labelling function is closed under both
open union and complement, and finally prove that $(4)\Rightarrow(1)$ by
showing that all sets of the form $1_{l}$ where $l$ is an eventually constant
labelling function can be expressed both as countable intersection of open
sets and countable union of closed sets.

####  3.5.2 Correspondence between Büchi/co-Büchi conditions and
$\Pi_{0}^{2}$/$\Sigma_{0}^{2}$

Two much studied types of winning condition in computer science are the Büchi
and co-Büchi conditions. Such winning conditions are given by a coloring
function $c$ that provides a color (elements in $\\{0,1\\}$) for every
history. In the case of a Büchi condition, a play is then winning if
infinitely many of its prefixes are associated with the color $1$ while in the
case of a co-Büchi condition it is winning if finitely many of its prefixes
are associated with the color $1$ (Büchi and co-Büchi conditions are thus the
complement of each other). As stated by the following lemma, whose proof can
be found in Appendix A.5, Büchi conditions actually describe the sets in
$\Pi_{2}^{0}$:

######  Lemma 3.3.

A subset $S$ of $C^{\omega}$ belongs to $\Pi_{2}^{0}$ if and only if it can be
expressed as a Büchi condition.

A trivial corollary is that co-Büchi conditions describe the sets in
$\Sigma_{2}^{0}$:

######  Corollary 3.4.

$W$ belongs to $\Sigma_{2}^{0}$ if and only if it can be expressed as a co-
Büchi condition.

##  4 On the existence of finite-memory winning strategies when the winning
set belongs to the Hausdorff difference hierarchy

Our aim is to exhibit conditions on $W$ that ensure Player $1$ has a finite-
memory winning strategy when some winning strategy exists.

Consider a game $(A,B,W)$ where the winning set $W$ belongs to
$\Delta_{2}^{0}$. We introduce a new hypothesis on the induced winning sets of
this game: the set inclusion relation, denoted by $\subseteq$, induces a well
partial order (wpo) on the winning sets induced by the histories in $\Gamma$.
That is, for any sequence $(h_{n})_{n\in\mathbb{N}}$ of histories in $\Gamma$,
there exists $k<l$ such that $W_{h_{k}}\subseteq W_{h_{l}}$. A known property
of well partial orders which we will use is that any set $S\subseteq\Gamma$
contains a finite subset $M$ such that for all $h\in S$ there exists $m\in M$
such that $W_{m}\subseteq W_{h}$. The set of winning sets induced by the
histories in $M$ effectively functions as a finite set of under-approximations
for the winning sets induced by the histories in $S$.

Such hypotheses might seem exotic and restrictive, but are effectively
satisfied for well-studied classes of games, such as energy games or multi-
energy games played on graphs (see for instance [9]), or games with a winning
condition expressed as a boolean combination of reachability/safety
conditions.

Under these specific conditions, we prove that Player $1$ always has a finite-
memory winning strategy when she has a winning strategy:

######  Theorem 4.1.

Assume that $W$ belongs to $\Delta_{2}^{0}$ and $\subseteq$ induces a well
partial order on $\\{W_{h}\mid h\in\Gamma\\}$. If Player $1$ has a winning
strategy from $\varepsilon$, then she also has a finite-memory one.

Given a set $S$ in the Hausdorff difference hierarchy, the rank of $S$ is the
least ordinal $\theta$ such that $S\in\mathcal{D}_{\theta}$. We prove Theorem
4.1 by a transfinite induction on the rank of $W$.

First notice that the inclusion of induced winning sets has the nice property
of being preserved by the addition of a suffix, which is formally expressed by
the following lemma:

######  Lemma 4.2.

If $W_{h}\subseteq W_{h^{\prime}}$ then for all $(a,b)\in A\times B$ we have
$W_{h(a,b)}\subseteq W_{h^{\prime}(a,b)}$.

######  Corollary 4.3.

If $W_{h}\subseteq W_{h^{\prime}}$ then all non-losing actions of $h$ are also
non-losing for $h^{\prime}$.

###  4.1 Proof for open sets

We begin by the case where $W$ is an open set ($W$ has rank $1$), generated by
a set $\mathcal{F}$ of histories.

######  Lemma 4.4.

If $W$ is an open set and $\varepsilon\in\Gamma$, then Player $1$ has a
finite-memory winning strategy from $\varepsilon$.

######  Proof 4.5.

Suppose that there exists a winning strategy $s$ from $\varepsilon$. Then
consider the strategic tree $T$ induced by $s$, and consider the tree
$T^{\prime}=T\setminus\\{h\in\mathcal{H}\mid\exists f\in\mathcal{F},f\sqsubset
h\\}$, where $\sqsubset$ is the strict prefix relation. Since $s$ is winning,
there is no infinite branch in $T^{\prime}$. By Kőnig’s lemma, this means that
$T^{\prime}$ is finite and by definition all maximal elements (with regards to
$\sqsubseteq$, the prefix relation) of $T^{\prime}$ belong to $\mathcal{F}$.
$T^{\prime}$ can then serve as the memory of a finite-memory winning strategy
$s_{f}=(T^{\prime},\sigma,\mu,m_{0})$ defined by:

  * •

for $t\in T^{\prime}\setminus\mathcal{F}$, $\sigma(t)=s(t)$;

  * •

for $t\in T^{\prime}\cap\mathcal{F}$, we set $\sigma(t)$ as any action $a\in
A$;

  * •

for $t\in T^{\prime}$ and $b\in B$, $\mu(t,(\sigma(t),b))=t(\sigma(t),b)$ if
$t\notin\mathcal{F}$ and $\mu(t,(\sigma(t),b))=t$ if $t\in\mathcal{F}$;

  * •

$m_{0}=\varepsilon$.

The strategy $s_{f}$ works by simply following $s$ alongside the branches of
$T^{\prime}$ until it reaches a history in $\mathcal{F}$, and is thus winning.

###  4.2 Proof for closed sets

We now focus on the study of the case where the winning set $W$ is a closed
set. In that case, the plays $\rho$ such that $\rho\in W$ are precisely the
plays for which all finite prefixes $h$ are such that $W_{h}\neq\emptyset$. As
a consequence, any strategy playing non-losing actions for Player $1$ is a
winning strategy: such a strategy only generates histories $h$ in $\Gamma$,
and in particular $W_{h}\neq\emptyset$.

Furthermore, if $\subseteq$ induces a well partial order on the partial
winning sets, then:

  1. $(*)$

there exists a finite subset $M$ of $\Gamma$ such that for all $h\in\Gamma$
there exists $m\in M$ such that $W_{m}\subseteq W_{h}$;

  2. $(**)$

any play $\rho$ has two finite prefixes $\rho_{0}$ and $\rho_{1}$ such that
$\rho_{0}\sqsubset\rho_{1}$ and $W_{\rho_{0}}\subseteq W_{\rho_{1}}$.

These two observations are the basis for two different approaches to prove the
next lemma.

######  Lemma 4.6.

If $W$ is an open set, if $\subseteq$ induces a well partial order on
$(W_{h})_{h\in\Gamma}$ and if $\varepsilon\in\Gamma$, then Player $1$ has a
finite-memory winning strategy from $\varepsilon$.

######  Proof 4.7.

Consider indeed a game $(A,B,W)$ where $W$ is a closed set, $\subseteq$
induces a well partial order on the partial winning sets associated with the
winning histories and such that $\varepsilon$ is a winning history. We
consider a strategy $s$ that is a winning strategy for Player $1$.

The first approach, derived from observation $(*)$, consists in building a
finite-memory strategy $(M,\sigma,\mu,m_{0})$ with memory set $M$ in the
following way:

  * •

for $m\in M$, we let $\sigma(m)$ be any non-losing action from $m$,

  * •

for $m\in M$ and $b\in B$, since $\sigma(m)$ is non-losing we know that
$m(\sigma(m),b)\in\Gamma$, which means that there exists $m^{\prime}\in M$
such that $W_{m^{\prime}}\subseteq W_{m(\sigma(m),b)}$; we then let
$\mu(m,(\sigma(m),b))=m^{\prime}$;

  * •

finally $m_{0}\in M$ is chosen such that we have $W_{m_{0}}\subseteq
W_{\varepsilon}$.

Informally, we have as our memory the set $M$ which contains under-
approximations for all winning sets induced by the histories of $\Gamma$. We
use the transition function to maintain an under-approximation of the "real"
induced winning set associated to the current history, and play according to
this under-approximation. By Corollary 4.3, this ensures that we always play a
non-losing action, which is enough to guarantee the win because $W$ is a
closed set.

The second approach is derived from observation $(**)$. Consider the winning
strategy $s$ and its associated strategic tree $T_{s}$. Along every infinite
branch $\rho$ of $T_{s}$, there exist two histories $h,h^{\prime}$ such that
$h\sqsubset h^{\prime}$ and $W_{h}\subseteq W_{h^{\prime}}$. Consider then the
tree $T_{s}^{f}$ obtained by pruning $T_{s}$ along these histories:
$T_{s}^{f}=\\{h^{\prime}\in T_{s}\mid\forall h\in T_{s},h\sqsubset
h^{\prime}\Rightarrow W_{h}\nsubseteq W_{h^{\prime}}\\}$. By Kőnig’s lemma,
$T_{s}^{f}$ is a finite tree. We call $\mathcal{P}$ the set $\\{h\in T_{s}\mid
h\notin T_{s}^{f}\text{ and }h^{\prime}\sqsubset h\Rightarrow h^{\prime}\in
T_{s}^{f}\\}$ of the minimal elements (with regards to the prefix relation) of
$T_{s}$ that do not belong to $T_{s}^{f}$. We then build a finite-memory
strategy $(M^{\prime},\sigma,\mu,m_{0})$ in the following way:

  * •

$M^{\prime}=T_{s}^{f}$

  * •

for $m\in M^{\prime}$, we let $\sigma(m)=s(m)$,

  * •

for $m\in M^{\prime}$ and $(a,b)\in A\times B$ such that $a=\sigma(m)=s(m)$,

    * –

if $m(a,b)\in T_{s}^{f}$ then we let $\mu(m,(a,b))=m(a,b)$,

    * –

else by construction we have $m(a,b)\in\mathcal{P}$ and there exists
$m^{\prime}\in T_{s}^{f}$ such that $m^{\prime}\sqsubset m(a,b)$ and
$W_{m}\subseteq W_{m(a,b)}$; we then let $\mu(m,(a,b))=m^{\prime}$,

  * •

finally $m_{0}=\varepsilon$.

Informally, this approach consists in playing according to $s$ until we reach
a history whose induced winning set is bigger than one we already met. We then
forget the current history and continue playing as if we were in the history
with the smaller induced winning set. This second approach also ensures that
the memory consists of an under-approximation of the "real" induced winning
set, and hence by Corollary 4.3 it guarantees that the resulting strategy is
non-losing, and thus winning since $W$ is a closed set.

###  4.3 Limitations to the above approaches

Until now, we have studied the lowest levels of the Hausdorff difference
hierarchy, focusing on the cases where the winning sets belongs to
$\Lambda_{1}$, the open sets, and $K_{1}$, the closed sets. We will explain
later how to handle the case for $\Lambda_{2}$ and for now turn our attention
to $K_{2}$, as it proves pivotal to the understanding of our method.

The sets in $K_{2}$ are the sets that can be written as the union of a closed
set and an open set. Informally, this means that Player $1$ can win in two
different ways, by ensuring that either the generated play lies in the closed
set or they reach a history which belongs to the generating family of the open
set.

The first condition is akin to a safety objective (Player $1$ manages to never
go out of a certain region) while the second condition is akin to a
reachability objective (Player $1$ meets a certain given condition at a finite
time and it suffices to ensure the win). As shown by the following example,
the two simple approaches we detailed previously for closed sets do not
suffice here:

pt$(\\{0\\}\times B)^{\omega}$$\emptyset$$\emptyset$$(\\{0\\}\times
B)^{\omega}$$\emptyset$$\emptyset$$(A\times B)^{\omega}$$(A\times
B)^{\omega}$$(A\times B)^{\omega}$$(A\times B)^{\omega}$$(A\times
B)^{\omega}$$(A\times
B)^{\omega}$…pt$00$pt$01$pt$10$11pt$00$pt$01$pt$10$$11$pt$00$pt$01$pt$10$$11$pt$00$pt$01$pt$10$$11$pt$00$
Figure 1: A game for which the naive algorithm does not work. For the sake of
concision, the pairs of actions in $A\times B$ are written as two-letter
words. In red is the partial winning set of the corresponding history.
pt$\varepsilon$$(0,1)$00pt$(0,0)$pt$\\{0\\}\times B$pt$(0,1)$ Figure 2: The
finite-memory strategy generated by approaches $(*)$ and $(**)$ for the game
represented in Figure 1. Each state is labeled by the history associated to
it, and in red is the action associated to that state.

######  Example 4.8.

Consider the game $(A,B,W)$ with $A=B=\\{0,1\\}$ and
$W=(0,0)^{*}(0,1)(\\{0\\}\times B)^{\omega}+(0,0)^{2}(0,0)^{*}(\\{1\\}\times
B+A\times\\{1\\})(A\times B)^{\omega}$. This game is described in Figure 1. In
other words, Player $1$ has two ways to win:

  * •

either the players play $(0,1)$ or $(0,0)(0,1)$ and Player $1$ then only has
to play action $0$ forever;

  * •

or the players play $(0,0)$ twice and then one player plays action $1$,
reaching a point where all possible continuations are winning for Player $1$.

As $W$ can be expressed via a regular expression, it induces finitely many
partial winning sets, which means that $\subseteq$ trivially induces a well
partial order over said partial winning sets. Moreover, $W$ can be expressed
as the union of an open set and a closed set (the closed set corresponds to
the first item above, while the open set corresponds to the second item), and
hence belongs to the Hausdorff difference hierarchy (more precisely it belongs
to $K_{2}$).

Moreover, one can easily check that $W_{\varepsilon}\subseteq W_{(0,0)}$. As a
consequence, both approach $(*)$ and approach $(**)$ yield the finite-memory
strategy described in Figure 2. This strategy is not winning for Player $1$,
as if Player $2$ always plays action $0$ it will generate the play
$(0,0)^{\omega}$, which does not belong to $W$.

###  4.4 Proofs for sets in $K_{2}$

To better understand how the proof works in the general case, we propose here
to study the basic case of sets in $K_{2}$. As we have seen previously, the
two approaches that worked well for the case where the winning set is a closed
set do not suffice in that case. We prove the following result:

######  Theorem 4.9.

If $W$ is in $K_{2}$, if $\subseteq$ induces a well partial order on
$(W_{h})_{h\in\Gamma}$ and if $\varepsilon\in\Gamma$, then Player $1$ has a
finite-memory winning strategy from $\varepsilon$.

Let us suppose then that $W$ is in $K_{2}$: as already mentioned, $W$ is the
union of a closed set $C$ and an open set $O$. We let $\mathcal{F}$ be the
generating family of $O$ and denote by $\text{Pref}(C)$ the set of histories
which have at least one continuation in $C$, that is
$\text{Pref}(C)=\\{h\in\mathcal{H}\mid\exists\rho,h\rho\in C\\}$.

As a preliminary observation, recall we already know how to handle the case
when the winning set is open. The method also works well for the general case
when Player $1$ is able to reach $O$ by herself (that is, she have a winning
strategy for $O$). We also know that finding a finite-memory non-losing
strategy for Player $1$ is always possible (see for instance the method $(*)$
for the case where the winning set is closed). As a consequence, a simple
method one would be tempted to try would be the following:

  * •

follow some non-losing strategy as long as the current history belongs to
$\text{Pref}(C)$;

  * •

as soon as we detect we have left $\text{Pref}(C)$, play some finite-memory
winning strategy to reach a history in $\mathcal{F}$ (this is possible because
if we have played in a non-losing fashion so far and the current history does
not belong to $\text{Pref}(C)$, then the only way to win from there is to
produce a play that belongs to $O$).

This method should produce a finite-memory winning strategy, however it relies
on the assumption that one is able to detect whether or not the current
history belongs to $\text{Pref}(C)$ using only finite memory. This assumption
does not rely on any solid ground, which makes this method incorrect. We
propose another construction of a finite-memory winning strategy, which does
not need to detect when the current history stops belonging to
$\text{Pref}(C)$, but which ensures that $\mathcal{F}$ will be reached if it
were the case (despite not knowing it).

Consider indeed a history $\overline{h}$ in $\Gamma\cap\text{Pref}(C)$ and a
history $h$ in $\Gamma$ such that $h\notin\text{Pref}(C)$ and
$W_{\overline{h}}\subseteq W_{h}$. We call $TC(\overline{h},h)$ the set
$\\{hl\mid\overline{h}l\in\text{Pref}(C)\\}$ consisting of the finite
continuations from $\overline{h}$ that belong to $\text{Pref}(C)$, but rooted
in $h$. Notice that for all infinite continuations $\rho$ such that
$\overline{h}\rho\in C$, we have $\overline{h}\rho\in W$, which means that
$h\rho\in W$ (since $W_{\overline{h}}\subseteq W_{h}$) and hence that
$h\rho\in O$ since $h\notin\text{Pref}(C)$ (which means that all winning
continuations of $h$ belong to $O$ because they cannot belong to $C$). We thus
know that $TC(\overline{h},h)$ contains a family of histories
$\mathcal{F}_{\overline{h},h}$ included in $\mathcal{F}$ (or in the case where
$h$ itself has a strict prefix in $\mathcal{F}$, we set
$\mathcal{F}_{\overline{h},h}=\\{h\\}$) and such that all infinite branches of
$TC(\overline{h},h)$ have a finite prefix in $\mathcal{F}_{\overline{h},h}$,
and by Kőnig’s lemma we know this family is finite. We call
$0pt(\overline{h},h)$ the maximal length of the elements in
$\mathcal{F}_{\overline{h},h}$. Intuitively, this means that, if the current
history were $h$ but Player $1$ only knew of its under-approximation
$\overline{h}$, she could ensure the win by following a play whose finite
prefixes $l$ were such that $\overline{h}l\in\text{Pref}(C)$ for
$0pt(\overline{h},h)$ steps. This however still requires to compute the value
of $0pt(\overline{h},h)$ and hence to know of $h$. However, as stated by the
following lemma, the value of $0pt(\overline{h},h)$ for all eligible $h$ is
bounded.

######  Lemma 4.10.

For all $\overline{h}$ in $\text{Pref}(C)$, $\\{0pt(\overline{h},h)\mid
h\in\Gamma,h\notin\text{Pref}(C),W_{\overline{h}}\subseteq W_{h}\\}$ is
bounded.

The proof of this lemma can be found in appendix B.1, and makes use of the
well partial order hypothesis.

For $\overline{h}$ in $\Gamma\cap\text{Pref}(C)$, we will then call
$0pt(\overline{h})$ the upper bound of $0pt(\overline{h},h)$ for $h$ meeting
the criteria described above. The idea is the following: if the current
history is $h\in\Gamma$, but Player $1$ only knows of its under-approximation
$\overline{h}$, and then plays some finite continuation $l$ of length
$0pt(\overline{h})$ (which is independent of $h$) such that
$\overline{h}l\in\text{Pref}(C)$, then she ensured the win as $hl$ has a
finite prefix in $\mathcal{F}$. This is formally stated in the following
lemma:

######  Lemma 4.11.

Let $\overline{h}\in\text{Pref}(C)$ and $h\notin\text{Pref}(C)$ such that
$W_{\overline{h}}\subseteq W_{h}$. Let $\rho\in(A\times B)^{\omega}$ such that
for all finite prefixes $l$ of $\rho$ such that $|l|\leq 0pt(\overline{h})$ we
have $\overline{h}l\in\text{Pref}(C)$. Then $h\rho\in O$.

######  Proof 4.12.

Let $l$ be the finite prefix of $\rho$ of length $0pt(\overline{h})$. As
$0pt(\overline{h},h)\leq 0pt(\overline{h})$ we know that $hl$ has a prefix in
$\mathcal{F}$, hence the result.

Consider now a finite family $(h_{i})_{i\in I}$ of histories in
$\Gamma\setminus\text{Pref}(C)$ such that for all $h\in\text{Pref}(C)$ there
exists $i\in I$ such that $W_{h_{i}}\subseteq W_{h}$. For all $i\in I$ there
exists a finite-memory decision machine $(M_{i},\sigma_{i},\mu_{i},m_{i})$
associated with a of finite-memory strategy $(s_{i})_{i\in I}$ such that
$s_{i}$ wins from $h_{i}$. As a consequence, for all
$h\in\Gamma\setminus\text{Pref}(C)$ there exists $i\in I$ such that $s_{i}$
wins from $h$. Consider also a finite family $(\overline{h}_{j})_{j\in J}$ of
histories in $\Gamma\cap\text{Pref}(C)$ indexed by $J\subseteq\mathbb{N}$ such
that for all histories $\overline{h}$ in $\text{Pref}(C)\cap\Gamma$ there
exists $j\in J$ such that $W_{\overline{h}_{j}}\subseteq W_{\overline{h}}$.
For all $j\in J$, let $T_{j}=\\{\overline{h}_{j}l\mid|l|\leq
0pt(\overline{h}_{j})\\}$. Up to renaming, we can suppose that the $T_{j}$’s
are disjoint from one another. We build our finite-memory winning strategy
$s=(M,\sigma,\mu,m_{0})$ in the following way:

  * •

$M=\cup_{i\in I}M_{i}\cup\cup_{j\in J}T_{j}$;

  * •

for $m\in M_{i}$ we let $\sigma(m)=\sigma_{i}(m)$;

  * •

for $t\in T_{j}$ we let $\sigma(t)$ be any non-losing action from $t$;

  * •

for $m\in M_{i}$ and $(a,b)\in A\times B$ we let
$\mu(m,(a,b))=\mu_{i}(m,(a,b))$;

  * •

for $t\in T_{j}$ and $(a,b)\in A\times B$ such that $a=\sigma(t)$:

    * –

if $t(a,b)\in T_{j}$ then $\mu(t,(a,b))=t(a,b)$;

    * –

else if $t(a,b)\in\Gamma\setminus\text{Pref}(C)$ then there exists $i\in I$
such that $s_{i}$ wins from $t(a,b)$: we let $\mu(t,(a,b))=m_{i}$;

    * –

else if $t(a,b)\in\Gamma\cap\text{Pref}(C)$ then there exists $j\in J$ such
that $W_{\overline{h}_{j}}\subseteq W_{t(a,b)}$ and we let
$\mu(h,(a,b))=\overline{h}_{j}$;

  * •

$m_{0}=\overline{h}_{j}$ where $j\in J$ is such that
$W_{\overline{h}_{j}}\subseteq W_{\varepsilon}$.

We prove this finite-memory strategy is winning for Player $1$. To this end,
let us first show that for all compatible histories $h$ such that $\mu(h)\in
T_{j}$ for some $j\in J$, the memory state $\mu(h)$ provides an under-
approximation of the winning set induced by $h$:

######  Lemma 4.13.

If $\mu(h)\in T_{j}$ for some $j\in J$ then we have $W_{\mu(h)}\subseteq
W_{h}$.

######  Proof 4.14.

The proof is by induction on $h$. First we have $\mu(\varepsilon)=m_{0}$ and
per the definition $W_{m_{0}}\subseteq W_{\varepsilon}$. Now consider
$h\in\mathcal{H}$ such that $\mu(h)\in T_{j}$ for some $j\in J$ and
$W_{\mu(h)}\subseteq W_{h}$. Let $(a,b)\in A\times B$ such that
$\mu(h(a,b))\in T_{j^{\prime}}$ for some $j^{\prime}\in J$. Then,

  * •

if $\mu(h)(a,b)\in T_{j}$ then we have $\mu(h(a,b))=\mu(h)(a,b)$ and the
desired result follows by Lemma 4.2,

  * •

else we must have $\mu(h)(a,b)\in\Gamma\cap\text{Pref}(C)$ (else we would not
have $\mu(h(a,b))\in T_{j^{\prime}}$) and
$\mu(h(a,b))=\overline{h}_{j^{\prime}}$ with $j^{\prime}$ such that
$W_{\overline{h}_{j^{\prime}}}\subseteq W_{\mu(h)(a,b)}$, and
$W_{\mu(h)(a,b)}\subseteq W_{h(a,b)}$ once again by Lemma 4.2, which ensures
the result.

As a consequence of Lemma 4.13, when $h$ is such that $\mu(h)\in T_{j}$ for
some $j\in J$ then we have $W_{\mu(h)}\subseteq W_{h}$. As a consequence, for
all $(a,b)\in A\times B$ we have $W_{\mu(h)(a,b)}\subseteq W_{h(a,b)}$. This
ensures that if $\mu(h)(a,b)\in\Gamma\setminus\text{Pref}(C)$ and the strategy
$s_{i}$ wins from $\mu(h)(a,b)$ then $s_{i}$ also wins from $h(a,b)$, which
explains why our finite-memory strategy is winning. Formally, we have the
following lemma:

######  Lemma 4.15.

If $\rho\in(A\times B)^{\omega}$ is compatible with $s$ and there exists
$k\in\mathbb{N}$ and $i\in I$ such that $\mu(\rho_{\leq k})=m_{i}$ then
$\rho\in W$.

######  Proof 4.16.

Without loss of generality, we can suppose that $k$ is the smallest integer
such that $\mu(\rho_{\leq k})\notin\cup_{j\in J}T_{j}$. We want to prove there
exists a history $h$ such that $W_{h}\subseteq W_{\rho_{\leq k}}$ and $s_{i}$
is winning from $h$, as this will yield the desired result. Our candidate for
$h$ is $\mu(\rho_{\leq k-1})(a,b)$ where $(a,b)=\rho_{k}$.

  * •

By Lemma 4.13 we know that $W_{\mu(\rho_{\leq k-1})}\subseteq W_{\rho_{\leq
k-1}}$, and thus $W_{\mu(\rho_{\leq k-1})(a,b)}\subseteq W_{\rho_{\leq k-1}}$.

  * •

Furthermore, we know per the definition of $s$ that $s_{i}$ is winning from
$\mu(\rho_{\leq k-1}(a,b))$ since $\mu(\rho_{\leq k})=m_{i}$.

Finally, a trivial induction shows that for any $\beta\in B^{\omega}$ we have
$\text{out}(\rho_{\leq k},s,\beta)=\text{out}(\rho_{\leq k},s_{i},\beta)$, and
since $s_{i}$ is winning from $\rho_{\leq k}$ we have $\rho\in W$.

Finally, with the help of Lemma 4.13 and Lemma 4.15, we can prove the
following, which concludes the proof of Theorem 4.9.

######  Lemma 4.17.

$s$ is winning from $\varepsilon$.

######  Proof 4.18.

Let us consider $\rho\in(A\times B)^{\omega}$ compatible with $s$. We want to
show that $\rho\in W$. If there exists $k\in\mathbb{N}$ such that
$\mu(\rho_{\leq k})\in\cup_{i\in I}M_{i}$ then Lemma 4.15 suffices to
conclude. Suppose then that for all $k\in\mathbb{N}$ we have $\mu(\rho_{\leq
k})\in\cup_{j\in J}T_{j}$. If $\rho\in C$ then obviously we have $\rho\in W$,
so let us suppose that there exists $n_{0}\in\mathbb{N}$ such that $\rho_{\leq
n_{0}}\notin\text{Pref}(C)$. Due to the construction of $s$, there exists some
$n_{1}\geq n_{0}$ and some $j\in J$ such that $\mu(\rho_{\leq
n_{1}})=\overline{h}_{j}$. By Lemma 4.13 we then have $W_{\mu(\rho_{\leq
n_{1}})}\subseteq W_{\rho_{\leq n_{1}}}$. Notice that we also have $\rho_{\leq
n_{1}}\notin\text{Pref}(C)$. Finally, let $l$ be the prefix of $\rho_{>n_{1}}$
of length $0pt(\overline{h}_{j})$. By construction and since we do not have
$\mu(\rho_{\leq k})\in\cup_{i\in I}M_{i}$ for any $k$, for all $k\leq
0pt(\overline{h}_{j})$ we have $\mu(\rho_{\leq
n_{1}+k})=\overline{h}_{j}l_{\leq k}\in\text{Pref}(C)$, and hence by
application of Lemma 4.11 we can conclude that $\rho\in O$ and thus $\rho\in
W$.

pt$\varepsilon$$(0,0)$$(0,1)$$(0,0)(0,1)$$(0,1)(0,0)$$(0,1)(0,1)$$(0,1)$$m$pt$(0,0)$pt$(0,1)$pt$(0,1)$pt$(0,0)$pt$(0,1)$$(0,0)$pt$\\{0\\}\times
B$$\\{0\\}\times B$$\\{0\\}\times B$$\\{0\\}\times B$pt$\\{1\\}\times B$
Figure 3: The finite-memory strategy for the game represented in Figure 1.

We illustrate our method on the game described in Figure 1:

######  Example 4.19.

Consider once again the game represented in 1. We recall here that we have
$A=B=\\{0,1\\}$ and $W=(0,0)^{*}(0,1)(\\{0\\}\times
B)^{\omega}+(0,0)^{2}(0,0)^{*}(\\{1\\}\times B+A\times\\{1\\})(A\times
B)^{\omega}$. We let $C=(0,1)(\\{0\\}\times
B)^{\omega}+(0,0)(0,1)(\\{0\\}\times B)^{\omega}$ and
$O=(0,0)^{2}(0,0)^{*}[(0,1)+(1,0)+(1,1)](A\times B)^{\omega}$, and we have
$W=C\cup O$. One can check easily that $C$ is a closed set and $O$ is an open
set generated by the family of histories
$\mathcal{F}=(0,0)^{2}(0,0)^{*}[(0,1)+(1,0)+(1,1)]$.

The histories in $\text{Pref}(C)$ are of three different types: $\varepsilon$,
whose induced winning set is $W$, $(0,0)$, whose induced winning set is
included in $W$, and all the other histories in $\text{Pref}(C)$, whose
induced winning set is $(\\{0\\}\times B)^{\omega}$. We choose two histories
in $\text{Pref}(C)$ that provide under-approximations for the open sets
induced by all elements of $\text{Pref}(C)$: $\varepsilon$ and $(0,1)$. Except
for histories which already have a prefix in $\mathcal{F}$, no history out of
$\text{Pref}(C)$ induces a winning set that includes $W_{(0,1)}$, which means
that $0pt((0,1))=0$. However $W_{\varepsilon}$ is included in all winning sets
induced by the histories in $(0,0)^{2}(0,0)^{*}$. Since
$(0,0)^{2}(0,0)^{*}(0,0)(0,1)\subseteq\mathcal{F}$, we have
$0pt(\varepsilon)=2$. The only continuation of length $2$ from $\varepsilon$
that goes out of $\text{Pref}(C)$ is $(0,0)(0,0)$, and the finite-memory
strategy we chose that reaches $O$ from $(0,0)(0,0)$ is one where Player $1$
always plays action $1$.

###  4.5 Proof for sets in $\Lambda_{\theta}$

We study now the case where $W\in\Lambda_{\theta}$ for an ordinal $\theta>1$
and Theorem 4.1 is true for all winning sets belonging to $\Lambda_{\eta}$ or
$K_{\eta}$ for all $\eta<\theta$. As always, we suppose that Player $1$ has a
winning strategy from $\varepsilon$ and we want to show she has a finite-
memory winning strategy.

As $W\in\Lambda_{\theta}$, there exists a family of sets $(S_{i})_{i\in I}$
such that $W=\Cup_{i\in I}S_{i}$ and for each $i$ there exists
$\theta_{i}<\theta$ such that $S_{i}\in\Lambda_{\theta_{i}}$ or $S_{i}\in
K_{\theta_{i}}$. Furthermore, there exists a disjoint family of open sets
$(O_{i})_{i\in I}$ such that for each $i\in I$ we have $S_{i}\subseteq O_{i}$.
Finally, for each $i$ the set $O_{i}$ is generated by a family of histories
$\mathcal{F}_{i}$.

Consider then a winning strategy $s$ for Player $1$ and let $T_{s}$ be its
induced strategic tree. Consider the tree
$T_{s}^{\prime}=T_{s}\setminus\\{h\in\mathcal{H}\mid\exists i\in I,\exists
f\in\mathcal{F}_{i},f\sqsubset h\\}$. Since $s$ is winning, all infinite
branches of $T_{s}$ belongs to $O_{i}$ for some $i$, and hence
$T_{s}^{\prime}$ does not have any infinite branch. By Kőnig’s lemma, this
means that $T_{s}^{\prime}$ is a finite tree. Let us consider the set
$\mathcal{L}$ of maximal elements (with regards to the prefix relation) in
$T_{s}^{\prime}$. By construction all histories $h$ in $\mathcal{L}$ are such
that there exists a unique (because the $O_{i}$’s are disjoint from one
another) $i\in I$ such that $h\in\mathcal{F}_{i}$. This means that the winning
plays which have $h$ as a prefix are included in $S_{i}$ and hence for
$h\in\mathcal{L}$ we have $W_{h}=h^{-1}(S_{i}\cap\textnormal{cyl}(h))$. Thus
by Lemma A.17 (which states that both $\Lambda_{\theta_{i}}$ and
$K_{\theta_{i}}$ are closed under intersection with a cylinder, see appendix
A.2) we know that $W_{h}\in\Lambda_{\theta_{i}}$ or $W_{h}\in K_{\theta_{i}}$
(depending on whether $S_{i}$ belongs to $\Lambda_{\theta_{i}}$ or
$K_{\theta_{i}}$). Moreover, since all histories in $\mathcal{L}$ belong to
$T_{s}$ and $s$ is winning we know that $\mathcal{L}\subseteq\Gamma$. This
means that we have all the hypotheses we need to apply the induction
hypothesis to any $l\in\mathcal{L}$ (namely, $l\in\Gamma$ and
$W_{l}\in\Lambda_{\eta}$ or $W_{l}\in K_{\eta}$ for some $\eta<\theta$), and
hence for all $l\in\mathcal{L}$ there exists a finite-memory strategy
$s_{l}=(M_{l},\sigma_{l},\mu_{l},m_{l})$ that wins from $l$ (up to renaming,
we suppose that the $M_{l}$’s are disjoint from one another and from $T_{s}$).

We will build a finite-memory strategy $s_{f}=(M,\sigma,\mu,m_{0})$ for Player
$1$ in the following way:

  * •

$M=T_{s}^{\prime}\cup\uplus_{l\in\mathcal{L}}M_{l}$;

  * •

$\sigma(m)=s(m)$ for $m\in T_{s}^{\prime}$, and $\sigma(m)=\sigma_{l}(m)$ for
$m\in M_{l}$;

  * •

$\mu(m,(a,b))=m(a,b)$ if $m\in T_{s}^{\prime}$ and $m(a,b)\neq l$ for all
$l\in\mathcal{L}$ (where $a=\sigma(m)$);

  * •

$\mu(m,(a,b))=m_{l}$ if $m\in T_{s}^{\prime}$ and $m(a,b)=l$ for some
$l\in\mathcal{L}$ (where $a=\sigma(m)$);

  * •

$\mu(m,(a,b))=\mu_{l}(m(a,b))$ if $m\in M_{l}$;

  * •

$m_{0}=\varepsilon$ if $\varepsilon\neq l$ for all $l\in\mathcal{L}$, and
$m_{0}=m_{l}$ if there exists $l\in\mathcal{L}$ such that $l=\varepsilon$.

The idea behind this construction is the following: we follow the winning
strategy $s$ until we reach some $l\in\mathcal{L}$, from which we know the
strategy $s_{l}$ is winning. It remains only to emulate $s_{l}$ from this
point onwards to guarantee the win. The formal proof that this strategy is
winning can be found in Appendix B.2.

###  4.6 Proof for sets in $K_{\theta}$

As this induction step is very technical, we do not present it here, but
provide a detailed proof in appendix B.3.

##  5 Tightness of the result

We explore the tightness of our result. In particular, the winning sets of the
two games in Example 5.1 below are in $\Pi_{2}^{0}$ and $\Sigma_{2}^{0}$,
respectively, just above $\Delta^{0}_{2}$ in the Borel hierarchy; the two
games satisfy the well partial order assumption and Player 1 has winning
strategies, but no finite-memory winning strategies. Note that the example in
$\Pi_{2}^{0}$ is harder to define and deal with than the one in
$\Sigma_{2}^{0}$. (See details in appendix C.)

######  Example 5.1.

For the counter-example in $\Pi_{2}^{0}$, let $A$ be a finite set of at least
two elements and $w$ a disjunctive sequence on $A\times\\{0\\}$. We define the
labeling function $l:(A\times\\{0\\})^{*}\to\\{0,1\\}$ in the following way:
$l(h)=1$ if and only if there exists $h_{0}$ and $h^{\prime}$ such that
$h=h_{0}h^{\prime}$ and $h^{\prime}$ is the longest factor of $h$ that is also
a prefix of $w$. Let then $W$ be the set defined by $\rho\in W$ if and only if
infinitely many prefixes $h$ of $\rho$ are such that $l(h)=1$ and consider the
game $(A,\\{0\\},W)$.

For the counter-example in $\Sigma_{2}^{0}$, let $A$ be a finite set of at
least two elements and $w$ an irregular sequence in $(A\times\\{0\\})^{*}$.
Let $W=\\{\rho\in(A\times\\{0\\})^{\omega}\mid\exists
h\in(A\times\\{0\\})^{*},\rho=h\rho_{0}\text{ where }\rho_{0}\text{ is a
suffix of }w\\}$. $W$ is the set of sequences which have a suffix in common
with $w$. Consider then the game $(A,\\{0\\},W)$.

We also considered a relaxation of the well partial order assumption, but
found a counter-example with a closed winning set. (See details in appendix
C.)

Finally, we studied the statement of our result where “Player 1” is
syntactically replaced with “Player 2”, but the $W_{h}$ still pertain to
Player 1. The variant holds for closed sets, but we found a counter-example
just above in the Hausdorff difference hierarchy.

##  6 Conclusion

To conclude, we have proven the existence of finite-memory winning strategies
under certain conditions on the winning set for Player $1$. These conditions
are met for well studied games such as energy games [9] or games where the
winning condition is a Boolean combination of reachability and safety
objectives, which makes our result a generalization of known results on the
topic. This result relies on contributions to the field of descriptive set
theory, in particular on representation of sets in $\Delta_{2}^{0}$.

We have also studied the tightness of our result. The results we currently
have in this direction encourage us to think that our hypotheses are tight and
that weakening them is no easy task. In the future, we want to extend these
tightness results by exploring other possible hypotheses, as well as study
infinitely branching games, when the action sets of the players are not
finite.

## References

  * [1] Benjamin Aminof and Sasha Rubin.  First-cycle games.  Inf. Comput., 254:195–216, 2017.  URL: https://doi.org/10.1016/j.ic.2016.10.008, doi:10.1016/j.ic.2016.10.008.
  * [2] Patricia Bouyer, Stéphane Le Roux, Youssouf Oualhadj, Mickael Randour, and Pierre Vandenhove.  Games where you can play optimally with arena-independent finite memory.  In 31st International Conference on Concurrency Theory, CONCUR 2020, September 1-4, 2020, Vienna, Austria (Virtual Conference), pages 24:1–24:22, 2020.  URL: https://doi.org/10.4230/LIPIcs.CONCUR.2020.24, doi:10.4230/LIPIcs.CONCUR.2020.24.
  * [3] John Fearnley and Martin Zimmermann.  Playing muller games in a hurry.  Int. J. Found. Comput. Sci., 23(3):649–668, 2012.  URL: https://doi.org/10.1142/S0129054112400321, doi:10.1142/S0129054112400321.
  * [4] Alexander Kechris.  Classical Descriptive Set Theory.  1995\.  doi:10.1007/978-1-4612-4190-4.
  * [5] Dénes Kőnig.  Über eine schlussweise aus dem endlichen ins unendliche (in german).  Acta Sci. Math. (Szeged), 1927.
  * [6] Stéphane Le Roux, Arno Pauly, and Mickael Randour.  Extending finite-memory determinacy by boolean combination of winning conditions.  In 38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2018, December 11-13, 2018, Ahmedabad, India, pages 38:1–38:20, 2018.  URL: https://doi.org/10.4230/LIPIcs.FSTTCS.2018.38, doi:10.4230/LIPIcs.FSTTCS.2018.38.
  * [7] Robert McNaughton.  Playing infinite games in finite time.  In A Half-Century of Automata Theory: Celebration and Inspiration, pages 73–91. 2000.
  * [8] Stéphane Le Roux.  Infinite subgame perfect equilibrium in the hausdorff difference hierarchy.  In Mohammad Taghi Hajiaghayi and Mohammad Reza Mousavi, editors, Topics in Theoretical Computer Science - The First IFIP WG 1.8 International Conference, TTCS 2015, Tehran, Iran, August 26-28, 2015, Revised Selected Papers, volume 9541 of Lecture Notes in Computer Science, pages 147–163. Springer, 2015.  URL: https://doi.org/10.1007/978-3-319-28678-5_11, doi:10.1007/978-3-319-28678-5\\_11.
  * [9] Yaron Velner, Krishnendu Chatterjee, Laurent Doyen, Thomas A. Henzinger, Alexander Rabinovich, and Jean-François Raskin.  The complexity of multi-mean-payoff and multi-energy games.  CoRR, abs/1209.3234, 2012.  URL: http://arxiv.org/abs/1209.3234, arXiv:1209.3234.

##  Appendix A Descriptive set theory

###  A.1 The Hausdorff difference hierarchy

In this section, we provide properties on the Hausdorff difference hierarchy.
We begin by showing that it is indeed an increasing hierarchy:

######  Lemma A.1.

For all ordinals $\theta_{1}$, $\theta_{2}$ such that $\theta_{1}<\theta_{2}$,
we have $\mathcal{D}_{\theta_{1}}\subseteq\mathcal{D}_{\theta_{2}}$.

######  Proof A.2.

We prove that for all ordinals $\theta$ we have
$\mathcal{D}_{\theta}\subseteq\mathcal{D}_{\theta+1}$, which ensures the
result by a straightforward induction.

Consider an ordinal $\theta$ and let $S\in\mathcal{D}_{\theta}$. Consider an
increasing family of open sets $(O_{\eta})_{\eta<\theta}$ such that
$S=D_{\theta}((O_{\eta})_{\eta<\theta})$, that is, $s\in S$ if and only if
there exists $\eta$ such that $s\in O_{\eta}$ and the least such $\eta$ is of
parity opposite to that of $\theta$. Let then $(P_{\eta})_{\eta<\theta+1}$ be
the increasing family of open sets defined by the following:

  * •

$P_{0}=\emptyset$;

  * •

for all successor ordinals $\eta$, $P_{\eta}=O_{\eta-1}$;

  * •

for all non-zero limit ordinals $\eta$, $P_{\eta}=\cup_{\zeta<\eta}O_{\zeta}$.

We will show that $S=D_{\theta+1}((P_{\eta})_{\eta<\zeta})$. Consider $s\in
C$. For all ordinals $\eta$, we have $s\in O_{\eta}\Leftrightarrow s\in
P_{\eta+1}$, which means that $s$ belongs to $S$ if and only if there exists
$\eta<\theta$ such that it belongs to $P_{\eta}$ and the least such $\eta$ is
of parity opposite to $\theta+1$, that is $s$ belongs to $S$ if and only if it
belongs to $\mathcal{D}_{\theta+1}((P_{\eta})_{\eta<\theta+1})$.

######  Lemma A.3.

For all ordinals $\theta$, $\mathcal{D}_{\theta}$ is closed under intersection
with an open set.

######  Proof A.4.

Let $\theta$ be an ordinal and $S\in\mathcal{D}_{\theta}$. There exists a
family of open sets $(O_{\eta})_{\eta<\theta}$ such that
$S=D_{\theta}((O_{\eta})_{\eta<\theta})$. Let $O$ be an open set. We will
prove that $S\cap O=D_{\theta}((O_{\eta}\cap O)_{\eta<\theta})$.

Let $\rho\in S\cap O$. Obviously for all $\eta<\theta$ such that $\rho\in
O_{\eta}$ we have $\rho\in O_{\eta}\cap O$. Hence $\rho\in
D_{\theta}((O_{\eta})_{\eta<\theta})$.

Conversely, let $\rho\in D_{\theta}((O_{\eta}\cap O)_{\eta<\theta})$. There
exists $\eta<\theta$ such that $\rho\in O_{\eta}\cap O$, and hence obviously
$\rho\in O$. Then for all $\eta<\theta$ we have $\rho\in
O_{\eta}\Leftrightarrow\rho\in O_{\eta}\cap O$, and hence $\rho\in
S\Leftrightarrow\rho\in
D_{\theta}((O_{\eta})_{\eta<\theta})\Leftrightarrow\rho\in
D_{\theta}((O_{\eta}\cap O)_{\eta<\theta})$, which means that $\rho\in S$.

######  Lemma A.5.

For all ordinals $\theta$, if $S\in\mathcal{D}_{\theta}$ then
$\overline{S}\in\mathcal{D}_{\theta+1}$.

######  Proof A.6.

Let $\theta$ be an ordinal and $S\in\mathcal{D}_{\theta}$. There exists a
family of open sets $(O_{\eta})_{\eta<\theta}$ such that
$S=D_{\theta}((O_{\eta})_{\eta<\theta})$. Let $O_{\theta}=(A\times
B)^{\omega}$. Then $\overline{S}=D_{\theta+1}((O_{\eta})_{\eta<\theta+1})$.

######  Lemma A.7.

For all successor ordinals $\theta$, a set $S$ belongs to
$\mathcal{D}_{\theta}$ if and only if there exists an open set $O$ and a set
$S^{\prime}$ in $\mathcal{D}_{\theta-1}$ such that $S=O\setminus S^{\prime}$.

######  Proof A.8.

Let $\theta$ be a successor ordinal, $S^{\prime}\in\mathcal{D}_{\theta-1}$ and
$O$ an open set. By Lemma A.5, $\overline{S^{\prime}}\in\mathcal{D}_{\theta}$,
and we have $O\setminus S^{\prime}=O\cap\overline{S^{\prime}}$ which by Lemma
A.3 means that $O\setminus S^{\prime}\in\mathcal{D}_{\theta}$.

Conversely, let $S\in\mathcal{D}_{\theta}$. There exists an increasing family
of open sets $(O_{\eta})_{\eta<\theta}$ such that
$S=D_{\theta}((O_{\eta})_{\eta<\theta})$. Hence a play $\rho$ belongs to $S$
if and only if it belongs to $O_{\theta-1}$ and the least $\eta$ such that
$\rho\in O_{\eta}$ is of parity opposite to $\theta$, i.e. is not of parity
opposite to $\theta-1$. That is, a play $\rho$ belongs to $S$ if and only if
it belongs to $O_{\theta-1}\setminus
D_{\theta-1}((O_{\eta})_{\eta<\theta-1})$, hence $S=O_{\theta-1}\setminus
D_{\theta-1}((O_{\eta})_{\eta<\theta-1})$.

###  A.2 The fine Hausdorff hierarchy

In this section we provide properties on the fine Hausdorff hierarchy that
lead to different ways of defining the sets in the hierarchy. We begin once
again by showing it is an increasing hierarchy:

######  Lemma A.9.

For $\theta_{0}<\theta_{1}$, we have $\Lambda_{\theta_{0}}\cup
K_{\theta_{0}}\subseteq\Lambda_{\theta_{1}}$ and $\Lambda_{\theta_{0}}\cup
K_{\theta_{0}}\subseteq K_{\theta_{1}}$.

######  Proof A.10.

We have $\Lambda_{\theta_{0}}\cup K_{\theta_{0}}\subseteq\Lambda_{\theta_{1}}$
from the definition of $\Lambda_{\theta_{1}}$, as any set can be written as
the open union of itself only. Moreover, since sets in $\Lambda_{\theta_{0}}$
and $K_{\theta_{0}}$ are the complements of each other, and since
$K_{\theta_{1}}$ contains the sets whose complement is in
$\Lambda_{\theta_{1}}$ we also have $\Lambda_{\theta_{0}}\cup
K_{\theta_{0}}\subseteq K_{\theta_{1}}$.

This yields two corollaries that provide other ways tosee the sets in
$\Lambda_{\theta}$. The first one states that sets in $\Lambda_{\theta}$ can
be written as open unions of sets in $K_{\theta}$, while the second one goes
further and states that $\Lambda_{\theta}$ contains exactly the sets that can
be written as open unions of sets that belong to $\cup_{\eta<\theta}K_{\eta}$.

######  Corollary A.11.

For every ordinal $\theta>0$, any set $S$ in $\Lambda_{\theta}$ can be written
as the open union of sets in $K_{\theta}$.

######  Proof A.12.

If $S$ belongs to $\Lambda_{1}$ then $S$ is an open set associated with a
generating family $\mathcal{F}$. Without loss of generality, we can suppose
that elements of $\mathcal{F}$ are incomparable with regards to the prefix
relation, and we then have $S=\Cup_{f\in\mathcal{F}}\textnormal{cyl}(f)$, and
for all $f$ $\textnormal{cyl}(f)$ is a closed set and hence belongs to
$K_{0}$.

Alternatively consider $S$ in $\Lambda_{\theta}$ with $\theta>1$: there exists
a family of sets $(S_{i})_{i\in I}$ such that for each $S_{i}$ there exists an
ordinal $\theta_{i}<\theta$ such that $S_{i}\in\Lambda_{\theta_{i}}$ or
$S_{i}\in K_{\theta_{i}}$ and $S=\Cup_{i\in I}S_{i}$. By Lemma A.9 we have
that each $S_{i}$ belongs to $K_{\theta}$, thus yielding the result.

######  Corollary A.13.

For all ordinals $\theta>1$, a set $S$ belongs to $\Lambda_{\theta}$ if and
only if there exists a family of sets $(S_{i})_{i\in I}$ such that
$S=\Cup_{i\in I}S_{i}$ such that for each $i$ there exists an ordinal
$\theta_{i}<\theta$ such that $S_{i}\in K_{\theta_{i}}$.

######  Proof A.14.

Consider $\theta>1$ and a set $S$ in $\Lambda_{\theta}$. There exists a family
of sets $(S_{i})_{i\in I}$ such that $S=\Cup_{i\in I}S_{i}$ such that for each
$i$ there exists an ordinal $\theta_{i}$ such that
$S_{i}\in\Lambda_{\theta_{i}}$ or $S_{i}\in K_{\theta_{i}}$. Let us write
$I=I_{\Lambda}\uplus I_{K}$ where $i\in I_{\Lambda}$ if and only if $S_{i}$
belongs to $\Lambda_{\theta_{i}}$ and not $K_{\theta_{i}}$, and $i\in I_{K}$
if and only if $S_{i}\in K_{\theta_{i}}$. For all $i\in I_{\Lambda}$, by
application of Corollary A.11 there exists a family of sets $(S_{i}^{j})_{j\in
J_{i}}$ such that each $S_{i}^{j}$ belongs to $K_{\theta_{i}}$ and
$S_{i}=\Cup_{j\in J_{i}}S_{i}^{j}$. We then have $S=\Cup_{i\in
I_{\Lambda}}\Cup_{j\in J_{i}}S_{i}^{j}\Cup\Cup_{i\in I_{K}}S_{i}$, which
proves the result.

######  Lemma A.15.

For all ordinals $\theta$, $\Lambda_{\theta}$ is closed under open union.

######  Proof A.16.

If $\theta=1$ then the result is straightforward because open sets are closed
under union.

Consider an ordinal $\theta>1$ and a family $(S_{i})_{i\in I}$ of sets in
$\Lambda_{\theta}$ such that there exists a family of disjoint open sets
$(O_{i})_{i\in I}$ such that for all $i$ we have $S_{i}\subseteq O_{i}$. For
each $i$ there exists a family of sets $(S_{j}^{i})_{j\in J_{i}}$ such that
$S_{i}=\Cup_{j\in J_{i}}S_{j}^{i}$. and for all $j\in J_{i}$ there exists
$\theta_{j}<\theta$ such that $S_{j}^{i}\in\Lambda_{\theta_{j}}$ or
$S_{j}^{i}\in K_{\theta_{j}}$ (up to renaming, we suppose that all the
$J_{i}$’s are disjoint), and such that there exists a disjoint family of open
sets $(O^{i}_{j})_{j\in J_{i}}$ such that for all $j\in J_{i}$ we have
$S_{j}^{i}\subseteq O_{j}^{i}$. We then have $S=\cup_{i\in I,j\in
J_{i}}S_{j}^{i}$ where for each $i$ and for each $j\in J_{i}$ we have
$S^{i}_{j}\in\Lambda_{\theta_{j}}$ or $S^{i}_{j}\in K_{\theta_{j}}$ and
$S^{i}_{j}\subseteq O^{i}_{j}\cap O_{i}$, which means that $S$ belongs to
$\Lambda_{\theta}$.

######  Lemma A.17.

For all ordinals $\theta$, both $\Lambda_{\theta}$ and $K_{\theta}$ are closed
under intersection with a cylinder: for all $S$ in $\Lambda_{\theta}$ (resp.
$K_{\theta}$), and for all $h\in\mathcal{H}$ we have $\textnormal{cyl}(h)\cap
S\in\Lambda_{\theta}$ (resp. $K_{\theta}$).

######  Proof A.18.

We prove the result by induction. First, since open sets are closed under
finite intersection, we obviously have the result for $\Lambda_{1}$. Consider
now an ordinal $\theta>1$, and suppose that the result is true for all
$\theta^{\prime}<\theta$. Consider some $S$ in $\Lambda_{\theta}$ and some
$h\in\mathcal{H}$. There exists a family of sets $(S_{i})_{i\in I}$ such that
$S=\Cup_{i\in I}S_{i}$ and for all $i\in I$ there exists $\theta_{i}<\theta$
such that $S_{i}\in\Lambda_{\theta_{i}}$ or $S_{i}\in K_{\theta_{i}}$. We then
have $\textnormal{cyl}(h)\cap S=\Cup_{i\in I}\textnormal{cyl}(h)\cap S_{i}$,
and by the induction hypothesis we can conclude $\textnormal{cyl}(h)\cap
S\in\Lambda_{\theta}$. Consider now some $S$ in $K_{\theta}$ and some
$h\in\mathcal{H}$. We have $\overline{\textnormal{cyl}(h)\cap
S}=\overline{\textnormal{cyl}(h)}\cup\textnormal{cyl}(h)\cap\overline{S}$.
Since $\overline{\textnormal{cyl}(h)}$ is an open set and hence belong to
$\Lambda_{1}\subseteq\Lambda_{\theta}$, and
$\textnormal{cyl}(h)\cap\overline{S}$ belongs to $\Lambda_{\theta}$ by what we
have just shown, and both sets are contained in disjoint open sets
$\overline{\textnormal{cyl}(h)}$ and $\textnormal{cyl}{h}$, by Lemma A.15 we
can conclude that $\overline{\textnormal{cyl}(h)\cap S}\in\Lambda_{\theta}$,
and hence $\textnormal{cyl}(h)\cap S\in K_{\theta}$, which concludes the
induction step.

######  Corollary A.19.

For all ordinals $\theta$, $\Lambda_{\theta}$ is closed under intersection
with an open set: for all $S$ in $\Lambda_{\theta}$ and all open sets $O$ we
have $O\cap S\in\Lambda_{\theta}$.

######  Proof A.20.

Consider a set $S$ in $\Lambda_{\theta}$ and an open set $O$ associated with a
generating family of histories $\mathcal{F}$. Without loss of generality we
can suppose that no two distinct elements in $\mathcal{F}$ are comparable with
regards to the prefix relation. Notice then that $O\cap
S=\Cup_{f\in\mathcal{F}}\textnormal{cyl}(f)\cap S$. By Lemma A.17, for all $f$
we have that $\textnormal{cyl}(f)\cap S$ belongs to $\Lambda_{\theta}$, which
means that by Lemma A.15 $O\cap S$ belongs to $\Lambda_{\theta}$ as the open
union of sets in $\Lambda_{\theta}$.

######  Lemma A.21.

For any successor ordinal $\theta>1$, a set $S$ belongs to $K_{\theta}$ if and
only if there exists a closed set $C$ and a set $L$ belonging to
$\Lambda_{\theta-1}$ such that $S=C\cup L$.

######  Proof A.22.

Suppose that $S$ belongs to $K_{\theta}$. Then there exists a family of sets
$(S_{i})_{i\in I}$ such that each $S_{i}$ belongs to either
$\Lambda_{\theta-1}$ or $K_{\theta-1}$ and $\overline{S}=\Cup_{i\in I}S_{i}$.
Thanks to Corollary A.13, we can suppose that for all $i$ $S_{i}$ belongs to
$K_{\theta-1}$. Consider a disjoint family of open sets $(O_{i})_{i\in I}$,
such that for all $i\in I$ we have $S_{i}\subseteq O_{i}$. Let $O=\cup_{i\in
I}O_{i}$ (notice $O$ is an open set) and $C$ be the complement of $O$. We have
$S=C\cup\Cup_{i\in I}(O_{i}\setminus S_{i})=C\cup\Cup_{i\in
I}(O_{i}\cap\overline{S_{i}})$. For all $i$ $\overline{S_{i}}$ belongs to
$\Lambda_{\theta-1}$, which means that by Corollary A.19 for all
$f\in\mathcal{F}$ $\textnormal{cyl}(f)\cap\overline{S_{i}}$ belongs to
$\Lambda_{\theta-1}$ as well. Finally, by Lemma A.15 we have that $\Cup_{i\in
I}O_{i}\cap\overline{S_{i}}$ belongs to $\Lambda_{\theta-1}$ as the open union
of sets in $\Lambda_{\theta-1}$.

Now suppose that $S$ is such that there exists a closed set $C$ and a set $L$
belonging to $\Lambda_{\theta-1}$ such that $S=C\cup L$. We have
$\overline{S}=\overline{C}\cap\overline{L}$, where $\overline{C}$ is an open
set and $\overline{L}$ belongs to $K_{\theta-1}$ and hence to
$\Lambda_{\theta}$. By application of Corollary A.19, $\overline{S}$ belongs
to $\Lambda_{\theta}$ and hence $S$ belongs to $K_{\theta}$.

######  Lemma A.23.

For any ordinal $\theta>0$, if a set $S$ belongs to $K_{\theta}$ then there
exists a closed set $C$ and a set $L$ belonging to $\Lambda_{\theta}$ such
that $S=C\cup L$.

######  Proof A.24.

Consider an ordinal $\theta>0$ and let $S\in K_{\theta}$. We have
$\overline{S}\in\Lambda_{\theta}$, which by Corollary A.13 means that there
exists a family of sets $(S_{i})_{i\in I}$ such that $\overline{S}=\Cup S_{i}$
and for all $i$ there exists $\theta_{i}<\theta$ such that $S_{i}\in
K_{\theta_{i}}$. Let $(O_{i})_{i\in I}$ be a family of disjoint open sets such
that for all $i$ we have $S_{i}\subseteq O_{i}$, $O=\cup_{i\in I}O_{i}$ and
$C$ be the complement of $O$ (notice $C$ is then a closed set). We have
$S=C\cup\Cup_{i\in I}(O_{i}\cap\overline{S_{i}})$. By Lemma A.19 we know that
for each $i$ we have $O_{i}\cap\overline{S_{i}}\in\Lambda_{\theta_{i}}$, which
means that $\Cup_{i\in I}(O_{i}\cap\overline{S_{i}}$ belongs to
$\Lambda_{\theta}$ which concludes the proof.

###  A.3 Equivalence between the Hausdorff difference hierarchy and the fine
Hausdorff hierarchy

This section is devoted to proving the Hausdorff difference hierarchy and fine
Hausdorff hierarchy actually coincide. We have two preliminary lemmas: one
states that the collections $\mathcal{D}_{\theta}$ are closed under open
union, and the other states that the collections $\mathcal{D}_{\theta}$
contain exactly the sets that can be written as open unions of sets lower in
the hierarchy, similarly to how $\Lambda_{\theta}$ is defined.

######  Lemma A.25.

For all ordinals $\theta$, $\mathcal{D}_{\theta}$ is closed under open union.

######  Proof A.26.

Let $\theta$ be an ordinal and let $(S_{i})_{i\in I}$ be a family of sets in
$\mathcal{D}_{\theta}$. There exists a family of open sets $(O_{i})_{i\in I}$
such that for each $i$ $S_{i}\subseteq O_{i}$ and for each $i$ there exists a
family of open sets $(P^{i}_{\eta})_{\eta<\theta}$ such that
$S_{i}=D_{\theta}((P^{i}_{\eta})_{\eta<\theta})$. Let $S=\Cup_{i\in I}S_{i}$.
For all $\eta<\theta$, let $P_{\eta}=\Cup_{i\in I}O_{i}\cap P^{i}_{\eta}$
(notice $(P_{\eta})_{\eta<\theta}$ is an increasing family of open sets). We
want to show that $S=D_{\theta}((P_{\eta})_{\eta<\theta})$.

First let us prove that $S\subseteq D_{\theta}((P_{\eta})_{\eta<\theta})$. Let
$\rho\in S$. There exists $i\in I$ such that $S\in S_{i}$. We know $\rho\in
O_{i}$, which means that for all $\eta$ such that $\rho\in P^{i}_{\eta}$ we
have $\rho\in O_{i}\cap P^{i}_{\eta}$. Moreover, we know that for all $j\neq
i$ we have $\rho\notin O_{j}$. As a consequence, we have
$\min\\{\eta|\rho\in\Cup_{j\in I}O_{j}\cap P^{j}_{\eta}\\}=\min\\{\eta|\rho\in
P^{i}_{\eta}\\}$, and hence $\rho\in D_{\theta}((P_{\eta})_{\eta<\theta})$.

Now we want to show that $D_{\theta}((P_{\eta})_{\eta<\theta})\subseteq S$.
Let $\rho\in D_{\theta}((P_{\eta})_{\eta<\theta})$. Obviously there exists a
unique $i\in I$ such that $\rho\in O_{i}$ (there exists at least one for all
$j\neq i$ $O_{j}$ is disjoint from $O_{i}$). We want to show that $\rho\in
S_{i}$. We have $\min\\{\eta|\rho\in P_{\eta}\\}=\min\\{\eta|\rho\in\Cup_{j\in
I}O_{j}\cap P^{j}_{\eta}\\}=\min\\{\eta|\rho\in O_{i}\cap
P^{i}_{\eta}\\}=\min\\{\eta|\rho\in P^{i}_{\eta}\\}$. Since $\rho\in S$, the
smallest $\eta$ such that $\rho\in P_{\eta}$ is of parity opposite to that of
$\theta$, and hence it is also the case for the smallest $\eta$ such that
$\rho\in P^{i}_{\eta}$, which means that $\rho\in S_{i}$ and thus $\rho\in S$.

######  Lemma A.27.

For all limit ordinals $\theta$, a set $S$ belongs to $\mathcal{D}_{\theta}$
if and only if it is the open union of sets in
$\cup_{\eta<\theta}\mathcal{D}_{\theta}$.

######  Proof A.28.

Consider a limit ordinal $\theta$ and a family of sets $(S_{i})_{i\in I}$ such
that for all $i\in I$ there exists $\theta_{i}<\theta$ such that
$S_{i}\in\mathcal{D}_{\theta_{i}}$, and such that there exists a family of
disjoint open sets $(O_{i})_{i\in I}$ such that for all $i\in I$ we have
$S_{i}\subseteq O_{i}$. Since by Lemma A.1 we have for all $i$
$\mathcal{D}_{\theta_{i}}\subseteq\mathcal{D}_{\theta_{i}+1}$ we can suppose
without loss of generailty that for all $i\in I$ $\theta_{i}$ is of the same
parity as $\theta$ (that is, even). Let $S=\Cup_{i\in I}S_{i}$. We want to
prove that $S\in\mathcal{D}_{\theta}$. For all $i\in I$, there exists an
increasing family of open sets $(O^{i}_{\eta})_{\eta<\theta_{i}}$ such that
$S_{i}=D_{\theta_{i}}((O^{i}_{\eta})_{\eta<\theta_{i}})$. For all
$\eta<\theta$, let $O_{\eta}=\cup_{i\in I,\eta^{\prime}\leq\eta}O_{i}\cap
O^{i}_{\eta^{\prime}}$. We will show that
$S=D_{\theta}((O_{\eta})_{\eta<\theta})$.

Indeed, consider $\rho\in S$ and let us prove $\rho\in
D_{\theta}((O_{\eta})_{\eta<\theta})$. There exists $i\in I$ such that
$\rho\in S_{i}$, which means that $\rho\in O_{i}$ and hence for all $j\neq i$
we have $\rho\notin O_{j}$. This means that for all $\eta<\theta$, $\rho\in
O_{\eta}$ if and only if $\eta<\theta_{i}$ and $\rho\in O^{i}_{\eta}$, and
thus the smallest $\eta$ such that $\rho\in O_{\eta}$ is also the smallest
$\eta$ such that $\rho\in O^{i}_{\eta}$, which ultimately means that $\rho\in
D_{\theta}((O_{\eta})_{\eta<\theta})$ since both $\theta$ and $\theta_{i}$ are
even.

Let us now consider $\rho\in D_{\theta}((O_{\eta})_{\eta<\theta})$ and let us
prove there exists some $i\in I$ such that $\rho\in S_{i}$. There exists
$\eta<\theta$ such that $\rho\in O_{\eta}$, and hence there exists $i\in I$
such that $\rho\in O_{i}$ and $\rho\in O^{i}_{\eta}$. Since for all $j\neq i$
the sets $O_{i}$ and $O_{j}$ are disjoint we know that for all $\eta<\theta$
$\rho\in O_{\eta}$ if and only if $\eta<\theta_{i}$ and $\rho\in
O^{i}_{\eta}$. This means that the smallest $\eta$ such that such that
$\rho\in O^{i}_{\eta}$ is also the smallest $\eta$ such that $\rho\in
O_{\eta}$, and thus $\rho\in S_{i}$ since both $\theta$ and $\theta_{i}$ are
even.

Conversely, let us consider some set $S\in\mathcal{D}_{\theta}$. There exists
an increasing family of open sets $(O_{\eta})_{\eta<\theta}$ such that
$S=D_{\theta}((O_{\eta})_{\eta<\theta})$. Let
$\mathcal{L}=\\{h\in\mathcal{H}\mid\exists\eta<\theta,\textnormal{cyl}(h)\subseteq
O_{\eta}\\}$ be the set of histories whose cylinder is included in some
$O_{\eta}$ for $\eta<\theta$. Let $\mathcal{F}$ be the set of histories which
belong to $\mathcal{L}$ and are minimal with regards to the prefix relation.
For $f\in\mathcal{F}$, let
$\theta_{f}=\min\\{\eta<\theta\mid\textnormal{cyl}(f)\subseteq O_{\eta}\\}$.
Finally, for $f\in\mathcal{F}$, if $\theta_{f}$ is even then let
$S_{f}=D_{\theta_{f}+2}((\textnormal{cyl}(f)\cap
O_{\eta})_{\eta<\theta_{f}+2})$, and if $\theta_{f}$ is odd then let
$S_{f}=D_{\theta_{f}+1}((\textnormal{cyl}(f)\cap
O_{\eta})_{\eta<\theta_{f}+1})$. Notice this means that for all
$f\in\mathcal{F}$, a play $\rho$ belongs to $S_{f}$ if and only if the
smallest $\eta$ such that $\rho\in\textnormal{cyl}(f)\cap O_{\eta}$ is smaller
than $\theta_{f}$ and is odd. We shall prove that
$S=\Cup_{f\in\mathcal{F}}S_{f}$ (notice we obviously have that for all
$f\in\mathcal{F}$ $S_{f}\subseteq\textnormal{cyl}(f)$, which ensures this is
indeed an open union as all histories in $\mathcal{F}$ are incomparable with
each other with regards to the prefix relation).

Consider $\rho\in S$ and let us show there exists $f\in\mathcal{F}$ such that
$\rho\in S_{f}$. There exists $\eta<\theta$ such that $\rho\in O_{\eta}$, and
hence there exists $f\in\mathcal{F}$ such that $f$ is a prefix of $\rho$. This
means in particular that $\rho\in\textnormal{cyl}(f)$, and as a consequence we
have that the smallest $\eta$ such that $\rho\in O_{\eta}$ is smaller than
$\theta_{f}$, and is also the smallest $\eta$ such that
$\rho\in\textnormal{cyl}(f)\cap O_{\eta}$. Since $\theta$ is even, this also
means that $\rho\in S_{f}$.

Now consider $f\in\mathcal{F}$, $\rho\in S_{f}$ and let us show $\rho\in S$.
Obviously $\rho\in\textnormal{cyl}(f)$, and the smallest $\eta$ such that
$\rho\in O_{\eta}$ is odd, which means that $\rho\in S$.

Finally, we can prove our main result about the two hierarchies, justifying
that the fine Hausdorff hierarchy is actually a refinement of the Hausdorff
difference hierarchy:

######  Theorem A.29 (Theorem 3.1).

For all ordinals $\theta$, we have $\mathcal{D}_{\theta}=\Lambda_{\theta}$.

######  Proof A.30.

We prove the result by induction on ordinals $\theta$. First, we obviously
have $\mathcal{D}_{1}=\Lambda_{1}$ as both are the collections of all the open
sets.

Now consider some ordinal $\theta$ such that for all $\eta<\theta$ we have
$\mathcal{D}_{\eta}=\Lambda_{\eta}$. We shall show prove that
$\mathcal{D}_{\theta}=\Lambda_{\theta}$.

If $\theta$ is a limit ordinal, then this is a straightforward consequence of
Lemma A.27 and the induction hypothesis.

Now suppose that $\theta$ is a successor ordinal.

  * •

Consider $S\in\Lambda_{\theta}$. By Corollary A.13, we know that there exists
a family of sets $(S_{i})_{i\in I}$ such that for all $i\in I$ we have
$S_{i}\in K_{\theta-1}$ and $S=\Cup_{i\in I}S_{i}$. By definition for all
$i\in I$ we have $\overline{S_{i}}\in\Lambda_{\theta-1}$ which means that
$\overline{S_{i}}\in\mathcal{D}_{\theta-1}$. By Lemma A.5 we then have that
for all $i\in I$, $S_{i}\in\mathcal{D}_{\theta}$, and finally by Lemma A.25 we
have $S\in\mathcal{D}_{\theta}$.

  * •

Consider now $S\in\mathcal{D}_{\theta}$. By Lemma A.7 there exists an open set
$O$ and a set $S^{\prime}$ in $\mathcal{D}_{\theta-1}$ such that $S=O\setminus
S^{\prime}=O\cap\overline{S^{\prime}}$. By the induction hypothesis we have
$S^{\prime}\in\Lambda_{\theta-1}$, which implies that
$\overline{S^{\prime}}\in K_{\theta-1}$ and thus
$\overline{S^{\prime}}\in\Lambda_{\theta}$. Finally, by Corollary A.19 we can
conclude that $S\in\Lambda_{\theta}$.

###  A.4 Equivalence of representations of $\Delta_{2}^{0}$

######  Theorem A.31 (Theorem 3.2).

Given a subset $S$ of $C^{\omega}$, the following propositions are equivalent:

  * $(1)$

$S\in\Delta_{2}^{0}$;

  * $(2)$

$S$ belongs to the Hausdorff difference hierarchy;

  * $(3)$

$S$ belongs to the fine Hausdorff hierarchy;

  * $(4)$

there exists an eventually constant labelling funcion $l$ such that $S=1_{l}$.

######  Proof A.32 (Proof of Theorem 3.2).

  * •

$(1)\Leftrightarrow(2)$ is the hausdorff-Kuratowski theorem, a proof of which
can be found in [4].

  * •

$(2)\Leftrightarrow(3)$ is a straightforward consequence of Theorem 3.1.

  * •

To prove $(3)\Rightarrow(4)$, we want to show that the collections of sets
$1_{l}$ where $l$ is an eventually constant labelling function contains the
open sets and is closed under both open union and complementation. First
notice that any open set $O$ with generating family $\mathcal{F}$ is equal to
$1_{l_{\mathcal{F}}}$ where $l_{\mathcal{F}}(w)=1$ if and only if $w$ has a
prefix in $\mathcal{F}$. Then, if $l$ is an eventually constant labelling
function, the function $\overline{l}$ defined by $\overline{l}(h)=1-l(h)$ is
also an eventually constant labelling function and we have
$\overline{1_{l}}=1_{\overline{l}}$. Finally, consider a countable family of
eventually labeling function $(l_{i})_{i\in I}$ and a family of disjoint open
sets $(O_{i})_{i\in I}$ associated with generating families of words
$(\mathcal{F}_{i})_{i\in I}$. Consider then the labelling function $l$ defined
by:

    * –

if there exists $i\in I$ and $f\in\mathcal{F}_{i}$ such that $f$ is a prefix
of $w$ then $l(w)=l_{i}(h)$;

    * –

else $l(w)=0$

Notice that since the $O_{i}$’s are disjoint from one another we cannot have
$f_{1}\in\mathcal{F}_{i}$ and $f_{2}$ in $\mathcal{F}_{j}$ such that $i\neq j$
and $f_{1}$ is a prefix of $f_{2}$, which ensures $l$ is well-defined. We
claim that we then have $1_{l}=\Cup_{i\in I}1_{l_{i}}$.

  * •

Finally, let us show $(4)\Rightarrow(1)$. Consider an eventually constant
labelling function $l$ and the set $W=1_{l}$. For $n\in\mathbb{N}$, let the
set $O_{n}$ be the open set generated by the family of histories $\\{h\mid
l(h)=1\text{ and }|h|\geq n\\}$. We have $W=\cap_{n\in\mathbb{N}}O_{n}$, and
thus $W\in\Pi^{0}_{2}$. Conversely, for all $n\in\mathbb{N}$, let $C_{n}$ be
the closed set defined as $\rho\in C_{n}$ if and only if all prefixes of
$\rho$ of length equal to or greater than $n$ have label $1$. We also have
$W=\cup_{n\in\mathbb{N}}C_{n}$, and hence $W\in\Sigma^{0}_{2}$.

###  A.5 Equivalence between Büchi/co-Büchi conditions and
$\Pi_{2}^{0}$/$\Sigma_{2}^{0}$

We provide here the proof of Lemma 3.3, which states that the sets that can be
described via a Büchi condition are exactly the sets that belong to
$\Pi_{2}^{0}$.

######  Proof A.33 (Proof of Lemma 3.3).

Suppose that $S$ belongs to $\Pi_{0}^{2}$: there exists a sequence
$(O_{n})_{n\in\mathbb{N}}$ of open sets such that
$S=\cap_{n\in\mathbb{N}}O_{n}$. Without loss of generality, we can suppose
that this sequence is increasing and $O_{0}=C^{\omega}$. Then define the
coloring function $c$ in the following way:

  * •

if $u\in C^{*}$ is such that $\textnormal{cyl}(u)\subseteq S$ then $c(u)=1$

  * •

else if $u$ is such that $\max\\{n\in\mathbb{N}|\textnormal{cyl}(u)\subseteq
O_{n}\\}>\max\\{n\in\mathbb{N}|\textnormal{cyl}(u_{<|u|-1})\subseteq O_{n}\\}$
then $c(u)=1$

  * •

else $c(u)=0$.

Now take a word $w$ that belongs to $S$: either there exists an index $n$ such
that $\textnormal{cyl}(u_{\leq n})\subseteq S$ or there exists an infinite
number of indices $n$ such that
$\max\\{n\in\mathbb{N}|\textnormal{cyl}(w_{\leq n})\subseteq
O_{n}\\}>\max\\{n\in\mathbb{N}|\textnormal{cyl}(w_{<n})\subseteq O_{n}\\}$
(because the set $\\{n|\rho\in O_{n}\\}$ is infinite). Conversely, if a word
$w$ is such that there exists an infinite number of indices $n$ such that
$c(u_{\leq n})=0$ then the set $\\{n|u\in O_{n}\\}$ is infinite and thus $u\in
S$.

Now suppose that there exists a coloring function $c$ such that $u\in
S\Leftrightarrow\\{n\in\mathbb{N}\mid c(\rho_{\leq n})=1\\}$ is infinite. We
define a sequence of open sets $(O_{n})_{n\in\mathbb{N}}$ by
$O_{n}=\\{u\mid\exists k\geq n\text{ such that }c(u_{\leq k})=1\\}$. One can
then easily check that we have $S=\cap_{n\in\mathbb{N}}O_{n}$.

##  Appendix B Proof of the main result

###  B.1 Proof for sets in $K_{2}$

We provide here the proof of Lemma 4.10, which states that when the winning
set $W$ is the union of a closed set and an open set ($W=C\cup O$), for all
$\overline{h}\in\text{Pref}(C)$ the value of $0pt(\overline{h},h)$ for $h$
eligible is bounded.

######  Proof B.1 (Proof of Lemma 4.10).

Consider $\overline{h}$ in $\text{Pref}(C)$ and $h_{1},h_{2}$ in $\Gamma$ such
that $h_{1},h_{2}\notin\text{Pref}(C)$ and $W_{\overline{h}}\subseteq
W_{h_{1}}\subseteq W_{h_{2}}$. By construction for all $l$ we have $h_{1}l\in
TC(\overline{h},h_{1})\Leftrightarrow h_{2}l\in TC(\overline{h},h_{2})$.
Moreover, for all $l$ we have $W_{h_{1}l}\subseteq W_{h_{2}l}$ by Lemma 4.2.
This ensures that for all $l$ belonging to $\mathcal{F}_{\overline{h},h_{1}}$,
since we have $W_{h_{1}l}=(A\times B)^{\omega}$ then we have
$W_{h_{2}l}=(A\times B)^{\omega}$ too, and since $h_{2}l\notin\text{Pref}(C)$
this means that $h_{2}l$ has a prefix in $\mathcal{F}$ and thus a prefix in
$\mathcal{F}_{\overline{h},h_{2}}$. This shows $0pt(\overline{h},h_{2})\leq
0pt(\overline{h},h_{1})$.

Consider then a finite set $\mathcal{S}$ of histories in
$\Gamma\setminus\text{Pref}(C)$ such that for all $h\in\mathcal{S}$ we have
$W_{\overline{h}}\subseteq W_{h}$ and for all
$h^{\prime}\in\Gamma\setminus\text{Pref}(C)$ such that
$W_{\overline{h}}\subseteq W_{h}$ there exists $h\in\mathcal{S}$ such that
$W_{h}\subseteq W_{h^{\prime}}$. As mentioned, we then have that
$0pt(\overline{h},h^{\prime})\leq 0pt(\overline{h},h)$, which ensures that for
all $h^{\prime}$ eligible we have
$0pt(\overline{h},h^{\prime})\leq\max\\{0pt(\overline{h},h)\mid
h\in\mathcal{S}\\}$.

###  B.2 Proof for sets in $\Lambda_{\theta}$

We first show that before our strategy emulates some $s_{l}$, the memory state
is exatcly the current history:

######  Lemma B.2.

For all histories $h$ compatible with $s_{f}$, for all $t\in T_{s}^{\prime}$,
we have $\mu(h)=t\Leftrightarrow h=t$.

######  Proof B.3.

A straightforward induction on $h$ allows us to prove this result.

This guarantees that when we reach a memory state $l\in\mathcal{l}$, the
current history is indeed $l$, which means that emulating $s_{l}$ from this
point guarantees the win. This is exactly what our strategy does, as stated by
the following Lemma:

######  Lemma B.4.

For all $l$ in $\mathcal{L}$ and all $h$ such that $lh$ is compatible with
$s_{f}$ we have $s_{f}(lh)=s_{l}(h)$.

######  Proof B.5.

The result is obtained by a straightforward induction on $h$.

######  Corollary B.6.

For all $\rho\in(A\times B)^{\omega}$ compatible with $s_{f}$, if there exists
$l\in\mathcal{L}$ such that $l$ is a prefix of $\rho$ then $\rho\in W$.

######  Proof B.7.

This is a direct application of Lemma B.4 and the fact that for all
$l\in\mathcal{L}$ $s_{l}$ wins from $l$.

Finally, we can prove our strategy is winning:

######  Lemma B.8.

The finite-memory strategy $s_{f}$ is a winning strategy from $\varepsilon$.

######  Proof B.9.

By Corollary B.6, we only need to prove that for all plays $\rho$ compatible
with $s_{f}$, $\rho$ has a prefix in $\mathcal{L}$. Consider then some play
$\rho$ compatible with $s_{f}$. By Lemma B.2 and since $T_{s}^{\prime}$ is
finite, we know there exists some $k\in\mathbb{N}$ such that for all $n>k$ we
have $\mu(\rho_{\leq n})\notin T_{s}^{\prime}$. Consider the smallest such
$k$. We know that we have $\mu(\rho_{\leq k}=\rho_{\leq k}\in T_{s}$. Then by
the definition of $\mu$, either $\mu(\rho_{\leq k+1})=\rho_{\leq k+1}$ or
$\mu(\rho_{\leq k+1})=m_{l}$ where $\rho_{\leq k+1}=l\in\mathcal{L}$. We know
the former is impossible as $\mu(\rho_{\leq k+1})$ does not belong to
$T_{s}^{\prime}$ by the definition of $k$ and hence does not belong to $T_{s}$
as$M\cap T_{s}=T_{s}^{\prime}$ (because all $M_{l}$’s are disjoint from
$T_{s}$). This means that the latter is true, and thus $\rho_{\leq
k+1}\in\mathcal{L}$, which concludes the proof.

###  B.3 Proof for sets in $K_{\theta}$

We provide here a proof of the induction step for Theorem 4.1 for sets in
$K_{\theta}$ for some ordinal $\theta\geq 1$. Suppose that $W\in K_{\theta}$
and Theorem 4.1 is true for all winning sets belonging to $\Lambda_{\eta}$ or
$K_{\eta}$ for all $\eta<\theta$, as well as for all winning sets belonging to
$\Lambda_{\theta}$. We suppose that Player $1$ has a winning strategy from
$\varepsilon$ and we want to show that she also has a finite-memory winning
strategy.

By Lemma A.23, there exists a closed set $C$ and a set $L$ in
$\Lambda_{\theta}$ such that $W=C\cup L$. By Theorem 3.1, $L$ belongs to
$\mathcal{D}_{\theta}$ and hence there exists an increasing family of open
sets $(O_{\eta})_{\eta<\theta}$ such that
$L=D_{\theta}((O_{\eta})_{\eta<\theta})$. For $h\in\mathcal{H}$, if there
exists $\eta$ such that $\textnormal{cyl}(h)\subseteq O_{\eta}$ then we call
the smallest such $\eta$ the rank of $h$. Else we say that $h$ is of rank
$\theta$. We write $\text{rank}(h)$ for the rank of $h$. Notice that if $h$ is
a prefix of $h^{\prime}$ then the rank of $h$ is larger than the rank of
$h^{\prime}$, and hence along a play $\rho$ there exists a unique ordinal
$\eta$ that is the rank of infinitely many prefixes of $\rho$: $\rho$ then
belongs to $W$ if and only if $\eta$ is of parity opposite to that of
$\theta$.

Similarly to the case for $K_{2}$, we split $\mathcal{H}$ into two sets: one
contains the histories that have at least one continuation in $C$ (this is the
set $\text{Pref}(C)$) and the other contains the histories that do not. For
all histories $h$ in $\Gamma\setminus\text{Pref}(C)$, we have
$W_{h}=h^{-1}L\in\Lambda_{\theta}$, which means by Lemma A.17 that
$W_{h}\in\Lambda_{\theta}$. This means that, by the induction hypothesis,
there exists a finite-memory strategy $s_{h}$ that wins from $h$.

Let $\overline{h}$ in $\Gamma\cap\text{Pref}(C)$ and $h$ in
$\Gamma\setminus\text{Pref}(C)$ such that $W_{\overline{h}}\subseteq W_{h}$
and the rank of $h$ is of the same parity as $\theta$. As before we call
$TC(\overline{h},h)$ the set $\\{hl\mid\overline{h}l\in\text{Pref}(C)\\}$
consisting of the finite continuations from $\overline{h}$ that belong to
$\text{Pref}(C)$, but rooted in $h$. Notice that all infinite continuations
$\rho$ such that for all $i$ we have $\overline{h}\rho_{\leq
i}\in\text{Pref}(C)$ are such that $\overline{h}\rho\in C$, and hence
$\overline{h}\rho\in W$ which means that $h\rho\in W$, and finally $h\rho\in
L$ since $h\notin\text{Pref}(C)$ (which means that all winning continuations
of $h$ belong to $L$ because they cannot belong to $C$). Since $h$’s rank is
of the same parity as $\theta$, we thus know that $TC(\overline{h},h)$
contains a family of histories $\mathcal{F}_{\overline{h},h}$ of rank strictly
smaller than $h$ and such that all infinite branches of $TC(\overline{h},h)$
have a finite prefix in $\mathcal{F}_{\overline{h},h}$. By Kőnig’s lemma we
can assume that this family is finite. We call $0pt(\overline{h},h)$ the
maximal length of the finite continuations $l$ such that
$hl\in\mathcal{F}_{\overline{h},h}$.

In contrast with the case for $K_{2}$ however, we cannot prove that for all
$\overline{h}\in\text{Pref}(C)$ the value of $0pt(\overline{h},h)$ for $h$
satisfying the hyptheses above is bounded. We then need to introduce more
complex ideas to build our finite-memory winning strategy.

For $\overline{h}$ in $\text{Pref}(C)$ and $\eta\leq\theta$, we call
$\text{Slice}_{\eta}(\overline{h})$ the set of histories $h$ of rank $\eta$
such that $W_{\overline{h}}\subseteq W_{h}$. We let
$\text{Min}_{\eta}(\overline{h})$ be a finite subset of
$\text{Slice}_{\eta}(\overline{h})$ such that for all $h^{\prime}$ in
$\text{Slice}_{\eta}(h)$ there exists $h\in\text{Min}_{\eta}(\overline{h})$
such that $W_{h}\subseteq W_{h^{\prime}}$ (we know such a finite set exists
because $\subseteq$ induces a well partial order on induced winning sets). Let
$\mathcal{O}$ be the set of ordinals $\eta$ such that $\eta\leq\theta$ and the
parity of $\eta$ is the same as that of $\theta$. For
$\overline{h}\in\text{Pref}(C)$, we build an increasing family of sets of
histories $(N_{\eta}(\overline{h}))_{\eta\in\mathcal{O}}$ in the following
inductive way:

  * •

$N_{\eta_{0}}(\overline{h})=\text{Min}_{\eta_{0}}(\overline{h})$ where
$\eta_{0}$ is the smallest ordinal in $\mathcal{O}$,

  * •

for $\eta>\eta_{0}$ then we let
$N_{<\eta}(\overline{h})=\cup_{\zeta<\eta,\zeta\in\mathcal{O}}N_{\zeta}(\overline{h})$
and
$N_{\eta}(\overline{h})=N_{<\eta}(\overline{h})\cup\\{h\in\text{Min}_{\eta}\mid\forall
h^{\prime}\in N_{<\eta}(\overline{h}),W_{h^{\prime}}\nsubseteq W_{h}\\}$.

Informally, we construct the family $N_{\eta}(\overline{h})$ by adding the
histories in $\text{Min}_{\eta}(\overline{h})$ whose winning set is
incomparable with that of the histories we have already considered. This
process eventually converges to a finite set, as stated by the following
Lemma:

######  Lemma B.10.

For $\overline{h}\in\text{Pref}(C)$, the set $N_{\theta}(\overline{h})$ is
finite.

######  Proof B.11.

Suppose that it is infinite. As for all $\eta$ the set
$\text{Min}_{\eta}(\overline{h})$ is finite, this means that there exists a
sequence $(h_{n})_{n\in\mathbb{N}}$ of histories in $N_{\theta}(\overline{h})$
such that $(\text{rank}(h_{n}))_{n\in\mathbb{N}}$ is strictly increasing. By
the construction of $(N_{\eta}(\overline{h}))_{\eta\in\mathcal{O}}$, this
means that for all $i,j$ such that $i<j$ we have $W_{h_{i}}\nsubseteq
W_{h_{j}}$, which is impossible since $\subseteq$ induces a well partial order
on the induced winning sets.

This allows us to define $0pt(\overline{h})=\max\\{0pt(\overline{h},h)\mid
h\in N_{\theta}(\overline{h})\\}$ for $\overline{h}\in\text{Pref}(C)$. The
construction of the winning finite-memory strategy then follows in a similar
fashion to the case for $K_{2}$. As we will see later, the set
$N_{\theta}(\overline{h})$ satisfies three essential properties which
constitute the groundwork for our proof:

  * •

it is finite, which allows us to define the value of $0pt(\overline{h})$;

  * •

it provides under-approximations for all the winning sets induced by histories
$h$ such that the rank of $h$ is of the same parity as $\theta$ and
$W_{\overline{h}}\subseteq W_{h}$;

  * •

its construction allows us to prove inductively that, for all such histories
$h$, if we play the strategy we define from $h$ starting in memory state
$\overline{h}$, then we can guarantee the win.

Consider a finite family of finite-memory strategies
$s_{i}=(M_{i},\sigma_{i},\mu_{i},m_{i})$, indexed by a set $I$ and such that
for all histories $h$ in $\Gamma\setminus\text{Pref}(C)$ there exists some
$i\in I$ such that $s_{i}$ wins from $h$. Such a family exists because by the
partial order hypothesis there exists a finite set $\mathcal{S}$ of histories
in $\Gamma\setminus\text{Pref}(C)$ whose induced winning sets provide
under)approximation for all winning sets induced by histories in
$\Gamma\setminus\text{Pref}(C)$. It then only remains to consider one finite-
memory strategy for each history in $\mathcal{S}$.

Consider also a finite family $(\overline{h}_{j})_{j\in J}$ of histories in
$\Gamma\cap\text{Pref}(C)$ indexed by $J\subseteq\mathbb{N}$ such that for all
histories $\overline{h}$ in $\text{Pref}(C)\cap\Gamma$ there exists $j\in J$
such that $W_{\overline{h}_{j}}\subseteq W_{\overline{h}}$. For all $j\in J$,
let $T_{j}=\\{\overline{h}_{j}l\in\text{Pref}(C)\mid|l|\leq
0pt(\overline{h}_{j})\\}$. Up to renaming, we can suppose that the $T_{j}$’s
are dsijoint from one another. We build our finite-memory winning strategy
$s=(M,\sigma,\mu,m_{0})$ in the following way:

  * •

$M=\cup_{i\in I}M_{i}\cup\cup_{j\in J}T_{j}$;

  * •

for $m\in M_{i}$ we let $\sigma(m)=\sigma_{i}(m)$;

  * •

for $t\in T_{j}$ we let $\sigma(t)$ be any non-losing action from $t$;

  * •

for $m\in M_{i}$ and $(a,b)\in A\times B$ we let
$\mu(m,(a,b))=\mu_{i}(m,(a,b))$;

  * •

for $t\in T_{j}$ and $(a,b)\in A\times B$ such that $a=\sigma(t)$:

    * –

if $t(a,b)\in T_{j}$ then $\mu(t,(a,b))=t(a,b)$;

    * –

else if $t(a,b)\in\Gamma\setminus\text{Pref}(C)$ then there exists $i\in I$
such that $s_{i}$ wins from $t(a,b)$: we let $\mu(t,(a,b))=m_{i}$;

    * –

else if $t(a,b)\in\Gamma\cap\text{Pref}(C)$ then there exists $j\in J$ such
that $W_{\overline{h}_{j}}\subseteq W_{t(a,b)}$ and we let
$\mu(h,(a,b))=\overline{h}_{j}$;

  * •

$m_{0}=\overline{h}_{j}$ where $j\in J$ is such that
$W_{\overline{h}_{j}}\subseteq W_{\varepsilon}$.

Once again, our memory function is built in such a way that if the memory
state belongs to $T_{j}$ for some $j\in J$ then it provides an under-
approximation for the winning set induced by the current history. This time
however we have to be more precise: if $t\in\cup_{j\in J}T_{j}$ is such that
$W_{t} \subseteq W_{h}$, then for all finite continuations $h^{\prime}$ such
that $\mu(t,h^{\prime})$ (the memory state obtained by following our strategy
from memory state $t$ against history $h^{\prime}$) belongs to $\cup_{j\in
J}T_{j}$, $\mu(t,h^{\prime})$ provides an under-approximation for the induced
winning set of $hh^{\prime}$.

######  Lemma B.12.

For all $t\in\cup_{j\in J}T_{j}$ and $h\in\mathcal{H}$, if $W_{t}\subseteq
W_{h}$ then for all $h^{\prime}$ such that $\mu(t,h^{\prime})\in\cup_{j\in
J}T_{j}$ we have $W_{\mu(t,h^{\prime})}\subseteq W_{hh^{\prime}}$.

######  Proof B.13.

The proof is by induction on $h^{\prime}$. First we have
$\mu(t,\varepsilon)=t$ and by hypothesis $W_{t}\subseteq W_{h}$. Consider now
$h^{\prime}\in\mathcal{H}$ such that $\mu(t,h^{\prime})\in T_{j}$ for some
$j\in J$ and such that $W_{\mu(t,h^{\prime})}\subseteq W_{hh^{\prime}}$. Let
$(a,b)\in A\times B$ such that $\mu(t,h^{\prime}(a,b))\in T_{j^{\prime}}$ for
some $j^{\prime}\in J$. Then,

  * •

if $\mu(t,h^{\prime}(a,b))=\mu(t,h^{\prime})(a,b)$ then the desired result
follows by Lemma 4.2,

  * •

else we must have $\mu(t,h^{\prime})(a,b)\in\Gamma\cap\text{Pref}(C)$ (else we
would not have $\mu(t,h^{\prime}(a,b))\in T_{j^{\prime}}$) and
$\mu(t,h^{\prime}(a,b))=\overline{h}_{j^{\prime}}$ with $j^{\prime}$ such that
$W_{\overline{h}_{j^{\prime}}}\subseteq W_{\mu(t,h^{\prime})(a,b)}$, and
$W_{\mu(t,h^{\prime})(a,b)}\subseteq W_{hh^{\prime}(a,b)}$ once again by Lemma
4.2, which ensures the result.

######  Corollary B.14.

If $\mu(h)\in T_{j}$ for some $j\in J$ then we have $W_{\mu(h)}\subseteq
W_{h}$.

######  Proof B.15.

This is a direct application of Lemma B.12, as by construction we have
$W_{m_{0}}\subseteq W_{\varepsilon}$.

Moreover, if we ever reach a memory state in $M_{i}$ for some $i\in I$ then
from this point onward our finite-memory strategy will emulate the strategy
$s_{i}$:

######  Lemma B.16.

For all $m\in M$, if $h\in\mathcal{H}$ is such that $\mu(m,h)\in M_{i}$ for
some $i$ then for all $h^{\prime}$ we have
$\mu(m,hh^{\prime})=\mu_{i}(\mu(m,h),h^{\prime})$.

######  Proof B.17.

This is shown by a straightforward induction on $h^{\prime}$.

######  Corollary B.18.

For all $\in I$, if $h\in\mathcal{H}$ is such that $s_{i}$ wins from $h$ then
$(M,\mu,\sigma,m_{i})$ wins from $h$.

######  Proof B.19.

By application of Lemma B.16 and by the definition of $\sigma$, all plays
$\rho$ compatible with $(M,\mu\sigma,m_{i})$ are also compatible with $s_{i}$.

By combining Lemma B.12 with Lemma B.16, we obtain that for any history
$h\in\Gamma$, if $t\in T_{j}$ is such that the winning set induced by $t$
constitutes an under-approximation of the winning set induced by $h$, if by
playing according to our finite-memory strategy from memory state $t$ in $h$
we reach a memory state that belongs to $M_{i}$ for some $i\in I$ then we can
guarantee that if we keep playing according to $s$ then we will win:

######  Lemma B.20.

For all $t\in\cup_{j\in J}T_{j}$ and $h\in\mathcal{H}$, if $h$ is such that
$W_{t}\subseteq W_{h}$ then for all $h^{\prime}$ compatible with
$(M,\sigma,\mu,t)$ such that $\mu(t,h^{\prime})=m_{i}$ for some $i\in I$ then
$s_{i}$ is winning from $hh^{\prime}$.

######  Proof B.21.

Consider $h^{\prime}_{0}$, the smallest prefix of $h^{\prime}$ such that
$\mu(t,h^{\prime}_{0})\in M_{i}$. By Lemma B.16 we know that $h^{\prime}_{0}$
is also the smallest prefix of $h^{\prime}$ such that
$\mu(h^{\prime}_{0})\notin\cup_{j\in J}T_{j}$ (because if
$\mu(t,h^{\prime})\in M_{i}$ then no prefix $h^{\prime\prime}$ of $h^{\prime}$
can be such that $\mu(t,h^{\prime\prime})\in M_{i^{\prime}}$ with
$i^{\prime}\neq i$). We will show that $s_{i}$ wins from $hh^{\prime}_{0}$.
Notice that if $s_{i}$ wins from $hh^{\prime}_{0}$ then $s_{i}$ wins from
$hh^{\prime}$: indeed, let $l$ be the history such that
$h^{\prime}=h^{\prime}_{0}l$. As we have
$\mu(t,hh^{\prime}_{0})=\mu(t,hh^{\prime})=m_{i}$, by Lemma B.16, this means
that $\mu_{i}(m_{i},l)=m_{i}$. If $s_{i}$ wins from $hh^{\prime}_{0}$ then for
all $l^{\prime}$ compatible with $s_{i}$, the strategy
$(M_{i},\sigma_{i},\mu_{i},\mu_{i}(l^{\prime}))$ must win from
$hh^{\prime}_{0}l^{\prime}$, and in particular $s_{i}$ must win from
$hh^{\prime}_{0}l=hh^{\prime}$.

Let then $h^{\prime}_{0}=l^{\prime}_{0}(a,b)$ with $l^{\prime}\in\mathcal{H}$
and $(a,b)\in A\times B$ (we cannot have $h^{\prime}_{0}=\varepsilon$ as
$\mu(t,\varepsilon)=t$ by definition). Obviously
$\mu(t,l^{\prime}_{0})\in\cup_{j\in J}T_{j}$. Since
$\mu(t,l^{\prime}_{0}(a,b))\in M_{i}$, by construction we have
$\mu(t,l^{\prime}_{0})=m_{i}$ and $s_{i}$ wins from
$\mu(t,l^{\prime}_{0})(a,b)$. Furthermore, by Lemma B.12 we have
$W_{\mu(t,l^{\prime}_{0})}\subseteq W_{hl^{\prime}_{0}}$, and hence
$W_{\mu(t,l^{\prime}_{0})(a,b)}\subseteq
W_{hl^{\prime}_{0}(a,b)}=W_{hh^{\prime}_{0}}$ by Lemma 4.2, which means that
$s_{i}$ wins from $hh^{\prime}_{0}$ as well.

######  Corollary B.22.

For all $t\in\cup_{j\in J}T_{j}$ and $h\in\mathcal{H}$, if $h$ is such that
$W_{t}\subseteq W_{h}$ then for all $h^{\prime}$ compatible with
$(M,\sigma,\mu,t)$ such that $\mu(t,h^{\prime})=m_{i}$ for some $i\in I$ then
$(M,\sigma,\mu,m_{i})$ is winning from $hh^{\prime}$.

######  Proof B.23.

This is a straightforward application of Corollary B.18 and Lemma B.20.

######  Corollary B.24.

If $h\in\mathcal{H}$ is compatible with $s$ and is such that $\mu(h)=m_{i}$
for some $i\in I$ then $s_{i}$ is winning from $h$.

######  Proof B.25.

This is a direct application of Lemma B.20, as by construction we have
$W_{m_{0}}\subseteq W_{\varepsilon}$.

######  Corollary B.26.

If $h\in\mathcal{H}$ is compatible with $s$ and is such that $\mu(h)\in M_{i}$
for some $i\in I$ then $(M,\sigma,\mu,\mu(h))$ is winning from $h$.

######  Proof B.27.

If $\mu(h)\in M_{i}$ then by construction $h$ has a prefix $h_{0}$ such that
$\mu(h_{0})=m_{i}$. By Lemma B.24 we know that $s_{i}$ wins from $h_{0}$, and
hence by Lemma B.16 we have that $(M,\sigma,\mu,\mu(h))$ wins from $h$.

Finally, we can show that if by playing according to $s$ we reach a history
that is outside of $\text{Pref}(C)$ then we can keep playing according to $s$
and win:

######  Lemma B.28.

For all $h\in\mathcal{H}\setminus\text{Pref}(C)$, if $h$ is compatible with
$s$ and $\mu(h)=\overline{h}_{j}$ for some $j\in J$ then
$(M,\sigma,\mu,\overline{h}_{j})$ wins from $h$.

######  Proof B.29.

For $j\in J$ and $\eta\leq\theta$ we let $\mathcal{P}(\overline{h}_{j},\eta)$
be the following property: for all
$h\in\text{Slice}_{\eta}(\overline{h}_{j})$, $(M,\sigma,\mu,\overline{h}_{j})$
wins from $h$. We shall prove by induction on $\eta$ that for all
$\eta\leq\theta$, for all $j\in J$ we have
$\mathcal{P}(\overline{h}_{j},\eta)$.

For the initial case ($\eta=0$), let $j\in J$.

  * •

If $\theta$ is even, then all histories $h$ such that $\text{rank}(h)=0$ are
such that $W_{h}=\emptyset$. Since $\overline{h}_{j}\in\Gamma$, it follows
that $\text{Slice}_{0}(\overline{h}_{j})=\emptyset$ and hence we have
$\mathcal{P}(\overline{h}_{j},0)$.

  * •

If $\theta$ is odd, then all histories $h$ such that $\text{rank}(h)=0$ are
such that $W_{h}=(A\times B)^{\omega}$, which means that any strategy wins
from $h$ and hence we have $\mathcal{P}(\overline{h}_{j},0)$.

Consider now an ordinal $\eta$ such that $\eta>0$ and $\eta\leq\theta$ and
suppose that for all $j\in J$ and for all $\eta^{\prime}<\eta$ we have
$\mathcal{P}(\overline{h}_{j},\eta^{\prime})$.

Suppose that $\eta$ is of parity opposite to that of $\theta$. Let $j\in J$,
$h\in\text{Slice}_{\eta}(\overline{h}_{j})$ and $\rho$ be a play compatible
with $(M,\sigma,\mu,\overline{h}_{j})$. We want to prove that $h\rho\in W$. If
there exists $k\geq 0$ such that $\mu(\overline{h}_{j},\rho_{\leq}k)=m_{i}$
for some $i\in I$ then $h\rho$ belongs to $W$ by Corollary B.22. Else from the
construction of $\mu$ we have that for all $k\geq 0$,
$\mu(\overline{h},\rho_{\leq k})\in\cup_{j^{\prime}\in J}T_{j^{\prime}}$. If
for all $k$ we have $\text{rank}(h\rho_{\leq k})=\eta$ then $h\rho\in W$ and
we have our result. Suppose then that there exists $k$ such that
$\text{rank}(h\rho_{\leq k})=\eta^{\prime}<\eta$. By construction there exists
some integer $n\geq k$ such that $\mu(\overline{h}_{j},\rho_{\leq
n})=\overline{h}_{j^{\prime}}$ for some $j^{\prime}\in J$. Then by Lemma B.12,
we have that $W_{\overline{h}_{j^{\prime}}}\subseteq W_{h\rho_{\leq n}}$,
which means that $h\rho_{\leq
n}\in\text{Slice}_{\eta^{\prime}}(\overline{h}_{j}^{\prime})$. By
$\mathcal{P}(h_{j^{\prime}},\eta^{\prime})$, we can conclude that
$(M,\sigma,\mu,h_{j^{\prime}})$ wins from $h\rho_{\leq n}$ and thus
$h\rho=h\rho_{\leq n}\rho_{>n}\in W$ (because $\rho$ is compatible with
$(M,\sigma,\mu,h_{j})$ and $\mu(h_{j},\rho{\leq n})=h_{h_{j}^{\prime}}$, which
means that $\rho_{>n}$ is compatible with $(M,\sigma,\mu,h_{j^{\prime}})$).

Suppose now that $\eta$ and $\theta$ have the same parity. Let $j\in J$ and
let $h\in\text{Slice}_{\eta}(\overline{h}_{j})$. There exists a history
$h_{0}$ in $\text{Min}_{\eta}(\overline{h}_{j})$ such that $W_{h_{0}}\subseteq
W_{h}$. We shall prove that $(M,\sigma,\mu,\overline{h}_{j})$ wins from
$h_{0}$, which implies that $(M,\sigma,\mu,\overline{h}_{j})$ wins from $h$.
If $h_{0}\notin N_{\eta}(\overline{h}_{j})$ then by construction there exists
$\eta^{\prime}<\eta$ and $h_{1}\in N_{\eta^{\prime}}(\overline{h}_{j})$ such
that $W_{h_{1}}\subseteq W_{h_{0}}$. By
$\mathcal{P}(\overline{h}_{j},\eta^{\prime})$ we know that
$(M,\sigma,\mu,\overline{h}_{j})$ wins from $h_{1}$ and hence wins from
$h_{0}$. Suppose then that $h_{0}\in N_{\eta}(\overline{h}_{j})$ and let
$\rho$ be a play compatible with $(M,\sigma,\mu,\overline{h}_{j})$. We want to
show that $h_{0}\rho$ belongs to $W$. As before, if there exists $k\geq 0$
such that $\mu(\overline{h}_{j},\rho_{\leq k})=m_{i}$ for some $i\in I$ then
$h_{0}\rho$ belongs to $W$ by Corollary B.22. Else from the definition of $M$
as the disjoint union of $\cup_{i\in I}M_{i}$ and $\cup_{j^{\prime}\in
J}T_{j^{\prime}}$ we have that for all $k\geq 0$,
$\mu(\overline{h},\rho_{\leq}k)\in\cup_{j^{\prime}\in J}T_{j^{\prime}}$. In
particular notice that for every $k$ such that $k\leq 0pt(\overline{h}_{j})$
we have $\mu(\overline{h}_{j},\rho_{\leq}k)=\overline{h}_{j}\rho_{\leq k}\in
T_{j}$. Let $d=0pt(\overline{h}_{j})$. Since $h_{0}\in
N_{\eta}(\overline{h}_{j})$ and $N_{\eta}(\overline{h}_{j})\subseteq
N_{\theta}(\overline{h}_{j})$ we have $d\geq 0pt(\overline{h}_{j},h_{0})$.
Recall that by definition this means that for any $l$ such that $|l|\geq d$
and $\overline{h}_{j}l\in\text{Pref}(C)$ we have $\text{rank}(h_{0}l)<\eta$.
Since $T_{j}\subseteq\text{Pref}(C)$ by definition, we thus have that
$\text{rank}(h_{0}\rho_{\leq d})<\eta$. Again by construction, there exists
$j^{\prime}\in J$ such that $\mu(\overline{h}_{j},\rho_{\leq
d+1})=\overline{h}_{j^{\prime}}$. By Lemma B.12 we have that
$W_{\overline{h}_{j^{\prime}}}\subseteq W_{h_{0}\rho_{\leq d+1}}$, and by the
properties of the rank we have that $\text{rank}(h_{0}\rho_{\leq
d+1})=\eta^{\prime}<\eta$ (because $\text{rank}(h_{0}\rho_{\leq
d+1})\leq\text{rank}(h_{0}\rho_{\leq d})$). Finally, by
$\mathcal{P}({h_{j^{\prime}},\eta^{\prime}})$ we know that
$(M,\sigma,\mu,\overline{h}_{j^{\prime}})$ wins from $h_{0}\rho_{\leq d+1}$,
which means that $h_{0}\rho\in W$ (because $\rho$ is compatible with
$(M,\sigma,\mu,\overline{h}_{j})$ and $\mu(\overline{h}_{j},\rho_{\leq
d+1})=\overline{h}_{j^{\prime}}$, which implies that $\rho_{>d+1}$ is
compatible with $(M,\sigma,\mu,\overline{h}_{j^{\prime}})$) and allows us to
conclude.

We finally have all the preliminary results we need to conclude this induction
step:

######  Theorem B.30.

The finite-memory strategy $s$ wins from $\varepsilon$.

######  Proof B.31.

Let $\rho$ be a play compatible with $s$. We want to show that $\rho\in W$. If
for all $n\in\mathbb{N}$ we have $\rho_{\leq n}\in\text{Pref}(C)$ then
$\rho\in C$ and hence $\rho\in W$. Else if there exists some $n\in\mathbb{N}$
such that $\mu(\rho)\in M_{i}$ for some $i\in I$ then by Corollary B.22 we
have $\rho\in W$. Else by construction there exists some $n\in\mathbb{N}$ such
that $\rho_{\leq n}\notin\text{Pref}(C)$ and such that there exists $j\in J$
such that $\mu(\rho_{\leq n})=\overline{h}_{j}$. By Corollary B.14 we know
that $W_{\overline{h}_{j}}\subseteq W_{\rho_{\leq n}}$ and we can conclude by
Lemma B.28 that $\rho\in W$.

##  Appendix C Tightness of the main result

###  C.1 Büchi counter-example

Here we provide an example of a game whose winning set satisfies the well
partial order property and belongs to $\Pi_{2}^{0}$. While Player $1$ does
have a winning strategy, she does not have any fnite-memory one.

######  Example C.1.

Let $A$ be a finite set of at least two elements and $w$ a disjunctive
sequence on $A\times\\{0\\}$. We define the labeling function
$l:(A\times\\{0\\})^{*}\to\\{0,1\\}$ in the following way: $l(h)=1$ if and
only if there exists $h_{0}$ and $h^{\prime}$ such that $h=h_{0}h^{\prime}$
and $h^{\prime}$ is the longest factor of $h$ that is also a prefix of $w$.
Let then $W$ be the set defined by $\rho\in W$ if and only if infinitely many
prefixes $h$ of $\rho$ are such that $l(h)=1$ and consider the game
$(A,\\{0\\},W)$.

Let us study the elements of $W$. We want to show that a play $\rho$ belongs
to $W$ if and only if its set of factors contains infinitely many prefixes of
$w$. A play $\rho$ belongs to $W$ if and only if it is such that infinitely
many prefixes $h$ of $\rho$ are such that $l(h)=1$. By definition if $l(h)=1$
then the longest factor of $h$ that is also a prefix of $w$ is also a suffix
of $h$. This means that if $l(h)=1$ and $h^{\prime}$ is such that
$l(hh^{\prime})=1$ then $hh^{\prime}$ has at least one factor which is also a
prefix of $w$ and longer than any factor of $h$ satisfying the same property.
In particular this means that the set of factors of $hh^{\prime}$ contains
strictly more prefixes of $w$ than the set of factors of $h$. Consequentially,
if a play $\rho$ is such that it has infinitely many prefixes $h$ such that
$l(h)=1$, then the set of factors of $\rho$ contains infinitely many prefixes
of $w$. Conversely, let $\rho$ be such that the set of factors of $\rho$
contains infinitely many prefixes of $w$ and let $\rho=h_{0}h_{1}...$ where
for each $n$ the word $h_{0}...h_{n}$ is the smallest prefix of $\rho$ such
that it has a suffix which is a prefix of $w$ that is not a factor of
$h_{0}...h_{n-1}$. Notice that if a prefix $p$ of $w$ is a factor of
$h_{0}...h_{n}$ but not of $h_{0}...h_{n-1}$ then it is also longer than all
prefixes of $w$ that are factors of $h_{0}...h_{n-1}$. This means that for all
$n$ we have $l(h_{0}...h_{n})=1$ and hence $\rho\in W$.

With this characterization of $W$, we will now see that this winning condition
is prefix-independent: that is, for all histories $h$ we have $W_{h}=W$.
Indeed, consider two histories $h$ and $h^{\prime}$ and a play $\rho$ such
that $h\rho\in W$. Let us split the set of factors of $h\rho$ into two sets:
$F_{>}$ is the set of factors of $\rho$ while $F_{<}$ is the set of factors of
$h\rho$ that overlap with $h$. Either $F_{>}$ or $F_{<}$ contains infinitely
many prefixes of $w$, and we will show $F_{>}$ always does. Suppose that
$F_{<}$ contains infinitely many prefixes of $w$. In particular, since $h$ is
a finite word, there exists a suffix $h_{0}$ of $h$ such that infinitely many
of these elements can be written as $h_{0}r$ with $r$ a prefix of $\rho$. This
means that infinitely many prefixes $r$ of $\rho$ are such that $h_{0}r$ is a
prefix of $w$, and hence we actually have $h_{0}\rho=w$. This means that
$\rho$ is a suffix of $w$, and as such is also a disjunctive sequence, which
ensures that infinitely many of its factors are prefixes of $w$. This means
that $F_{>}$ always contains infinitely many prefixes of $w$, and hence
$h^{\prime}\rho\in W$.

Since the winning condition is prefix-independent, all the induced winning
sets are equal: for all histories $h$ we have $W_{h}=W$. Hence it is obvious
that $\subseteq$ induces a well partial on the induced winning sets. Moreover,
all winning plays $\rho$ have infinitely many factors that are also prefixes
of $w$, and thus are disjunctive sequences too and are such can only be
irregular sequences. This means that, while Player $1$ obviously have a
winning strategy from $\varepsilon$, she cannot have a finite-memory one
(whose resulting play could only be a regular sequence).

###  C.2 Co-Büchi counter-example

Here we provide an example of a game whose winning set satisfies the well
partial order property and belongs to $\Sigma_{2}^{0}$. While Player $1$ does
have a winning strategy, she does not have any fnite-memory one.

######  Example C.2.

Let $A$ be a finite set of at least two elements and $w$ an irregular sequence
in $(A\times\\{0\\})^{*}$. Let
$W=\\{\rho\in(A\times\\{0\\})^{\omega}\mid\exists
h\in(A\times\\{0\\})^{*},\rho=h\rho_{0}\text{ where }\rho_{0}\text{ is a
suffix of }w\\}$. $W$ is the set of sequences which have a suffix in common
with $w$. Consider then the game $(A,\\{0\\},W)$.

We shall now show that $W\in\Sigma^{0}_{2}$. We have $W=\cup_{h\in
A^{*}}\cup_{\rho_{0}\text{ suffix of }w}\\{h\rho_{0}\\}$. Since $A^{*}$ is
countable and $w$ has a countable number of suffixes, $W$ is then a countable
union of closed set, which means that $W\in\Sigma^{0}_{2}$.

Obviously the winning condition of this game is prefix-independent, that is we
have for all histories $h$ $W_{h}=W$, and hence $\subseteq$ trivially induces
a well partial on the induced winning sets. Moreover as $W\neq\emptyset$ we
know that Player $1$ has a winning strategy from $\varepsilon$. However, all
winning play have a suffix which coincide with a suffix of $w$. As $w$ is
irregular, all winning plays are irregular too, which means that there exists
no finite-memory winning strategy for Player $1$ in this game.

###  C.3 Virtual bar counter-example

In this section we tackle the well partial order hypothesis and study one
possible weakening of it: instead of $\subseteq$ inducing a well partial order
on the histories of $\Gamma$, we only make the assumption that there exists a
virtual bar for the induced winning set: there exists a finite family $S$ of
sets such that every induced winning set includes set in $S$. We provide an
example with a closed winning set that shows this hypothesis does not lead to
the same result, as Player $1$ has a winning strategy but no finite one.

######  Example C.3.

Let $A=\\{0,1,x,y\\}$. For all $n\in\mathbb{N}$, let $v_{n}=(1,0)(0,0)^{n}$
and $u_{n}=(0,0)(1,0)^{n}$. Let $c_{x}=(x,0)v_{0}v_{1}...$ and
$c_{y}=(y,0u_{0}u_{1}...$. Consider an irregular sequence $s_{n}$ over
$\\{x,y\\}$ and let $W$ be the set of words in $(A\times\\{0\\})^{\omega}$
such that $\rho\in W$ if and only if either there exists a sequence
$(w_{n})_{n\in\mathbb{N}}$ of non-empty finite words in $(A\times\\{0\\})^{*}$
such that for each $n$ we have $w_{n}\sqsubset c_{s_{n}}$ and
$\rho=w_{0}w_{1}w_{2}...$, or there exists $k\in\mathbb{N}$ and a finite
sequence $(w_{n})_{n<k}$ of non-empty finite words in $(A\times\\{0\\})^{*}$
such that for each $n<k$ we have $w_{n}\sqsubset c_{s_{n}}$ and
$\rho=w_{0}...w_{k-1}c_{s_{k}}$. As in every one-player games where the
winning set is non-empty, Player $1$ has a winning strategy from $\varepsilon$
in $(A,\\{0\\},W)$.

For a finite word $h$ in $(A\times\\{0\\})^{*}$ beginning with either $(x,0)$
or $(y,0)$, we call $xy$-decomposition of $h$ the sequence $(w_{n})_{n<k}$ of
non-empty finite words such that each $w_{n}$ begins with either $(x,0)$ or
$(y,0)$ and the letters $(x,0)$ or $(y,0)$ do not appear later in $w_{n}$, and
$h=w_{0}...w_{k}$.

Let us show $W$ is a closed set. We will show that $\rho$ does not belong to
$W$ if and only if there exists a finite prefix $h$ of $\rho$ such there
exists no finite sequence $(w_{n})_{n<k}$ of non-empty finite words in
$(A\times B)^{*}$ such that for each $n$ $w_{n}\sqsubset c_{s_{n}}$ and
$h=w_{0}...w_{k-1}$. The complement of $W$ is then the open set generated by
these such histories. Notice the desired property is equivalent to the fact
that either $h$ does not begin with either $(x,0)$ or $(y,0)$ or the
$xy$-decomposition of $h$ $(w_{n})_{n<k}$ does not satisfy $w_{n}\sqsubset
c_{s_{n}}$ for all $n<k$.

Let $\rho\in(A\times\\{0\\})^{\omega}$. Let $h$ be a finite prefix of $\rho$
such that there exists no finite sequence $(w_{n})_{n<k}$ of non-empty finite
words in $(A\times\\{0\\})^{*}$ such that for each $n$ $w_{n}\sqsubset
c_{s_{n}}$ and $h=w_{0}...w_{k-1}$. Obviously there cannot be any sequence
$(w_{n})_{n\in\mathbb{N}}$ of non-empty finite words in $(A\times\\{0\\})^{*}$
such that for each $n$ $w_{n}\sqsubset c_{s_{n}}$ and
$\rho=w_{0}w_{1}w_{2}...$, nor any $k\in\mathbb{N}$ and finite sequence
$(w_{n})_{n<k}$ of non-empty finite words in $(A\times\\{0\\})^{*}$ such that
for each $n<k$ we have $w_{n}\sqsubset c_{s_{n}}$ and
$\rho=w_{0}...w_{k-1}c_{s_{k}}$, as we could use such a sequence to build a
suitable sequence for $h$. This means that $\rho\notin W$.

Let then $\rho\notin W$. Obviously if $\rho$ does not start with either
$(x,0)$ or $(y,0)$ then $\rho$ satisfies the desired property (with its prefix
of length $1$). Else,

  * •

if the letters $\\{(x,0),(y,0)\\}$ appear infinitely often along $\rho$, then
let $(w_{n})_{n\in\mathbb{N}}$ be the sequence of non-empty words such that
$\rho=w_{0}w_{1}...$ and for each $n$ $w_{n}$ begins with either $(x,0)$ and
$(y,0)$ and the letters $\\{(x,0),(y,0)\\}$ do not appear in $w_{n}$ except
for the first letter. Since $\rho\notin W$, there exists $k$ such that $w_{k}$
is not a prefix of $c_{s_{k}}$. This means in particular that $w_{0}...w_{k}$
is a finite prefix of $\rho$ such that $(w_{n})_{n<k+1}$ is its
$xy$-decomposition and it does not satisfy $w_{n}\sqsubset c_{s_{n}}$ for all
$n<k+1$.

  * •

else the letters $\\{(x,0),(y,0)\\}$ appear finitely often along $\rho$. Let
then $(w_{n})_{n<k}$ be the sequence of non-empty words such that
$\rho=w_{0}w_{1}...w_{k-1}$ and for each $n$ $w_{n}$ begins with either
$(x,0)$ or $(y,0)$ and the letters $\\{(x,0),(y,0)\\}$ do not appear in
$w_{n}$ except for the first letter. Since $\rho\notin W$, either there exists
$n<k-1$ such that $w_{n}$ is not a prefix of $c_{s_{n}}$, or $w_{k-1}\neq
c_{s_{k-1}}$. In the first case, we use arguments similar to the previous
item. In the second case, there exists a prefix $w^{\prime}$ of $w_{k-1}$ that
is not a prefix of $c_{s_{n}}$, and we use similar arguments on
$w_{0}...w_{k-2}w^{\prime}$.

Now that we know $W$ is a closed set, let us show that Player $1$ does not
have a finite-memory winning strategy from $\varepsilon$ in $(A,\\{0\\},W)$.
Indeed, consider such a finite-memory winning strategy $(M,\sigma,\mu,m_{0})$
and let $\rho$ be its outcome.

  * •

If there exists a sequence $(w_{n})_{n\in\mathbb{N}}$ of non-empty finite
words in $(A\times\\{0\\})^{*}$ such that for each $n$ $w_{n}\sqsubset
c_{s_{n}}$ and $\rho=w_{0}w_{1}w_{2}...$, then Player $1$ also has a finite-
memory winning strategy from $\varepsilon$ in
$(A,\\{0\\},\\{s_{0}s_{1}...\\})$, which is impossible since
$(s_{n})_{n\in\mathbb{N}}$ is irregular.

  * •

Else there exists $k\in\mathbb{N}$ and a finite sequence $(w_{n})_{n<k}$ of
non-empty finite words in $(A\times\\{0\\})^{*}$ such that for each $n<k$ we
have $w_{n}\sqsubset c_{s_{n}}$ and $\rho=w_{0}...w_{k-1}c_{s_{k}}$. This
means that Player $1$ has a finite-memory winning strategy from $\varepsilon$
in $(A,\\{0\\},\\{c_{s_{k}}\\})$, which is also impossible.

$W$ is hence a closed set with virtual bar $\\{c_{x},c_{y}\\}$ which is such
that there exists no finite-memory winning strategy for Player $1$ in
$(A,\\{0\\},W)$.

###  C.4 What about the opponent?

In this section, we want to answer the following question: given a two-player
game $(A,B,W)$ where $W$ belongs to the Hausdorff difference hierarchy and
such that $\subseteq$ induces a well partial order on the induced winning sets
for Player $1$, if Player $2$ has a winning strategy for $\varepsilon$ then is
it the case that he also has a finite-memory winning strategy? We provide here
a counter-example to show this is not the case as soon as $W\in\Lambda_{2}$.

######  Example C.4.

Let $A=B=\\{0,1\\}$. Let $W=\cup_{n\in\mathbb{N}}\cup_{k\leq n}(\\{0\\}\times
B)^{n}(\\{1\\}\times B)[(A\times\\{0\\})^{k}(A\times\\{1\\})(A\times
B)^{\omega}+(A\times\\{0\\})^{\omega}]$. Informally, Player $1$ wins if the
following happens:

  * •

first Player $1$ plays $0$ a number $n$ of times, and then plays $1$;

  * •

then Player $2$ either plays $0$ a number $k\leq n$ of times, and then plays
$1$, or Player $2$ plays $0$ for ever.

Hence, to win Player $2$ must wait until Player $1$ plays action $1$, then
play $0$ for strictly longer than he has waited, and only after play $1$. We
can thus divide the histories of this game into four groups:

  * •

the first group is composed of the histories along which Player $1$ has only
played $0$. The induced winning set of these histories is wholly determined by
their length, and for any two histories belonging to this group, the longest
history is always associated with a bigger winning set. Hence $\subseteq$
induces a well partial order over the induced winning sets associated with the
histories of this group.

  * •

the second group is composed of the histories along which Player $1$ has
played $0$ a number $n$ of times, then played $1$, and since then Player $2$
has played $0$ a number $k$ of times and has not played $1$. The induced
winning set for the histories of this group is wholly determined by the value
$n-k$: if $n-k\leq 0$ then the induced winning set associated with the history
is $(A\times\\{0\\})^{\omega}$, while if $n-k>0$ then the induced winning set
associated with the history is
$(A\times\\{0\\})^{\omega}\cup\cup_{i<n-k}(A\times\\{0\\})^{i}(A\times\\{1\\})$.
In particular, if two histories $h$ and $h^{\prime}$ associated with
parameters $(n_{h},k_{h})$ and $(n_{h^{\prime}},k_{h^{\prime}})$ in this group
are such that $0\leq n_{h}-k_{h}\leq n_{h^{\prime}}-k_{h^{\prime}}$ then we
have $W_{h}\subseteq W_{h^{\prime}}$. This means that $\subseteq$ induces a
well partial order over the induced winning sets associated with the histories
of this group.

  * •

the third group consists of the histories along which Player $1$ has played
$0$ a number $n$ of times, then played $1$, and since then Player $2$ has
played $0$ a number $k\leq n$ of times and then played $1$. The induced
winning set for the histories of this group is always equal to $(A\times
B)^{\omega}$, and hence $\subseteq$ trivially induces a well partial order
over said induced winning sets.

  * •

finally, the fourth group is the group of the histories along which Player $1$
has played $0$ a number $n$ of times, then played $1$, and since then Player
$2$ has played $0$ a number $k>n$ of times and then played $1$. The induced
winning set for the histories of this group is always equal to $\emptyset$,
which means that $\subseteq$ trivially induces a well partial over said
induced winning sets.

We have seen that $\subseteq$ induces a well partial order over the induced
winning sets associated with the histories of each group. This means that it
also induces a well partial order over the induced winning sets of the game as
a whole.

One can also easily check that Player $2$ has a winning strategy from
$\varepsilon$, which consists in waiting until Player $1$ plays action $1$ and
then play action $0$ for long enough until he can finally win by playing $1$.
However, as the number of times he has to play action $0$ increases as Player
$1$ waits before playing action $1$, he does not have a finite-memory winning
strategy.