11institutetext: LSV – CNRS & ENS Paris-Saclay, Université Paris-Saclay,
France 22institutetext: LACL – UPEC, France 33institutetext: F.R.S.-FNRS &
UMONS – Université de Mons, Belgium

# Games Where You Can Play Optimally with Finite Memory††thanks: Research
supported by F.R.S.-FNRS under Grant n∘ F.4520.18 (ManySynth), F.R.S.-FNRS
mobility funding for scientific missions (Y. Oualhadj in UMONS, 2018), and ENS
Paris-Saclay visiting professorship (M. Randour, 2019). Mickael Randour is an
F.R.S.-FNRS Research Associate and Pierre Vandenhove is an F.R.S.-FNRS
Research Fellow.

Patricia Bouyer 11 Stéphane Le Roux 11 Youssouf Oualhadj 22 Mickael Randour 33
Pierre Vandenhove 1133

###### Abstract

For decades, two-player (antagonistic) games on graphs have been a framework
of choice for many important problems in theoretical computer science. A
notorious one is controller synthesis, which can be rephrased through the
game-theoretic metaphor as the quest for a winning strategy of the system in a
game against its antagonistic environment. Depending on the specification,
optimal strategies might be simple or quite complex, for example having to use
(possibly infinite) memory. Hence, research strives to understand which
settings allow for simple strategies.

In 2005, Gimbert and Zielonka [25] provided a complete characterization of
preference relations (a formal framework to model specifications and game
objectives) that admit memoryless optimal strategies for both players. In the
last fifteen years however, practical applications have driven the community
toward games with complex or multiple objectives, where memory — finite or
infinite — is almost always required. Despite much effort, the exact frontiers
of the class of preference relations that admit finite-memory optimal
strategies still elude us.

In this work, we establish a complete characterization of preference relations
that admit optimal strategies using arena-independent finite memory,
generalizing the work of Gimbert and Zielonka to the finite-memory case. We
also prove an equivalent to their celebrated corollary of utmost practical
interest: if both players have optimal (arena-independent-)finite-memory
strategies in all one-player games, then it is also the case in all two-player
games. Finally, we pinpoint the boundaries of our results with regard to the
literature: our work completely covers the case of arena-independent memory
(e.g., multiple parity objectives, lower- and upper-bounded energy
objectives), and paves the way to the arena-dependent case (e.g., multiple
lower-bounded energy objectives).

##  1 Introduction

Controller synthesis through the game-theoretic metaphor. Two-player games on
(finite) graphs are studied extensively, in particular for their application
to controller synthesis for reactive systems (see, e.g., [26, 33, 6, 2]). The
seminal model is antagonistic (i.e., zero-sum if one chooses a quantitative
view): player 1 ($\mathcal{P}_{1}$) is seen as the system to control, player 2
($\mathcal{P}_{2}$) as its antagonistic environment, and the game models their
interaction. Each vertex of the game graph (called arena) models a state of
the system and belongs to one of the players. Players take turns moving a
pebble from state to state according to the edges, each player choosing the
destination whenever the pebble is on one of his states. These choices are
made according to the strategy of the player, which, in general, might use
memory (bounded or not) of the past moves to prescribe the next action.

The resulting infinite sequence of states, called play, represents the
execution of the system. The objective of $\mathcal{P}_{1}$ is to enforce a
given specification, often encoded as a winning condition (i.e., a set of
winning plays) or as a payoff function to maximize (i.e., a quantitative
performance to optimize). This paradigm focuses on the worst-case performance
of the system, hence $\mathcal{P}_{2}$’s goal is to prevent $\mathcal{P}_{1}$
from achieving his objective.

The goal of synthesis is thus to decide if $\mathcal{P}_{1}$ has a winning
strategy, i.e., one ensuring a given winning condition or guaranteeing a given
payoff threshold, against all possible strategies of $\mathcal{P}_{2}$, and to
build such a strategy efficiently if it exists.

Winning strategies are essentially formal blueprints for controllers to
implement in practical applications. Therefore, the complexity of these
strategies is of tremendous importance: the simpler the strategy, the easier
and cheaper it will be to build the corresponding controller and maintain it.
This explains why a lot of research effort is constantly put in identifying
the exact complexity (in terms of memory and/or randomness) of strategies
needed to play optimally (i.e., to the best of the player’s ability) for each
specific class of games and objectives (e.g., [25, 16, 13, 38, 21, 9, 1, 4,
37, 5, 10]). Alongside the practical interest of this question lies the
theoretical puzzle: understanding the underlying mechanisms and implicit
properties of games that lead to “simple” strategies being sufficient. Given
the numerous connections between two-player games and various branches of
mathematics and computer science, this endeavor is undoubtedly of high
interest.

Preference relations. As hinted above, there are two prominent ways to
formalize a game objective in the literature. The first one, dubbed
quantitative and inspired by games in economics, is to use payoff functions
mapping plays to numerical values, and to see $\mathcal{P}_{1}$ as a maximizer
player. This is for example the case of mean-payoff games [18]. The second
one, called qualitative, is to define a set of winning plays — called winning
condition — induced by some property, as in, e.g., parity games [19, 39]. The
two formalisms are strongly linked: the classical decision problem for
quantitative games is to fix a payoff threshold and ask if $\mathcal{P}_{1}$
has a strategy to guarantee it, essentially transforming the problem into a
qualitative one (where the winning plays are all those achieving a payoff at
least equal to the threshold). To define payoff functions or winning
conditions, one often uses weights, priorities, colors, etc, on states or
edges of the arena.

In this work, we walk in the footsteps of Gimbert and Zielonka [25]: we
associate a color to each edge of our arenas, and we adopt the abstract
formalism of preference relations over infinite sequences of colors (induced
by plays). This general formalism permits to encode virtually all classical
game objectives, both qualitative and quantitative, and lets us reason in a
well-founded framework under minimal assumptions. See Example 1 for
illustrations of classical objectives encoded as preference relations.

Memoryless optimal strategies. Remarkably, several canonical classes of games
that have been around for decades and proved their usefulness over and over —
e.g., mean-payoff [18], parity [19, 39], or energy games [11] — share a
desirable property: they all admit memoryless optimal strategies for both
players. That is, for every strategy $\sigma_{i}$ of $\mathcal{P}_{i}$, there
is a strategy $\sigma^{\mathsf{ML}}_{i}$ which is at least as good (i.e., wins
whenever $\sigma_{i}$ wins or ensures at least the same payoff) and that uses
no memory at all. Such a memoryless strategy always picks the same edge when
in the same state, regardless of what happened before in the game.

Memoryless strategies are the simplest kind of strategies one can use in a
turn-based game on a graph. Therefore, it is quite interesting that they
suffice for objectives as rich as the ones we just discussed. Following this
observation, a lot of effort has been put in understanding which games admit
memoryless optimal strategies, and in identifying the exact frontiers of
memoryless determinacy. Let us mention, non-exhaustively, works by Gimbert and
Zielonka [24, 25] (culminating in a complete characterization), Aminof and
Rubin [1] (through the prism of first-cycle games), and Kopczynski [30] (half-
positional determinacy). All these advances were built by identifying the
common underlying mechanisms in ad hoc proofs for specific classes of games,
and generalizing them to wide classes (e.g., the first-cycle games of Aminof
and Rubin are inspired by the seminal paper of Ehrenfeucht and Mycielski on
mean-payoff games [18]).

Gimbert and Zielonka’s approach. Arguably, the most important result in this
direction is the complete characterization of preference relations admitting
memoryless optimal strategies, established in [25], fifteen years ago. By
complete characterization, we mean sufficient and necessary conditions on the
preference relations.

This result can be stated as follows: a preference relation admits memoryless
optimal strategies for both players on all arenas if and only if the relation
(used by $\mathcal{P}_{1}$) and its inverse (used by $\mathcal{P}_{2}$) are
monotone and selective. These concepts will be defined formally in Section
3.1, but let us give an intuition here. Roughly, a preference relation is
monotone if it is stable under prefix addition: that is, given two sequences
of colors such that one is strictly preferred to the other, it is impossible
to reverse this order of preference by adding the same prefix to both
sequences. Selectivity is similarly defined with regard to cycle mixing: if a
preference relation is selective, then, starting from two sequences of colors,
it is impossible to create a third one by mixing the first two in such a way
that the third one is strictly preferred to the first two. Observe that these
elegant notions coincide with the natural intuition that memoryless strategies
suffice if there is no interest in behaving differently in a state depending
on what happened before.

In addition to this complete characterization, Gimbert and Zielonka proved
another great result, of high interest in practice [25, Corollary 7]. As a by-
product of their approach, they obtain that if memoryless strategies suffice
in all one-player games of $\mathcal{P}_{1}$ and all one-player games of
$\mathcal{P}_{2}$, they also suffice in all two-player games. Such a lifting
corollary provides a neat and easy way to prove that a preference relation
admits memoryless optimal strategies without proving monotony and selectivity
at all: proving it in the two one-player subcases, which is generally much
easier as it boils down to graph reasoning, and then lifting the result to the
general two-player case through the corollary.

The rise of memory. Over the last decade, the increasing need to model complex
specifications has shifted research toward games where multiple (quantitative
and qualitative) objectives co-exist and interact, requiring the analysis of
interplay and trade-offs between several objectives. Hence, a lot of effort is
put in studying games where objectives are actually conjunctions of
objectives, or even richer Boolean combinations. See for example [15] for
combinations of parity, [12, 16, 29] for combinations of energy and parity,
[38] for combinations of mean-payoff, [5, 4] for combinations of energy and
average-energy, [10] for combinations of energy and mean-payoff, [13] for
combinations of total-payoff, or [13, 9, 7] for combinations of window
objectives.

When considering such rich objectives, memoryless strategies usually do not
suffice, and one has to use an amount of memory which can quickly become an
obstacle to implementation (e.g., exponential memory) or which can prevent it
completely (infinite memory). Establishing precise memory bounds for such
general combinations of objectives is tricky and sometimes counterintuitive.
For example, while energy games and mean-payoff games are inter-reducible in
the single-objective setting, exponential-memory strategies are both
sufficient and necessary for conjunctions of energy objectives [16, 29] while
infinite-memory strategies are required for conjunctions of mean-payoff ones
[38].

A natural question arises: which preference relations do admit finite-memory
optimal strategies? Surprisingly, whether an equivalent to Gimbert and
Zielonka’s characterization could be obtained in the finite-memory case or not
has remained an open question up to now. It is worth noticing that such an
equivalent could be of tremendous help in practice, especially if a lifting
corollary also holds: see for example [5, 4, 10], where proving that finite-
memory strategies suffice in one-player games was fairly easy, in contrast to
the high complexity of the two-player case — a lifting corollary could grant
the two-player case for free!

Having said that, one has to hope that the following corollary can be
established: “if finite-memory strategies suffice in all one-player games of
$\mathcal{P}_{1}$ and all one-player games of $\mathcal{P}_{2}$, they also
suffice in all two-player games.” Unfortunately, this hope is but a delusion.

Lifting corollary: a counterexample. Consider games where the colors are
integers, and the objective of $\mathcal{P}_{1}$ is to create a play such that
(a) the running sum of weights grows up to infinity (e.g., consider its
$\liminf$ to define it properly), or (b) this running sum of weights takes
value zero infinitely often. As this defines a qualitative objective, the
corresponding preference relation induces only two equivalence classes:
winning and losing plays. The inverse relation, used by $\mathcal{P}_{2}$, is
trivial to obtain. It is fairly easy to prove that $\mathcal{P}_{1}$ always
has finite-memory optimal strategies in his one-player games (i.e., games
where he owns all states), and so does $\mathcal{P}_{2}$ in his one-player
games. See Appendix 0.A for the details.

Now, consider the very simple two-player game depicted in Figure 1. First,
observe that $\mathcal{P}_{1}$ (circle) has an infinite-memory strategy to
win: $\mathcal{P}_{1}$ should keep track of the running sum of weights (which
is unbounded, hence the need for infinite memory) and loop in $s_{1}$ up to
the point where this sum hits zero, when $\mathcal{P}_{1}$ should then go to
$s_{2}$. This strategy ensures victory because either $\mathcal{P}_{2}$ always
goes back to $s_{1}$, in which case (b) is satisfied; or $\mathcal{P}_{2}$
eventually loops forever on $s_{2}$, in which case (a) is satisfied. It
remains to argue that $\mathcal{P}_{1}$ has no finite-memory winning strategy
in this game. This can be done using a standard argument: whatever the amount
of memory used by $\mathcal{P}_{1}$, $\mathcal{P}_{2}$ may loop in $s_{2}$
long enough as to exceed the bound up to which $\mathcal{P}_{1}$ can track the
sum accurately; thus dooming $\mathcal{P}_{1}$ to fail to reset the sum to
zero in $s_{1}$ infinitely often.

$s_{2}$$s_{1}$$1$$1$$-1$$-1$ Figure 1: $\mathcal{P}_{1}$ (circle) needs
infinite memory to win in this game (by always resetting the sum of weights to
zero by looping long enough in $s_{1}$ before going back to $s_{2}$), whereas
both players have finite-memory optimal strategies in all one-player games
using the same preference relations.

This modest example proves that Gimbert and Zielonka’s approach cannot work in
full generality in the finite-memory case, and for good reasons. Informally,
in this case, the corollary breaks down because of (the absence of some sort
of) monotony. Recall that a preference relation is monotone if no matter how
we reach a state (i.e., no matter the prefix), there is always one edge which
is the best to pick. In the case of memoryless strategies, as in [25],
$\mathcal{P}_{1}$ is already doomed in one-player games in the absence of
monotony: two prefixes to distinguish can be hardcoded as different paths
leading to the same state in a game arena, as if they were chosen by
$\mathcal{P}_{2}$ in a two-player game. In the case of finite-memory
strategies, however, the situation is different. In one-player games, the
number of such paths that can be hardcoded in an arena is always bounded,
hence finite memory might suffice to react, i.e., to keep track of which
prefix is the current one and how to behave accordingly. However, in two-
player games, $\mathcal{P}_{2}$ might create an infinite number of prefixes to
distinguish (using a cycle), thus requiring $\mathcal{P}_{1}$ to use infinite
memory to be able to do so. This is exactly what happens in the example above:
in any one-player game, the largest sum that $\mathcal{P}_{1}$ has to track is
bounded, whereas $\mathcal{P}_{2}$ can make this sum as large as he wants in
two-player games.

Our approach. In a nutshell, we generalize Gimbert and Zielonka’s results —
characterization and lifting corollary — to the case of arena-independent
finite memory. That is, we encompass all situations where the amount of memory
needed by the two players is solely dependent on the preference relation, and
not on the game arena. Let us take some classical examples to illustrate this
notion.

  * •

All memoryless-determined relations — studied in [25] — use arena-independent
memory: the amount of memory required, none, is the same for all arenas.

  * •

Combinations of parity objectives use arena-independent memory [15]: the
amount of memory only depends on the number of objectives and the number of
priorities — both parameters of the preference relation, not on the size of
the arena.

  * •

Lower- and upper-bounded energy objectives also use arena-independent memory
(see, e.g., [3, 5, 4]): the memory only depends on the bounds — parameters of
the preference relation, not on the size of the arena, nor the weights used in
it.

  * •

Combinations of lower-bounded energy objectives (with no upper bound) require
arena-dependent memory [16, 29]: the memory depends on the size of the arena
and the largest weight used in it. Such a setting falls outside the scope of
our results.

This informal concept of arena-independent memory is transparent in our work:
in all our results, we use memory skeletons — essentially Mealy machines
without a next-action function (Section 2) — that suffice for all arenas, and
that are at the basis of the strategies we build. A quick look at our main
concepts (Section 3.1) and results (Section 3.2) suffices to grasp the
formalism behind this intuition.

This restriction to arena-independent memory is natural given the
counterexample to a general approach presented above. It is also important to
note that it is not as restrictive as it may seem, as hinted by the examples
above: we are not restricted to constant memory but to memory only depending
on the parameters of the preference relation (or equivalently, objective), and
not of the arena. This framework thus already encompasses many objectives from
the literature, as well as possible extensions. We discuss this topic in more
details in Section 6, where we provide a precise description of the frontiers
of our results within the current research landscape.

We believe it should be possible to generalize our approach to some extent to
the arena-dependent case, through some function associating memory skeletons
to arenas. Again, the previous example proves that this would not hold in full
generality, but our hope is to establish conditions on this function (which is
induced by the preference relation) under which the approach would hold. We
leave this question open for now: this paper paves the way to this more
general setting.

Let us highlight however that the arena-independent case, which we solve here,
is an exact equivalent to Gimbert and Zielonka’s results in the finite-memory
case: the memoryless case is de facto arena-independent. Therefore, this paper
strictly generalizes [25] and captures lots of widely-studied classes of games
(Section 6).

Outline of our contributions. Informally, our complete characterization can be
stated as follows: given a preference relation and a memory skeleton
$\mathcal{M}$, both players have optimal finite-memory strategies based on
skeleton $\mathcal{M}$ in all games if and only if the relation and its
inverse are $\mathcal{M}$-monotone and $\mathcal{M}$-selective.

These last two concepts are keys to our approach. Intuitively, they correspond
to Gimbert and Zielonka’s monotony and selectivity, modulo a memory skeleton.
Recall that monotony and selectivity are related to stability of the
preference relation with regard to prefix addition and cycle mixing,
respectively. Our more general concepts of $\mathcal{M}$-monotony and
$\mathcal{M}$-selectivity serve the same purpose, but they only compare
sequences of colors that are deemed equivalent by the memory skeleton. For the
sake of illustration, take selectivity: it implies that one has no interest in
mixing different cycles of the game arena. For its generalization, the memory
skeleton is taken into account: $\mathcal{M}$-selectivity implies that one has
no interest in mixing cycles of the game arena that are read as cycles on the
same memory state in the skeleton $\mathcal{M}$.

Let us give a quick breakdown of our approach. In Section 2, we introduce all
basic notions, including the memory skeletons, and we establish several
technical results. Of particular importance is the discussion of optimal
strategies and Nash equilibria, their relationship, and their roles in our
approach.

Section 3 is dedicated to our characterization, and consists of three parts.
In Section 3.1, we introduce the concepts of $\mathcal{M}$-monotony and
$\mathcal{M}$-selectivity, cornerstones of our work. We also present two
essential tools to establish the characterization: prefix-covers and cyclic-
covers of arenas. Section 3.2 states formally our characterization (Theorem
3.1), as well as the corresponding lifting corollary (Corollary 1), from one-
player to two-player games, thus providing this coveted result of utmost
practical interest. We close this overview with an example of application, in
Section 3.3.

The proof of the characterization (Theorem 3.1) is split in two. In Section 4,
we establish the implication from (the sufficiency of) finite memory based on
$\mathcal{M}$ to $\mathcal{M}$-monotony (Theorem 4.1) and
$\mathcal{M}$-selectivity (Theorem 4.2) of the preference relation. The main
idea here is to build game arenas based on automata recognizing the languages
involved in the two concepts, and to use the existence of finite-memory
optimal strategies in these arenas to prove that $\mathcal{M}$-monotony and
$\mathcal{M}$-selectivity hold.

In Section 5, we prove the converse implication. We proceed in two steps,
first establishing the existence of memoryless optimal strategies in “covered”
arenas (Lemma 8 and Theorem 5.1), and then building on it to obtain the
existence of finite-memory optimal strategies in general arenas (Corollary 2).
The main technical tools we use are Nash equilibria and the aforementioned
notions of prefix-covers and cyclic-covers.

We close the paper with a discussion of our characterization, presented in
Section 6: we highlight some limitations and interesting features, compare its
scope with the current research landscape, and sketch directions for future
work.

Technical overview. Naturally, our technical approach is inspired by the one
of Gimbert and Zielonka for the memoryless case [25], which can actually be
rediscovered through our results using a trivial memory skeleton. Two of the
most important challenges we had to overcome were:

  1. 1.

establishing natural concepts of monotony and selectivity modulo memory that
are exactly as powerful as required to maintain a complete characterization
(i.e., sufficient and necessary conditions) in the finite-memory case;

  2. 2.

circumventing the seemingly unavoidable coupling between the memory skeleton
and the arena in the inductive argument needed to prove the implication from
$\mathcal{M}$-monotony and $\mathcal{M}$-selectivity to finite-memory optimal
strategies — which we were able to do using our notions of prefix-covers and
cyclic-covers.

All along our paper, we highlight the similarities and discrepancies between
our work and Gimbert and Zielonka’s [25]. Whenever possible, we also go
further, using weaker hypotheses and proving stronger results, along with
addressing core problems left untouched in [25] (e.g., the role of the zero-
sum hypothesis). In that respect, we hope to shed a new light on the seminal
results of [25] and offer a comprehensive, strongly-motivated generalization
of high practical interest.

Related work. We already discussed the most important related papers, notably
[25]. Let us highlight here some works where similar approaches have been
considered to establish “meta-theorems” applying to general classes of games.
First and foremost is the determinacy theorem by Martin that guarantees
determinacy (without considering the complexity of strategies) for Borel
winning conditions [31].

Following the same motivation as our work — the need to characterize
(combinations of) objectives admitting finite-memory optimal strategies, Le
Roux et al. [37] take another road: whereas our work permits to lift results
from one-player games to two-player games, they provide a lifting from the
single-objective case to the multi-objective one.

Our work focuses on deterministic turn-based two-player games. Sufficient
conditions exist for stochastic models but to the best of our knowledge, no
complete characterization is known, even for the simplest case of Markov
decision processes (e.g., [23]). Whether part of our approach can be useful in
this context, or in richer contexts mixing games and stochastic models (e.g.,
[8]) is a question for future research. Some sufficient criteria, orthogonal
to our approach, were studied for concurrent games in [35].

Acknowledgments. We extend our warmest thanks to Mathieu Sassolas, for
inspiring discussions that were essential in starting this work.

##  2 Preliminaries

Automata and languages of colors. Let $C$ be an arbitrary set of colors.

We recall classical notions on automata on finite words. A _non-deterministic
finite-state automaton (NFA)_ is a tuple
$\mathcal{N}=(Q,B,\delta,Q_{\mathsf{init}},Q_{\mathsf{fin}})$, where $Q$ is a
finite set of states, $B\subseteq C$ is a finite alphabet of colors,
$\delta\subseteq Q\times B\times Q$ is a set of transitions,
$Q_{\mathsf{init}}\subseteq Q$ is a set of initial states, and
$Q_{\mathsf{fin}}\subseteq Q$ is a set of final states. Given a state $q\in Q$
and a word $w\in B^{*}$, we denote by $\widehat{\delta}(q,w)$ the set of
states that can be reached from $q$ after reading $w$. Without loss of
generality, we assume all NFAs to be coaccessible, i.e., for all $q\in Q$,
there exists $w\in B^{\ast}$, such that $\widehat{\delta}(q,w)\cap
Q_{\mathsf{fin}}\neq\emptyset$. Recall that NFAs precisely recognize regular
languages.

For any finite subset $B\subseteq C$, we denote by $\textsf{Reg}(B)$ the set
of all regular languages over $B$. Let
$\mathcal{R}(C)=\bigcup_{B\,\subseteq\,C,\,|B|<\infty}\textsf{Reg}(B),$ that
is, all the regular languages built over $C$.

Let $K\subseteq C^{*}$ be a language of finite words. We denote by
$\textsf{Prefs}(K)$ the set of all prefixes of the words in $K$. We define the
set of infinite words $[K]=\\{w=c_{1}c_{2}\ldots{}\in
C^{\omega}\mid\forall\,n\geq 1,\,c_{1}\ldots{}c_{n}\in\textsf{Prefs}(K)\\},$
which contains all infinite words for which every finite prefix is a prefix of
a word in $K$. Intuitively, if $K$ is regular, language $[K]$ corresponds to
all the infinite words that can be read on an automaton for $K$: we will
formalize this in Lemma 2.

The following observation, already noted in [25], will come in handy too.

###### Lemma 1

Let $K_{1},K_{2}\subseteq C^{*}$. Then $[K_{1}\cup K_{2}]=[K_{1}]\cup[K_{2}]$.

###### Proof

Let $w\in[K_{1}\cup K_{2}]$. Every finite prefix of $w$ is in
$\textsf{Prefs}(K_{1}\cup K_{2})$. Assume w.l.o.g. that infinitely many
prefixes of $w$ are in $\textsf{Prefs}(K_{1})$. This implies that _all_
prefixes of $w$ are in $\textsf{Prefs}(K_{1})$ (intuitively, because there is
a continuity in the prefix relation). Hence, $w\in[K_{1}]\cup[K_{2}]$.

Now, let $w\in[K_{1}]\cup[K_{2}]$. If $w\in[K_{1}]$ (resp. $[K_{2}]$), every
finite prefix of $w$ is in $\textsf{Prefs}(K_{1})$ (resp.
$\textsf{Prefs}(K_{2})$), so in particular it is in $\textsf{Prefs}(K_{1}\cup
K_{2})$. Hence, $w\in[K_{1}\cup K_{2}]$.∎

Arenas. We consider two players: player 1 ($\mathcal{P}_{1}$) and player 2
($\mathcal{P}_{2}$). An _arena_ is a tuple $\mathcal{A}=(S_{1},S_{2},E)$ such
that $S=S_{1}\uplus S_{2}$ (disjoint union) is a finite set of _states_
partitioned into states of $\mathcal{P}_{1}$ ($S_{1}$) and $\mathcal{P}_{2}$
($S_{2}$), and $E\subseteq S\times C\times S$ is a finite set of _edges_. Let
$\mathsf{col}\colon E\to C$ be the projection of edges to colors and
$\mathsf{\widehat{col}}$ its natural extension to sequences of edges. For an
edge $e\in E$, we use $\mathsf{in}(e)$ and $\mathsf{out}(e)$ to denote its
starting state and arrival state respectively, i.e.,
$e=(\mathsf{in}(e),\mathsf{col}(e),\mathsf{out}(e))$. We assume all arenas to
be non-blocking, i.e., for all $s\in S$, there exists $e\in E$ such that
$\mathsf{in}(e)=s$.

Let $\mathsf{Hists}(\mathcal{A},s)$ denote the set of histories in
$\mathcal{A}$ from initial state $s\in S$, i.e., finite sequences of edges
$\rho=e_{1}\ldots{}e_{n}\in E^{+}$ such that $\mathsf{in}(e_{1})=s$ and for
all $i$, $1\leq i<n$, $\mathsf{out}(e_{i})=\mathsf{in}(e_{i+1})$. Let
$\mathsf{Plays}(\mathcal{A},s)$ denote the set of plays in $\mathcal{A}$ from
initial state $s\in S$, i.e., infinite sequences of edges
$\pi=e_{1}e_{2}\ldots{}\in E^{\omega}$ such that $\mathsf{in}(e_{1})=s$ and
for all $i\geq 1$, $\mathsf{out}(e_{i})=\mathsf{in}(e_{i+1})$. We write
$\mathsf{Hists}(\mathcal{A},S^{\prime})$ and
$\mathsf{Plays}(\mathcal{A},S^{\prime})$ for the unions over subsets of
initial states $S^{\prime}\subseteq S$, and write
$\mathsf{Hists}(\mathcal{A})$ and $\mathsf{Plays}(\mathcal{A})$ for the unions
over all states of $\mathcal{A}$.

Let $\rho=e_{1}\ldots e_{n}\in\mathsf{Hists}(\mathcal{A})$ (resp.
$\pi=e_{1}e_{2}\ldots\in\mathsf{Plays}(\mathcal{A})$): we extend the operator
$\mathsf{in}$ to histories (resp. plays) by identifying $\mathsf{in}(\rho)$
(resp. $\mathsf{in}(\pi)$) to $\mathsf{in}(e_{1})$. We proceed similarly for
$\mathsf{out}$ and histories: $\mathsf{out}(\rho)=\mathsf{out}(e_{n})$. For
the sake of convenience, we consider that any set
$\mathsf{Hists}(\mathcal{A},s)$ contains the empty history $\lambda_{s}$ such
that $\mathsf{in}(\lambda_{s})=\mathsf{out}(\lambda_{s})=s$. We write
$\mathsf{Hists}_{i}(\mathcal{A},s)$ and $\mathsf{Hists}_{i}(\mathcal{A})$ for
the subsets of histories $\rho$ such that $\mathsf{out}(\rho)\in S_{i}$,
$i\in\\{1,2\\}$, i.e., histories whose last state belongs to
$\mathcal{P}_{i}$.

For any set of histories $H\subseteq\mathsf{Hists}(\mathcal{A})$, we write
$\mathsf{\widehat{col}}(H)$ for its projection to colors, i.e.,
$\mathsf{\widehat{col}}(H)=\\{\mathsf{\widehat{col}}(\rho)\mid\rho\in H\\}$.
We do the same for sets of plays.

Memory skeletons. A _memory skeleton_ is a tuple
$\mathcal{M}=(M,m_{\mathsf{init}},\alpha_{\mathsf{upd}})$ where $M$ is a
finite set of states, $m_{\mathsf{init}}\in M$ is a fixed initial state and
$\alpha_{\mathsf{upd}}\colon M\times C\to M$ is an update function. We write
$\widehat{\alpha_{\mathsf{upd}}}$ for the natural extension of
$\alpha_{\mathsf{upd}}$ to sequences of colors in $C^{\ast}$. Note that memory
skeletons are deterministic and might have an infinite number of transitions,
in contrast to NFAs.

Let $\mathcal{M}=(M,m_{\mathsf{init}},\alpha_{\mathsf{upd}})$ be a memory
skeleton. For $m,m^{\prime}\in M$, we define the language
$L_{m,m^{\prime}}=\left\\{w\in
C^{\ast}\mid\widehat{\alpha_{\mathsf{upd}}}(m,w)=m^{\prime}\right\\}$ that
contains all words that can be read from $m$ to $m^{\prime}$ in $\mathcal{M}$.

Let $\mathcal{M}^{1}=(M^{1},m_{\mathsf{init}}^{1},\alpha_{\mathsf{upd}}^{1})$
and $\mathcal{M}^{2}=(M^{2},m_{\mathsf{init}}^{2},\alpha_{\mathsf{upd}}^{2})$
be two memory skeletons. We define their product
$\mathcal{M}^{1}\otimes\mathcal{M}^{2}$ as the memory skeleton
$\mathcal{M}=(M,m_{\mathsf{init}},\alpha_{\mathsf{upd}})$ obtained as follows:
$M=M^{1}\times M^{2}$,
$m_{\mathsf{init}}=(m_{\mathsf{init}}^{1},m_{\mathsf{init}}^{2})$, and, for
all $m^{1}\in M^{1}$, $m^{2}\in M^{2}$, $c\in C$,
$\alpha_{\mathsf{upd}}((m^{1},m^{2}),c)=(\alpha_{\mathsf{upd}}^{1}(m^{1},c),\alpha_{\mathsf{upd}}^{2}(m^{2},c))$.
That is, the memories are updated in parallel when a color is read.

Product arenas. Let $\mathcal{A}=(S_{1},S_{2},E)$ be an arena and
$\mathcal{M}=(M,m_{\mathsf{init}},\alpha_{\mathsf{upd}})$ be a memory
skeleton. We define their product $\mathcal{A}\ltimes\mathcal{M}$ as the arena
$(S_{1}^{\prime},S_{2}^{\prime},E^{\prime})$ where $S_{1}^{\prime}=S_{1}\times
M$, $S_{2}^{\prime}=S_{2}\times M$, and $E^{\prime}\subseteq S^{\prime}\times
C\times S^{\prime}$, with $S^{\prime}=S_{1}^{\prime}\uplus S_{2}^{\prime}$, is
such that $((s_{1},m_{1}),c,(s_{2},m_{2}))\in E^{\prime}$ if and only if
$(s_{1},c,s_{2})\in E$ and $\alpha_{\mathsf{upd}}(m_{1},c)=m_{2}$. That is,
the memory is updated according to the colors of the edges in $E$. Note that
even though $\mathcal{M}$ might contain an infinite number of transitions
since $C$ might be infinite, $\mathcal{A}\ltimes\mathcal{M}$ is always finite,
as $E$ is finite in $\mathcal{A}$. Since we assume arena $\mathcal{A}$ is non-
blocking, it is also the case of arena $\mathcal{A}\ltimes\mathcal{M}$.

Arena induced by an NFA. Let
$\mathcal{N}=(Q,B,\delta,Q_{\mathsf{init}},Q_{\mathsf{fin}})$ be an NFA. We
say that a state $q\in Q$ is essential if there exists an infinite path in
$\mathcal{N}$ starting in $q$. Let $Q_{\mathsf{ess}}=\\{q\in Q\mid q\text{ is
essential}\\}$. We define the corresponding one-player arena
$\mathsf{Arena}(\mathcal{N})=(S_{1}=Q_{\mathsf{ess}},S_{2}=\emptyset,E\subseteq
Q_{\mathsf{ess}}\times B\times Q_{\mathsf{ess}})$, where
$e=(q,c,q^{\prime})\in E$ if $(q,c,q^{\prime})\in\delta$. Intuitively,
$\mathsf{Arena}(\mathcal{N})$ transforms $\mathcal{N}$ into a non-blocking
arena thanks to the restriction to essential states.

We may now state formally the link between $[K]$ and the underlying automaton
for $K$. Our proof is similar to [25, Lemma 4].

###### Lemma 2

Let $\mathcal{N}=(Q,B,\delta,Q_{\mathsf{init}},Q_{\mathsf{fin}})$ be a
(coaccessible) NFA recognizing the regular language $K\subseteq C^{\ast}$. Let
$Q_{\mathsf{init}}^{\prime}=Q_{\mathsf{init}}\cap Q_{\mathsf{ess}}$. The
following equality holds:

$[K]=\mathsf{\widehat{col}}\big{(}\mathsf{Plays}\left(\mathsf{Arena}(\mathcal{N}),Q_{\mathsf{init}}^{\prime}\right)\big{)}.$

In particular, $[K]$ is non-empty if and only if there exists an essential
initial state in $\mathcal{N}$.

###### Proof

If $Q_{\mathsf{init}}^{\prime}$ is empty, the equality trivially holds:
$\mathsf{\widehat{col}}\big{(}\mathsf{Plays}\left(\mathsf{Arena}(\mathcal{N}),Q_{\mathsf{init}}^{\prime}\right)\big{)}$
and $[K]$ are both empty. Hence, from now on, we assume
$Q_{\mathsf{init}}^{\prime}\neq\emptyset$.

We start with the left-to-right inclusion. Let $w=c_{1}c_{2}\ldots\in[K]$. We
first prove that for all $n\geq 1$, it holds that

$c_{1}\ldots
c_{n}\in\mathsf{\widehat{col}}\big{(}\mathsf{Hists}\left(\mathsf{Arena}(\mathcal{N}),Q_{\mathsf{init}}^{\prime}\right)\big{)}.$

We assume on the contrary that there exists $n\geq 1$ such that $c_{1}\ldots
c_{n}\notin\mathsf{\widehat{col}}\big{(}\mathsf{Hists}\left(\mathsf{Arena}(\mathcal{N}),Q_{\mathsf{init}}^{\prime}\right)\big{)}$.
As $\mathsf{Arena}(\mathcal{N})$ is a restriction of the states of
$\mathcal{N}$ to $Q_{\mathsf{ess}}$, this means that no matter how
$c_{1}\ldots c_{n}$ is read on $\mathcal{N}$, it goes through a state in
$Q\setminus Q_{\mathsf{ess}}$. As there is no infinite path from these states,
this contradicts that $w\in[K]$; there cannot be arbitrarily long prefixes
starting with $c_{1}\ldots c_{n}$.

We now use the property that we have just proved along with König’s lemma to
show that
$w\in\mathsf{\widehat{col}}\big{(}\mathsf{Plays}\left(\mathsf{Arena}(\mathcal{N}),Q_{\mathsf{init}}^{\prime}\right)\big{)}$.
We build a forest of trees $\mathcal{F}$. The vertices of $\mathcal{F}$ are
paths
$\rho\in\mathsf{Hists}\left(\mathsf{Arena}(\mathcal{N}),Q_{\mathsf{init}}^{\prime}\right)$
such that $\mathsf{\widehat{col}}(\rho)$ is a prefix of $w$ and
$\mathsf{in}(\rho)\in Q_{\mathsf{init}}^{\prime}$. For every $q\in
Q_{\mathsf{init}}^{\prime}$, there is one tree in $\mathcal{F}$ whose root is
the empty path $\lambda_{q}$. There is a transition from a vertex $\rho$ to a
vertex $\rho^{\prime}$ if there exists $e\in E$ such that $\rho\cdot
e=\rho^{\prime}$. As there is at least one vertex for each prefix $c_{1}\ldots
c_{n}$, (at least) one of the trees of $\mathcal{F}$ must be infinite.
Moreover, $\mathcal{F}$ is finitely branching. By König’s lemma, we obtain
that there must be an infinite path $\pi$ starting from a root $\lambda_{q}$
for some $q\in Q_{\mathsf{init}}^{\prime}$. By construction,
$\mathsf{\widehat{col}}(\pi)=w$, so
$w\in\mathsf{\widehat{col}}\big{(}\mathsf{Plays}\left(\mathsf{Arena}(\mathcal{N}),Q_{\mathsf{init}}^{\prime}\right)\big{)}$.

We now prove the right-to-left inclusion. Let
$\pi=e_{1}e_{2}\ldots\in\mathsf{Plays}\left(\mathsf{Arena}(\mathcal{N}),Q_{\mathsf{init}}^{\prime}\right)$.
For $n\geq 1$, the word $\mathsf{\widehat{col}}(e_{1}\ldots e_{n})$ is the
color of a path in $\mathcal{N}$, since every edge of
$\mathsf{Arena}(\mathcal{N})$ corresponds to a transition of $\mathcal{N}$. As
$\mathcal{N}$ is coaccessible, there is a path in $\mathcal{N}$ from the state
corresponding to $\mathsf{out}(e_{n})$ to a final state in $Q_{\mathsf{fin}}$.
Thus, the word $\mathsf{\widehat{col}}(e_{1}\ldots e_{n})$ is a prefix of an
accepted word of $\mathcal{N}$, i.e., a prefix of a word in $K$; as this holds
for all $n\geq 1$, we obtain that $\mathsf{\widehat{col}}(\pi)\in[K]$.∎

Strategies. A strategy $\sigma_{i}$ for $\mathcal{P}_{i}$, $i\in\\{1,2\\}$, on
arena $\mathcal{A}=(S_{1},S_{2},E)$, is a function
$\sigma_{i}\colon\mathsf{Hists}_{i}(\mathcal{A})\to E$ such that for all
$\rho\in\mathsf{Hists}_{i}(\mathcal{A})$,
$\mathsf{in}(\sigma_{i}(\rho))=\mathsf{out}(\rho)$. Let
$\Sigma_{i}(\mathcal{A})$ be the set of all strategies of $\mathcal{P}_{i}$ on
$\mathcal{A}$.

A finite-memory strategy $\sigma_{i}$ is a strategy that can be encoded as a
Mealy machine, i.e., a memory skeleton
$\mathcal{M}=(M,m_{\mathsf{init}},\alpha_{\mathsf{upd}})$ with transitions
over a finite subset of colors $B\subseteq C$, enriched with a next-action
function $\alpha_{\mathsf{nxt}}\colon M\times S_{i}\to E$ such that for all
$m\in M$, $s\in S_{i}$, $\mathsf{in}(\alpha_{\mathsf{nxt}}(m,s))=s$. Given a
Mealy machine $\Gamma_{\sigma_{i}}=(\mathcal{M},\alpha_{\mathsf{nxt}})$,
strategy $\sigma_{i}$ is defined as follows:

  * •

$\forall\,s\in
S_{i},\,\sigma_{i}(\lambda_{s})=\alpha_{\mathsf{nxt}}(m_{\mathsf{init}},s)$,

  * •

$\forall\,\rho\cdot e\in\mathsf{Hists}_{i}(\mathcal{A})$, $e\in E$,
$\sigma_{i}(\rho\cdot
e)=\alpha_{\mathsf{nxt}}\left(\widehat{\alpha_{\mathsf{upd}}}\left(m_{\mathsf{init}},\mathsf{\widehat{col}}\left(\rho\cdot
e\right)\right),\mathsf{out}(e)\right)$.

We denote by $\Sigma^{\mathsf{FM}}_{i}(\mathcal{A})$ the set of all finite-
memory strategies of $\mathcal{P}_{i}$ on $\mathcal{A}$. We say that a
strategy $\sigma_{i}\in\Sigma^{\mathsf{FM}}_{i}(\mathcal{A})$ is based on
memory skeleton $\mathcal{M}$ if it can be encoded as a Mealy machine
$\Gamma_{\sigma_{i}}=(\mathcal{M},\alpha_{\mathsf{nxt}})$, as above. We always
implicitly assume that strategies of $\Sigma^{\mathsf{FM}}_{i}(\mathcal{A})$
are built by restricting the transitions of their skeleton $\mathcal{M}$ to
the actual subset of colors appearing in $\mathcal{A}$. A strategy
$\sigma_{i}$ is memoryless if it is a function $\sigma_{i}\colon S_{i}\to E$,
or equivalently, if its Mealy machine uses only one state. We denote by
$\Sigma^{\mathsf{ML}}_{i}(\mathcal{A})$ the set of all memoryless strategies
of $\mathcal{P}_{i}$ on $\mathcal{A}$.

We denote by $\mathsf{Plays}(\mathcal{A},s,\sigma_{i})$ the set of plays
consistent with a strategy $\sigma_{i}$ of $\mathcal{P}_{i}$ from an initial
state $s$, i.e., all plays
$\pi=e_{1}e_{2}\ldots\in\mathsf{Plays}(\mathcal{A},s)$ such that for all
prefixes $\rho=e_{1}\ldots e_{n}$, $\mathsf{out}(\rho)\in
S_{i}\implies\sigma_{i}(\rho)=e_{n+1}$. We write
$\mathsf{Plays}(\mathcal{A},s,\sigma_{1},\sigma_{2})$ for the singleton set
containing the unique play consistent with a couple of strategies for the two
players. We use similar notations for histories.

Preference relations. Let $\sqsubseteq$ be a total preorder on $C^{\omega}$,
called _preference relation_. We consider antagonistic games, where the
objective of $\mathcal{P}_{1}$ is to create the best possible play with regard
to $\sqsubseteq$ whereas the objective of $\mathcal{P}_{2}$ is to obtain the
worst possible one. That is, $\mathcal{P}_{2}$ uses the inverse relation
${\sqsubseteq}^{-1}$. This corresponds to zero-sum games when using a
quantitative framework.

Given $w,w^{\prime}\in C^{\omega}$, we write $w\sqsubset w^{\prime}$ if we
have $\neg(w^{\prime}\sqsubseteq w)$ since the preorder is total. We extend
the relation $\sqsubseteq$ to subsets of $C^{\omega}$ as follows: for
$W,W^{\prime}\subseteq C^{\omega}$,

$W\sqsubseteq W^{\prime}\iff\forall\,w\in W,\,\exists\,w^{\prime}\in
W^{\prime},\,w\sqsubseteq w^{\prime}.$

We also write

$W\sqsubset W^{\prime}\iff\exists\,w^{\prime}\in W^{\prime},\,\forall\,w\in
W,\,w\sqsubset w^{\prime}.$

Note that $W\sqsubset W^{\prime}$ if and only if $\neg(W^{\prime}\sqsubseteq
W)$.

We sometimes compare words $w\in C^{\omega}$ with languages $K\subseteq
C^{\omega}$, by simply identifying word $w$ to its singleton language
$\\{w\\}$.

Games. A _game_ is a tuple $\mathcal{G}=(\mathcal{A},\sqsubseteq)$ where
$\mathcal{A}$ is an arena and $\sqsubseteq$ is a preference relation. As
discussed in Section 1, all the classical objectives from the literature (both
qualitative and quantitative) can be expressed in the general framework of
preference relations.

###### Example 1

There are two prominent ways to formalize game objectives in the literature:
through payoff functions and through winning conditions. We take an example of
each.

First, consider (lim inf) mean-payoff games [18]. In this setting, colors are
integers, i.e., $C=\mathbb{Z}$, and the goal of $\mathcal{P}_{1}$ is to create
a play $\pi$, with $w=\mathsf{\widehat{col}}(\pi)=c_{1}c_{2}\ldots{}$,
maximizing the following payoff function:

$\mathsf{MP}(w)=\liminf_{n\rightarrow\infty}\dfrac{1}{n}\sum_{i=1}^{n}c_{i}.$

Such a payoff function induces a natural preference relation
$\sqsubseteq_{\mathsf{MP}}$ between sequences of colors as follows: for all
$w,w^{\prime}\in C^{\omega}$, $w\sqsubseteq_{\mathsf{MP}}w^{\prime}$ if and
only if $\mathsf{MP}(w)\leq\mathsf{MP}(w^{\prime})$. Such quantitative games
are zero-sum, hence $\mathcal{P}_{2}$ uses the natural inverse relation
$\sqsubseteq_{\mathsf{MP}}^{-1}$: he is a minimizer player in the payoff
formulation of these games.

Second, consider reachability games (e.g., [20]). In this setting, only two
colors are needed: one for edges in the target set, and one for the other
edges. Let us use $\top$ and $\bot$ respectively to color these two sets of
edges, i.e., $C=\\{\top,\bot\\}$. Then, the winning condition can be simply
written as $W=\\{w\in C^{\omega}\mid\top\in w\\}\subsetneq C^{\omega}$. In
such games, the goal of $\mathcal{P}_{1}$ is to create a play $\pi$ such that
$\mathsf{\widehat{col}}(\pi)\in W$, called winning play. Defining a
corresponding preference relation $\sqsubseteq_{\mathsf{reach}}$ is
straightforward: for all $w,w^{\prime}\in C^{\omega}$,
$w\sqsubset_{\mathsf{reach}}w^{\prime}$ if and only if $w^{\prime}\in W$ and
$w\not\in W$. That is, $\sqsubseteq_{\mathsf{reach}}$ defines two equivalence
classes: losing and winning plays. This qualitative setting is antagonistic,
hence $\mathcal{P}_{2}$ uses the inverse relation
$\sqsubseteq_{\mathsf{reach}}^{-1}$: his winning condition is
$\overline{W}=C^{\omega}\setminus W$ in the classical formulation of these
games.

As explained in Section 1, quantitative games are often reduced to qualitative
ones by fixing a threshold to achieve. $\lhd$

Optimal strategies. Let $\mathcal{G}=(\mathcal{A},\sqsubseteq)$ be a game on
arena $\mathcal{A}=(S_{1},S_{2},E)$. Given a $\mathcal{P}_{i}$-strategy
$\sigma_{i}\in\Sigma_{i}(\mathcal{A})$ and a state $s\in S$, we define

$\displaystyle\mathsf{UCol}_{\sqsubseteq}(\mathcal{A},s,\sigma_{i})$
$\displaystyle=\\{w\in
C^{\omega}\mid\exists\,\sigma_{3-i}\in\Sigma_{3-i}(\mathcal{A}),\,\mathsf{\widehat{col}}(\mathsf{Plays}(\mathcal{A},s,\sigma_{1},\sigma_{2}))\sqsubseteq
w\\},$ $\displaystyle\mathsf{DCol}_{\sqsubseteq}(\mathcal{A},s,\sigma_{i})$
$\displaystyle=\\{w\in
C^{\omega}\mid\exists\,\sigma_{3-i}\in\Sigma_{3-i}(\mathcal{A}),\,w\sqsubseteq\mathsf{\widehat{col}}(\mathsf{Plays}(\mathcal{A},s,\sigma_{1},\sigma_{2}))\\}.$

Note that
$\mathsf{DCol}_{\sqsubseteq}(\mathcal{A},s,\sigma_{i})=\mathsf{UCol}_{{\sqsubseteq}^{-1}}(\mathcal{A},s,\sigma_{i})$.
Intuitively, $\mathsf{UCol}_{\sqsubseteq}$ and $\mathsf{DCol}_{\sqsubseteq}$
represent the upward and downward closures of sequences of colors (consistent
with a strategy) with respect to the preference relation.

Taking the standpoint of $\mathcal{P}_{1}$, we say that a strategy
$\sigma_{1}\in\Sigma_{1}(\mathcal{A})$ is at least as good as a strategy
$\sigma^{\prime}_{1}\in\Sigma_{1}(\mathcal{A})$ from a state $s\in S$ if

$\mathsf{UCol}_{\sqsubseteq}(\mathcal{A},s,\sigma_{1})\subseteq\mathsf{UCol}_{\sqsubseteq}(\mathcal{A},s,\sigma^{\prime}_{1}).$

Intuitively, $\sigma_{1}$ is at least as good as $\sigma^{\prime}_{1}$ if the
“worst-case” plays consistent with $\sigma_{1}$ are at least as good as the
ones consistent with $\sigma^{\prime}_{1}$. The $\mathsf{UCol}$ operator is
useful to define this notion properly even in the case where there is no
“worst-case” play for a strategy (i.e., if the infimum used in the classical
quantitative setting is not reached). Similar notions have been used before,
e.g., in [34].

Symmetrically, for $\mathcal{P}_{2}$, we say that a strategy
$\sigma_{2}\in\Sigma_{2}(\mathcal{A})$ is at least as good as a strategy
$\sigma^{\prime}_{2}\in\Sigma_{2}(\mathcal{A})$ from a state $s\in S$ if

$\mathsf{DCol}_{\sqsubseteq}(\mathcal{A},s,\sigma_{2})\subseteq\mathsf{DCol}_{\sqsubseteq}(\mathcal{A},s,\sigma^{\prime}_{2}).$

Now, we say that a strategy $\sigma_{i}\in\Sigma_{i}(\mathcal{A})$ of
$\mathcal{P}_{i}$ is optimal from a state $s\in S$, aka $s$-optimal, if it is
at least as good as every other strategy
$\sigma^{\prime}_{i}\in\Sigma_{i}(\mathcal{A})$ from $s$. We extend this
notation to subsets of states in the natural way, and we say that a strategy
$\sigma_{i}$ is uniformly-optimal if it is $S$-optimal.

The goal of our paper is to characterize the preference relations that admit
uniformly-optimal finite-memory (UFM) strategies in all arenas. We also
discuss the simpler case of uniformly-optimal memoryless (UML) strategies,
which corresponds to the subset of preference relations studied by Gimbert and
Zielonka [25].

In that respect, the following link is important to observe.

###### Lemma 3

Let $\mathcal{G}=(\mathcal{A},\sqsubseteq)$ be a game on arena
$\mathcal{A}=(S_{1},S_{2},E)$. Let
$\mathcal{M}=(M,m_{\mathsf{init}},\alpha_{\mathsf{upd}})$ be a memory skeleton
and let $\sigma_{i}\in\Sigma^{\mathsf{FM}}_{i}(\mathcal{A})$ be a finite-
memory strategy encoded by the Mealy machine
$\Gamma_{\sigma_{i}}=(\mathcal{M},\alpha_{\mathsf{nxt}})$. Then, $\sigma_{i}$
is a UFM strategy in $\mathcal{G}$ if and only if $\alpha_{\mathsf{nxt}}$
corresponds to an $(S\times\\{m_{\mathsf{init}}\\})$-optimal memoryless
strategy in
$\mathcal{G}^{\prime}=(\mathcal{A}\ltimes\mathcal{M},\sqsubseteq)$.

###### Proof

We first aim to define a bijection
$\mathcal{H}\colon\mathsf{Hists}(\mathcal{A})\to\mathsf{Hists}(\mathcal{A}\ltimes\mathcal{M},S\times\\{m_{\mathsf{init}}\\})$.
Let $\rho=e_{1}\ldots e_{n}\in\mathsf{Hists}(\mathcal{A})$, with
$e_{j}=(s_{j},c_{j},s_{j+1})$. We set $m_{1}=m_{\mathsf{init}}$, and for
$2\leq j\leq n$, $m_{j}=\alpha_{\mathsf{upd}}(m_{j-1},c_{j})$. We define
$e_{j}^{\prime}=((s_{j},m_{j}),c_{j},(s_{j+1},m_{j+1}))$, and
$\mathcal{H}(\rho)=e_{1}^{\prime}\ldots e_{n}^{\prime}$. Notice that
$\mathsf{\widehat{col}}(\mathcal{H}(\rho))=\mathsf{\widehat{col}}(\rho)$.
Furthermore, $\mathcal{H}$ is bijective; as the initial state of the memory
$m_{\mathsf{init}}$ is fixed and the memory skeleton is deterministic, the
memory states added to $\rho$ to obtain $\mathcal{H}(\rho)$ are uniquely
determined.

We now show that there is a correspondence between strategies of
$\Sigma_{i}(\mathcal{A})$ and strategies of
$\Sigma_{i}(\mathcal{A}\ltimes\mathcal{M})$: intuitively, augmenting the arena
with the skeleton allows some strategies to be played using less memory, but
does not fundamentally change each player’s possibilities. We define a
function
$f\colon\Sigma_{i}(\mathcal{A})\to\Sigma_{i}(\mathcal{A}\ltimes\mathcal{M})$.
For $\tau_{i}\in\Sigma_{i}(\mathcal{A})$ and
$\rho^{\prime}\in\mathsf{Hists}_{i}(\mathcal{A}\ltimes\mathcal{M})$ with
$\mathsf{in}(\rho^{\prime})\in S\times\\{m_{\mathsf{init}}\\}$ and
$\mathsf{out}(\rho^{\prime})=(s,m)\in S_{i}\times M$, if
$\tau_{i}({\mathcal{H}}^{-1}(\rho^{\prime}))=(s,c,s^{\prime})$, we define
$f(\tau_{i})(\rho^{\prime})=((s,m),c,(s^{\prime},\alpha_{\mathsf{upd}}(m,c)))$.
The histories induced by strategies $\tau_{i}$ and $f(\tau_{i})$ correspond:
if $\rho={\mathcal{H}}^{-1}(\rho^{\prime})$, then we have

$\mathcal{H}(\rho\cdot\tau_{i}(\rho))=\rho^{\prime}\cdot(f(\tau_{i})(\rho^{\prime})).$
(1)

We are only interested in the behavior of strategies of
$\Sigma_{i}(\mathcal{A}\ltimes\mathcal{M})$ on histories $\rho^{\prime}$ with
$\mathsf{in}(\rho^{\prime})\in S\times\\{m_{\mathsf{init}}\\}$ (in what
follows, we will only consider histories and plays starting in such states).
If we restrict the image of $f$ to the set of strategies
$\tau_{i}^{\prime}\colon\mathsf{Hists}_{i}(\mathcal{A}\ltimes\mathcal{M},S\times\\{m_{\mathsf{init}}\\})\to
E^{\prime}$, then $f$ is a bijection.

Consider the next-action function $\alpha_{\mathsf{nxt}}$ of strategy
$\sigma_{i}$. Formally, we have to transform $\alpha_{\mathsf{nxt}}$ into a
proper memoryless strategy in
$\Sigma^{\mathsf{ML}}_{i}(\mathcal{A}\ltimes\mathcal{M})$. This can be done
through the bijection $f$, yielding the memoryless strategy
$\alpha_{\mathsf{nxt}}^{\prime}=f(\sigma_{i})$, which corresponds to
$\alpha_{\mathsf{nxt}}$ interpreted over the product arena, and well-defined
for all histories starting in $S\times\\{m_{\mathsf{init}}\\}$.

We now show a second fact related to $f$: we have that for all $s\in S$, for
all $\tau_{1}\in\Sigma_{1}(\mathcal{A})$,
$\tau_{2}\in\Sigma_{2}(\mathcal{A})$,

$\mathsf{\widehat{col}}\big{(}\mathsf{Plays}(\mathcal{A},s,\tau_{1},\tau_{2})\big{)}=\mathsf{\widehat{col}}\big{(}\mathsf{Plays}(\mathcal{A}\ltimes\mathcal{M},(s,m_{\mathsf{init}}),f(\tau_{1}),f(\tau_{2}))\big{)}.$
(2)

This can easily be proved by induction using Equation (1). Indeed, at each
step, both strategy $\tau_{1}$ (resp. $\tau_{2}$) and strategy $f(\tau_{1})$
(resp. $f(\tau_{2})$) pick an edge with the same color.

We finish the proof assuming that
$\sigma_{i}=\sigma_{1}\in\Sigma^{\mathsf{FM}}_{1}(\mathcal{A})$; the proof is
symmetric for $\mathcal{P}_{2}$. Equation (2) implies that for all $s\in S$,
$\tau_{1}\in\Sigma_{1}(\mathcal{A})$,

$\displaystyle\mathsf{UCol}_{\sqsubseteq}(\mathcal{A},s,\tau_{1})$
$\displaystyle=\\{w\in
C^{\omega}\mid\exists\,\tau_{2}\in\Sigma_{2}(\mathcal{A}),\,\mathsf{\widehat{col}}\big{(}\mathsf{Plays}(\mathcal{A},s,\tau_{1},\tau_{2})\big{)}\sqsubseteq
w\\}$ $\displaystyle=\\{w\in
C^{\omega}\mid\exists\,\tau_{2}\in\Sigma_{2}(\mathcal{A}),\,\mathsf{\widehat{col}}\big{(}\mathsf{Plays}(\mathcal{A}\ltimes\mathcal{M},(s,m_{\mathsf{init}}),f(\tau_{1}),f(\tau_{2}))\big{)}\sqsubseteq
w\\}$ $\displaystyle=\\{w\in
C^{\omega}\mid\exists\,\tau_{2}^{\prime}\in\Sigma_{2}(\mathcal{A}\ltimes\mathcal{M}),\,\mathsf{\widehat{col}}\big{(}\mathsf{Plays}(\mathcal{A}\ltimes\mathcal{M},(s,m_{\mathsf{init}}),f(\tau_{1}),\tau_{2}^{\prime})\big{)}\sqsubseteq
w\\}$
$\displaystyle=\mathsf{UCol}_{\sqsubseteq}(\mathcal{A}\ltimes\mathcal{M},(s,m_{\mathsf{init}}),f(\tau_{1})).$
(3)

where the penultimate equality uses that the aforementioned restriction of $f$
is bijective.

Using Equation (2), we can obtain that a strategy $\tau_{1}$ is uniformly-
optimal in $\mathcal{G}=(\mathcal{A},\sqsubseteq)$ if and only if
$f(\tau_{1})\in\Sigma_{1}(\mathcal{A}\ltimes\mathcal{M})$ is
$(S\times\\{m_{\mathsf{init}}\\})$-optimal in
$\mathcal{G}^{\prime}=(\mathcal{A}\ltimes\mathcal{M},\sqsubseteq)$. In
particular, $\sigma_{1}$ is uniformly-optimal in $\mathcal{G}$ if and only if
$f(\sigma_{1})=\alpha_{\mathsf{nxt}}^{\prime}$ is
$(S\times\\{m_{\mathsf{init}}\\})$-optimal in $\mathcal{G}^{\prime}$. ∎

Nash equilibria. We use Nash equilibria [32] as tools to establish the
existence of optimal strategies in some of our proofs. Let
$\mathcal{G}=(\mathcal{A},\sqsubseteq)$ be a game on arena
$\mathcal{A}=(S_{1},S_{2},E)$. Formally, a Nash equilibrium (NE) from a state
$s\in S$ is a couple of strategies
$(\sigma_{1},\sigma_{2})\in\Sigma_{1}(\mathcal{A})\times\Sigma_{2}(\mathcal{A})$
such that, for all $\sigma^{\prime}_{1}\in\Sigma_{1}(\mathcal{A})$,
$\sigma^{\prime}_{2}\in\Sigma_{2}(\mathcal{A})$,

$\mathsf{\widehat{col}}(\mathsf{Plays}(\mathcal{A},s,\sigma^{\prime}_{1},\sigma_{2}))\sqsubseteq\mathsf{\widehat{col}}(\mathsf{Plays}(\mathcal{A},s,\sigma_{1},\sigma_{2}))\sqsubseteq\mathsf{\widehat{col}}(\mathsf{Plays}(\mathcal{A},s,\sigma_{1},\sigma^{\prime}_{2})).$
(4)

Similarly to optimal strategies, we call an NE uniform if it is an NE from all
states $s\in S$.

It is worth taking a moment to discuss the link between optimal strategies and
Nash equilibria in our specific context of antagonistic games. Both notions
seem closely related, and indeed, in [25], Gimbert and Zielonka did choose
Equation (4) — i.e., the definition of a Nash equilibrium — as their
definition of a pair of optimal strategies. This could lead the reader to
believe that both notions coincide. However, they do not in full generality,
as we discuss in the following.

Additionally, defining optimality for a pair of strategies gives rise to
difficulties as one naturally wants to reason about optimal strategies of a
player without talking about the (possibly optimal) strategy of its adversary.
Our definition of optimal strategy has the advantage of giving a clear and
precise definition that does not involve the standpoint of the adversary.

As stated before, the ultimate goal of our paper is to characterize preference
relations that admit finite-memory optimal strategies, but Nash equilibria
will serve as tools in our endeavor. Let us establish two interesting
properties of Nash equilibria in antagonistic games.

First, it is possible to mix different Nash equilibria.

###### Lemma 4

Let $\mathcal{G}=(\mathcal{A},\sqsubseteq)$ be a game on arena
$\mathcal{A}=(S_{1},S_{2},E)$, and let $s\in S$ be a state. Let
$(\sigma^{a}_{1},\sigma^{a}_{2})$ and
$(\sigma^{b}_{1},\sigma^{b}_{2})\in\Sigma_{1}(\mathcal{A})\times\Sigma_{2}(\mathcal{A})$
be two Nash equilibria from $s$. Then, $(\sigma^{a}_{1},\sigma^{b}_{2})$ is
also a Nash equilibrium from $s$.

###### Proof

We need to prove that for all $\sigma^{\prime}_{1}\in\Sigma_{1}(\mathcal{A})$,
$\sigma^{\prime}_{2}\in\Sigma_{2}(\mathcal{A})$,

$\mathsf{\widehat{col}}(\mathsf{Plays}(\mathcal{A},s,\sigma^{\prime}_{1},\sigma^{b}_{2}))\sqsubseteq\mathsf{\widehat{col}}(\mathsf{Plays}(\mathcal{A},s,\sigma^{a}_{1},\sigma^{b}_{2}))\sqsubseteq\mathsf{\widehat{col}}(\mathsf{Plays}(\mathcal{A},s,\sigma^{a}_{1},\sigma^{\prime}_{2})).$
(5)

Since $(\sigma^{a}_{1},\sigma^{a}_{2})$ is an NE, we know that

$\mathsf{\widehat{col}}(\mathsf{Plays}(\mathcal{A},s,\sigma^{b}_{1},\sigma^{a}_{2}))\sqsubseteq\mathsf{\widehat{col}}(\mathsf{Plays}(\mathcal{A},s,\sigma^{a}_{1},\sigma^{a}_{2}))\sqsubseteq\mathsf{\widehat{col}}(\mathsf{Plays}(\mathcal{A},s,\sigma^{a}_{1},\sigma^{b}_{2})),$

instantiating $\sigma^{\prime}_{1}$ and $\sigma^{\prime}_{2}$ to
$\sigma_{1}^{b}$ and $\sigma^{b}_{2}$ respectively in Equation (4). Similarly,
since $(\sigma^{b}_{1},\sigma^{b}_{2})$ is an NE, we know that

$\mathsf{\widehat{col}}(\mathsf{Plays}(\mathcal{A},s,\sigma^{a}_{1},\sigma^{b}_{2}))\sqsubseteq\mathsf{\widehat{col}}(\mathsf{Plays}(\mathcal{A},s,\sigma^{b}_{1},\sigma^{b}_{2}))\sqsubseteq\mathsf{\widehat{col}}(\mathsf{Plays}(\mathcal{A},s,\sigma^{b}_{1},\sigma^{a}_{2})),$

instantiating $\sigma^{\prime}_{1}$ and $\sigma^{\prime}_{2}$ to
$\sigma_{1}^{a}$ and $\sigma^{a}_{2}$ respectively in Equation (4).

Now it is easy to see from the last two lines that all six sequences of colors
are equivalent under $\sqsubseteq$ as the inequalities form a cycle. Hence,
since Equation (4) holds for $(\sigma^{a}_{1},\sigma^{a}_{2})$ and
$(\sigma^{b}_{1},\sigma^{b}_{2})$, and since
$\mathsf{\widehat{col}}(\mathsf{Plays}(\mathcal{A},s,\sigma^{a}_{1},\sigma^{b}_{2}))$
is $\sqsubseteq$-equivalent to both
$\mathsf{\widehat{col}}(\mathsf{Plays}(\mathcal{A},s,\sigma^{a}_{1},\sigma^{a}_{2}))$
and
$\mathsf{\widehat{col}}(\mathsf{Plays}(\mathcal{A},s,\sigma^{b}_{1},\sigma^{b}_{2}))$,
Equation (5) is trivially verified. That concludes our proof.∎

###### Remark 1

Lemma 4 crucially relies on the assumption (transparent in our definition of
Nash equilibrium) that we consider antagonistic games, that is,
$\mathcal{P}_{2}$ uses the inverse preference relation ${\sqsubseteq}^{-1}$.
Actually, our approach almost completely carries over to the general case
where $\mathcal{P}_{1}$ and $\mathcal{P}_{2}$ use two different, unrelated,
preference relations: the single breaking point being the use of Lemma 4 in
Theorem 5.1 to preserve memoryless Nash equilibria in the induction step.
$\lhd$

We now establish that Nash equilibria induce optimal strategies (again, in our
antagonistic context).

###### Lemma 5

Let $\mathcal{G}=(\mathcal{A},\sqsubseteq)$ be a game on arena
$\mathcal{A}=(S_{1},S_{2},E)$, and let $s\in S$ be a state. Let
$(\sigma_{1},\sigma_{2})\in\Sigma_{1}(\mathcal{A})\times\Sigma_{2}(\mathcal{A})$
be a Nash equilibrium from $s$. Then, both $\sigma_{1}$ and $\sigma_{2}$ are
$s$-optimal strategies.

###### Proof

We do the proof for $\mathcal{P}_{1}$ (it works symmetrically for
$\mathcal{P}_{2}$). Let
$(\sigma_{1},\sigma_{2})\in\Sigma_{1}(\mathcal{A})\times\Sigma_{2}(\mathcal{A})$
be a Nash equilibrium from $s\in S$. Consider the rightmost inequality of
Equation (4). From it, we deduce that

$\mathsf{UCol}_{\sqsubseteq}(\mathcal{A},s,\sigma_{1})=\\{w\in
C^{\omega}\mid\mathsf{\widehat{col}}(\mathsf{Plays}(\mathcal{A},s,\sigma_{1},\sigma_{2}))\sqsubseteq
w\\}.$ (6)

Indeed, $\sigma_{2}$ is the best response [32] to $\sigma_{1}$.

We claim that $\sigma_{1}$ is at least as good as every other strategy, hence
that $\sigma_{1}$ is optimal. Let
$\sigma^{\prime}_{1}\in\Sigma_{1}(\mathcal{A})$. We need to prove that
$\mathsf{UCol}_{\sqsubseteq}(\mathcal{A},s,\sigma_{1})\subseteq\mathsf{UCol}_{\sqsubseteq}(\mathcal{A},s,\sigma^{\prime}_{1})$.
Let $w\in\mathsf{UCol}_{\sqsubseteq}(\mathcal{A},s,\sigma_{1})$. From Equation
(6) and the leftmost inequality of Equation (4), we have
$\mathsf{\widehat{col}}(\mathsf{Plays}(\mathcal{A},s,\sigma^{\prime}_{1},\sigma_{2}))\sqsubseteq
w$. Hence, by definition,
$w\in\mathsf{UCol}_{\sqsubseteq}(\mathcal{A},s,\sigma^{\prime}_{1})$, which
concludes our proof.∎

As noted above, optimal strategies do not always coincide with Nash
equilibria. Intuitively, they do coincide in the classical quantitative
formulation (using payoff functions) if the value of the game exists, that is,
if the best payoff that $\mathcal{P}_{1}$ can guarantee is equal to the worst
payoff that $\mathcal{P}_{2}$ can guarantee [32]. In a sense, our concepts of
$\mathsf{UCol}_{\sqsubseteq}$ and $\mathsf{DCol}_{\sqsubseteq}$ are meant to
mimic the classical $\sup\inf$ and $\inf\sup$ formulations in our abstract
context where objectives are described as preference relations.

So (quantitative) games do not always have a value, and similarly, in our
context, optimal strategies as defined above do not always induce a Nash
equilibrium. That being said, they do for arguably all reasonable preference
relations, as Martin’s determinacy result grants the existence of winning
strategies — in our formalism, Nash equilibria — for all Borel winning
conditions [31]. That is, for the equivalence to fail, we would need a
preference relation capable of inducing non-Borel sets of winning plays (once
a threshold is chosen).

###### Remark 2

The main contribution of our paper is an equivalence between the existence of
UFM strategies (based on $\mathcal{M}$) and upcoming notions of
$\mathcal{M}$-monotony and $\mathcal{M}$-selectivity of the relation. It is
worth noting that we only need optimal strategies in the left-to-right
direction (Theorem 4.1 and Theorem 4.2) — and not the stronger notion of Nash
equilibrium — while we do prove the existence of finite-memory Nash equilibria
in the other direction (Theorem 5.1 and Corollary 2). That is, whenever
possible, we use the weakest hypothesis and prove the strongest result. $\lhd$

###### Remark 3

In one-player games, the two visions — optimal strategies and Nash equilibria
— coincide. $\lhd$

###### Remark 4

Lemma 3 can be restated in terms of Nash equilibria, using a similar
reasoning. $\lhd$

##  3 Characterization

We are now able to establish our characterization of preference relations
admitting finite-memory optimal strategies. We proceed in three steps. First,
in Section 3.1, we present the core concepts of this characterization, i.e.,
the properties that preference relations must verify to yield UFM strategies.
Second, we state our equivalence result in Section 3.2, alongside a corollary
of utmost practical importance that lets one lift results from the one-player
case to the two-player one. We defer the formal proofs of both directions of
the equivalence to Section 4 and Section 5, and only explain here how to
combine them. Finally, we provide an illustrative application of our
characterization in Section 3.3.

###  3.1 Concepts

Generalizing monotony and selectivity. As discussed in Section 1, Gimbert and
Zielonka’s characterization [25] relies on notions of monotony and selectivity
of the preference relation. One of the main stumbling blocks to lift their
characterization to the finite-memory case was finding natural counterparts to
these notions that would capture the additional intricacy of this more general
setting.

Intuitively, one huge difference between Gimbert and Zielonka’s technical
approach and ours is the following. In the memoryless setting, all the
reasoning can be abstracted away from the underlying arena and done at the
level of sequences of colors. In the finite-memory one, however, one has to
pay attention to how sequences of colors are composed and compared, to
maintain integrity with regard to the memory and the underlying game arena. In
a sense, this need to intertwine abstract reasoning on arbitrary sequences of
colors with concrete tracking of memory updates has been a constant obstacle
that prevented the emergence of a complete characterization since Gimbert and
Zielonka’s result in 2005. This issue can be observed in related works, as
discussed in Section 1, along with partial answers to the problem (e.g.,
[37]).

Much of our effort was thus spent on trying to define concepts that would
preserve the elegance of monotony and selectivity while allowing us to lift
the theory to the finite-memory case. As often the case in these endeavors,
the good concepts turned out to be the most natural ones, capturing the
intuitive idea that one needs monotony and selectivity modulo a memory
skeleton.

######  Definition 1 ($\mathcal{M}$-monotony)

Let $\mathcal{M}=(M,m_{\mathsf{init}},\alpha_{\mathsf{upd}})$ be a memory
skeleton. A preference relation $\sqsubseteq$ is $\mathcal{M}$-_monotone_ if
for all $m\in M$, for all $K_{1},K_{2}\in\mathcal{R}(C)$,

$\exists\,w\in
L_{m_{\mathsf{init}},m},\,[wK_{1}]\sqsubset[wK_{2}]\implies\forall\,w^{\prime}\in
L_{m_{\mathsf{init}},m},\,[w^{\prime}K_{1}]\sqsubseteq[w^{\prime}K_{2}].$ (7)

Recall that a memory skeleton $\mathcal{M}$ has a fixed initial state
$m_{\mathsf{init}}$. Intuitively, $\mathcal{M}$-monotony extends Gimbert and
Zielonka’s monotony by asking one to compare prefixes belonging to the same
language $L_{m_{\mathsf{init}},m}$, that is, prefixes that are deemed
equivalent by the memory skeleton. This property roughly captures that
$\sqsubseteq$ is stable with regard to prefix addition, for memory-equivalent
prefixes.

Observe that the original monotony notion is exactly equivalent to our
$\mathcal{M}$-monotony if $\mathcal{M}$ is a trivial memory skeleton with only
one state: that is, the memoryless case is naturally a specific subcase of our
framework.

######  Definition 2 ($\mathcal{M}$-selectivity)

Let $\mathcal{M}=(M,m_{\mathsf{init}},\alpha_{\mathsf{upd}})$ be a memory
skeleton. A preference relation $\sqsubseteq$ is $\mathcal{M}$-_selective_ if
for all $w\in C^{*}$,
$m=\widehat{\alpha_{\mathsf{upd}}}(m_{\mathsf{init}},w)$, for all
$K_{1},K_{2}\in\mathcal{R}(C)$ such that $K_{1},K_{2}\subseteq L_{m,m}$, for
all $K_{3}\in\mathcal{R}(C)$,

$[w(K_{1}\cup
K_{2})^{*}K_{3}]\sqsubseteq[wK_{1}^{*}]\cup[wK_{2}^{*}]\cup[wK_{3}].$ (8)

Similarly, $\mathcal{M}$-selectivity extends Gimbert and Zielonka’s
selectivity by asking one to compare sequences of colors belonging to the same
language $L_{m,m}$, that is, sequences read as cycles on the memory skeleton.
Note also that the memory state $m$ should be consistent with the prefix $w$
read from the initial memory state $m_{\mathsf{init}}$. This property roughly
captures that $\sqsubseteq$ is stable with regard to cycle mixing, for memory-
equivalent cycles.

Again, observe that the original selectivity notion is exactly equivalent to
our $\mathcal{M}$-selectivity if $\mathcal{M}$ is a trivial memory skeleton
with only one state.

Our notions respect the natural intuition that access to additional memory
should always be helpful: if a skeleton $\mathcal{M}$ is sufficient to
classify sequences of colors in a way that guarantees $\mathcal{M}$-monotony
and $\mathcal{M}$-selectivity, then it should also be the case for “more
powerful” skeletons.

###### Lemma 6

Let $\mathcal{M}$ and $\mathcal{M}^{\prime}$ be two memory skeletons. If
$\sqsubseteq$ is $\mathcal{M}$-monotone (resp. $\mathcal{M}$-selective) then,
it is also $(\mathcal{M}\otimes\mathcal{M}^{\prime})$-monotone (resp.
$(\mathcal{M}\otimes\mathcal{M}^{\prime})$-selective).

###### Proof

We write $\mathcal{M}=(M,m_{\mathsf{init}},\alpha_{\mathsf{upd}})$ and
$\mathcal{M}^{\prime}=(M^{\prime},m_{\mathsf{init}}^{\prime},\alpha_{\mathsf{upd}}^{\prime})$.

Let us assume that $\sqsubseteq$ is $\mathcal{M}$-monotone, that is, for all
$m\in M$, for all $K_{1},K_{2}\in\mathcal{R}(C)$,

$\exists\,w\in
L_{m_{\mathsf{init}},m},\,[wK_{1}]\sqsubset[wK_{2}]\implies\forall\,w^{\prime}\in
L_{m_{\mathsf{init}},m},\,[w^{\prime}K_{1}]\sqsubseteq[w^{\prime}K_{2}].$ (9)

We show that $\sqsubseteq$ is
$(\mathcal{M}\otimes\mathcal{M}^{\prime})$-monotone, that is, for all
$(m,m^{\prime})\in M\times M^{\prime}$, for all
$K_{1},K_{2}\in\mathcal{R}(C)$,

$\exists\,w\in
L_{(m_{\mathsf{init}},m_{\mathsf{init}}^{\prime}),(m,m^{\prime})},\,[wK_{1}]\sqsubset[wK_{2}]\implies\forall\,w^{\prime}\in
L_{(m_{\mathsf{init}},m_{\mathsf{init}}^{\prime}),(m,m^{\prime})},\,[w^{\prime}K_{1}]\sqsubseteq[w^{\prime}K_{2}].$
(10)

To do so, we notice that
$L_{(m_{\mathsf{init}},m_{\mathsf{init}}^{\prime}),(m,m^{\prime})}\subseteq
L_{m_{\mathsf{init}},m}$ (the product of memory skeletons simply updates both
memories in parallel). Thus, if the premise of Equation (10) holds, we obtain
by Equation (9) that the conclusion of Equation (10) also holds.

A similar argument can be laid out to show that $\mathcal{M}$-selectivity
implies $(\mathcal{M}\otimes\mathcal{M}^{\prime})$-selectivity. It is enough
to notice that for all $(m,m^{\prime})\in M\times M^{\prime}$, we have
$L_{(m,m^{\prime}),(m,m^{\prime})}\subseteq L_{m,m}$: the definition of
$\mathcal{M}$-selectivity is thus clearly stronger than the definition of
$(\mathcal{M}\otimes\mathcal{M}^{\prime})$-selectivity.∎

Prefix-covers and cyclic-covers. While the aforementioned concepts of
$\mathcal{M}$-monotony and $\mathcal{M}$-selectivity are the primordial ones
for stating the characterization, we still need two additional notions to
prove it.

Let us sketch the issue here already. To prove that monotone and selective
preference relations yield UML strategies, Gimbert and Zielonka deploy an
inductive argument on the number of choices in an arena. Intuitively, we want
to use a similar approach for UFM strategies, but because of the unavoidable
coupling between the memory skeleton and the arena (e.g., Lemma 3), the
induction argument breaks, as adding one choice in the arena results in adding
many in the product arena (as many as there are memory states), where the
reasoning needs to take place.

To solve this issue, we decouple the two aspects (see Section 5). Intuitively,
we first establish that, on arenas that inherently share the same good
properties as product arenas (that is, they already “classify” prefixes and
cycles as the memory would), we can deploy the induction argument and obtain
UML strategies. Then, we obtain the result for UFM strategies on general
arenas as a corollary. The crux is identifying such “good” arenas: this is
done through the following notions.

######  Definition 3 (Prefix-covers and cyclic-covers)

Let $\mathcal{M}=(M,m_{\mathsf{init}},\alpha_{\mathsf{upd}})$ be a memory
skeleton and $\mathcal{A}=(S_{1},S_{2},E)$ be an arena. Let
$S_{\mathsf{cov}}\subseteq S$.

We say that $\mathcal{M}$ is a prefix-cover of $S_{\mathsf{cov}}$ in
$\mathcal{A}$ if for all $s\in S$, there exists $m_{s}\in M$ such that, for
all $\rho\in\mathsf{Hists}(\mathcal{A})$ such that $\mathsf{in}(\rho)\in
S_{\mathsf{cov}}$ and $\mathsf{out}(\rho)=s$,
$\widehat{\alpha_{\mathsf{upd}}}(m_{\mathsf{init}},\mathsf{\widehat{col}}(\rho))=m_{s}$.

We say that $\mathcal{M}$ is a cyclic-cover of $S_{\mathsf{cov}}$ in
$\mathcal{A}$ if for all $\rho\in\mathsf{Hists}(\mathcal{A})$ such that
$\mathsf{in}(\rho)\in S_{\mathsf{cov}}$, if $s=\mathsf{out}(\rho)$ and
$m=\widehat{\alpha_{\mathsf{upd}}}(m_{\mathsf{init}},\mathsf{\widehat{col}}(\rho))$,
for all $\rho^{\prime}\in\mathsf{Hists}(\mathcal{A})$ such that
$\mathsf{in}(\rho^{\prime})=\mathsf{out}(\rho^{\prime})=s$,
$\widehat{\alpha_{\mathsf{upd}}}(m,\mathsf{\widehat{col}}(\rho^{\prime}))=m$.

Intuitively, $\mathcal{M}$ is a prefix-cover for a set of states
$S_{\mathsf{cov}}$ if the histories starting in $S_{\mathsf{cov}}$ and ending
in a given state $s\in S$ are read up to the same memory state in the memory
skeleton. Similarly, $\mathcal{M}$ is a cyclic-cover of $\mathcal{A}$ if the
cycles of $\mathcal{A}$ are read as cycles in the memory skeleton, once the
memory has been initialized properly.

As hinted above, the canonical example of a prefix-covered and cyclic-covered
arena is a product arena (but many more may be in this case, hence it is
beneficial to be general with these concepts).

###### Lemma 7

Let $\mathcal{M}=(M,m_{\mathsf{init}},\alpha_{\mathsf{upd}})$ be a memory
skeleton and $\mathcal{A}=(S_{1},S_{2},E)$ be an arena. Then $\mathcal{M}$ is
both a prefix-cover and a cyclic-cover for
$S_{\mathsf{cov}}=S\times\\{m_{\mathsf{init}}\\}$ in the product arena
$\mathcal{A}\ltimes\mathcal{M}$.

###### Proof

The main argument that we will be using in this proof is that if there is a
history $\rho$ with $\mathsf{in}(\rho)=(s,m)$ and
$\mathsf{out}(\rho)=(s^{\prime},m^{\prime})$ in the product arena
$\mathcal{A}\ltimes\mathcal{M}$, then reading $\mathsf{\widehat{col}}(\rho)$
from $m$ in the memory skeleton $\mathcal{M}$ leads to $m^{\prime}$ (i.e.,
$\widehat{\alpha_{\mathsf{upd}}}(m,\mathsf{\widehat{col}}(\rho))=m^{\prime}$).
This can be easily proved by induction on the length of $\rho$, thanks to how
the product arena is built.

We first show that $\mathcal{M}$ is a prefix-cover for
$S_{\mathsf{cov}}=S\times\\{m_{\mathsf{init}}\\}$ in the product arena
$\mathcal{A}\ltimes\mathcal{M}$. What we have to prove, instantiating the
definition of prefix-cover in this case, is that for all $(s,m)\in S\times M$,
there exists $m_{(s,m)}\in M$ such that, for all
$\rho\in\mathsf{Hists}(\mathcal{A}\ltimes\mathcal{M})$ such that
$\mathsf{in}(\rho)\in S_{\mathsf{cov}}$ and $\mathsf{out}(\rho)=(s,m)$,
$\widehat{\alpha_{\mathsf{upd}}}(m_{\mathsf{init}},\mathsf{\widehat{col}}(\rho))=m_{(s,m)}$.
Let $(s,m)\in M$; we take $m_{(s,m)}=m$. Then, if
$\rho\in\mathsf{Hists}(\mathcal{A}\ltimes\mathcal{M})$ is such that
$\mathsf{in}(\rho)\in S_{\mathsf{cov}}$ (that is, is equal to
$(s^{\prime},m_{\mathsf{init}})$ for some $s^{\prime}\in S$), and
$\mathsf{out}(\rho)=(s,m)$, we have by construction of the product arena that
$\widehat{\alpha_{\mathsf{upd}}}(m_{\mathsf{init}},\mathsf{\widehat{col}}(\rho))=m=m_{(s,m)}$,
as required.

To prove that $\mathcal{M}$ is a cyclic-cover for $S_{\mathsf{cov}}$ in
$\mathcal{A}\ltimes\mathcal{M}$, we have to prove that for all
$\rho\in\mathsf{Hists}(\mathcal{A}\ltimes\mathcal{M})$ such that
$\mathsf{in}(\rho)\in S_{\mathsf{cov}}$, if $(s,m)=\mathsf{out}(\rho)$ and
$m^{\prime}=\widehat{\alpha_{\mathsf{upd}}}(m_{\mathsf{init}},\mathsf{\widehat{col}}(\rho))$,
for all $\rho^{\prime}\in\mathsf{Hists}(\mathcal{A}\ltimes\mathcal{M})$ such
that $\mathsf{in}(\rho^{\prime})=\mathsf{out}(\rho^{\prime})=(s,m)$,
$\widehat{\alpha_{\mathsf{upd}}}(m^{\prime},\mathsf{\widehat{col}}(\rho^{\prime}))=m^{\prime}$.
Let $\rho\in\mathsf{Hists}(\mathcal{A}\ltimes\mathcal{M})$ such that
$\mathsf{in}(\rho)\in S_{\mathsf{cov}}$ (that is,
$\mathsf{in}(\rho)=(s^{\prime},m_{\mathsf{init}})$ for some $s^{\prime}\in
S$). Then, if $(s,m)=\mathsf{out}(\rho)$, we have by construction of the
product arena that
$m^{\prime}=\widehat{\alpha_{\mathsf{upd}}}(m_{\mathsf{init}},\mathsf{\widehat{col}}(\rho))=m$.
Let $\rho^{\prime}\in\mathsf{Hists}(\mathcal{A}\ltimes\mathcal{M})$ such that
$\mathsf{in}(\rho^{\prime})=\mathsf{out}(\rho^{\prime})=(s,m)$. By
construction of the product arena, we therefore have that
$\widehat{\alpha_{\mathsf{upd}}}(m,\mathsf{\widehat{col}}(\rho^{\prime}))=m$,
as required.∎

###  3.2 Main results

Equivalence. We now have the necessary ingredients to state our general
equivalence result formally.

######  Theorem 3.1 (Equivalence)

Let $\sqsubseteq$ be a preference relation and let $\mathcal{M}$ be a memory
skeleton. Then, both players have UFM strategies based on memory skeleton
$\mathcal{M}$ in all games $\mathcal{G}=(\mathcal{A},\sqsubseteq)$ if and only
if $\sqsubseteq$ and ${\sqsubseteq}^{-1}$ are $\mathcal{M}$-monotone and
$\mathcal{M}$-selective.

We state this theorem broadly and with a focus on UFM strategies. The actual
results we have for each direction of the equivalence — which we develop in
Section 4 and Section 5 — are a bit stronger, of wider applicability and/or
more interesting, but this statement carries the take-home message of our
work. It is also meant to mirror the seminal result of Gimbert and Zielonka
[25, Theorem 2]: their result can be retrieved from Theorem 3.1 by taking the
trivial memory skeleton with only one state, which can be written as
$\mathcal{M}_{\mathsf{triv}}=(M=\\{m_{\mathsf{init}}\\},m_{\mathsf{init}},\alpha_{\mathsf{upd}}\colon\\{m_{\mathsf{init}}\\}\times
C\to\\{m_{\mathsf{init}}\\})$. As such, our work brings a strict
generalization of Gimbert and Zielonka’s results [25] to the finite-memory
case.

###### Remark 5

Recall Remark 2: in the following sections, we will break down Theorem 3.1
into different results that are always stated using the weakest hypotheses and
granting the strongest conclusions. For example, we can actually guarantee
Nash equilibria, not only optimal strategies (Theorem 5.1 and Corollary 2).
Similarly, we study the two implications of the equivalence in a compositional
way: we split the reasoning for $\mathcal{M}$-monotony and
$\mathcal{M}$-selectivity, using different skeletons for each whenever
meaningful, as well as for the players, again when beneficial. Additionally,
we distinguish between arenas where the players do not need memory and the
ones where they do, the first essentially being arenas that already share the
good properties of product arenas (as in “product with a memory skeleton”).

While such a level of care is not necessary to obtain Theorem 3.1, it has two
advantages. First, from a practical standpoint, it permits to obtain more
useful results when focusing on a particular direction of the equivalence (as
often the case in applications). Second, from a theoretical standpoint, it
permits to isolate each concept and each element of the reasoning and to
highlight their true roles in the underlying mechanisms that lead to the
existence of UFM strategies. $\lhd$

To prove Theorem 3.1, we invoke the results we will prove in Section 4 and
Section 5.

######  Proof (Theorem 3.1)

The left-to-right implication trivially follows from Theorem 4.1 (for
$\mathcal{M}$-monotony) and Theorem 4.2 (for $\mathcal{M}$-selectivity),
applied to each player with respect to his preference relation. The converse
implication is established in Corollary 2, which can be restated in terms of
UFM strategies through Lemma 5.∎

Lifting corollary. As discussed in Section 1, the work of Gimbert and Zielonka
contains not one, but two great results. Alongside the aforementioned
equivalence result, Gimbert and Zielonka provide a corollary of utmost
practical interest [25, Corollary 7]: they essentially obtain as a by-product
of their approach that if memoryless strategies suffice in all one-player
games of $\mathcal{P}_{1}$ and all one-player games of $\mathcal{P}_{2}$, they
also suffice in all two-player games.

This provides an elegant way to prove that a preference relation (or
equivalently an objective) admits memoryless optimal strategies without
proving monotony and selectivity at all: proving it in the two one-player
subcases, which is generally much easier as it boils down to graph reasoning,
and then lifting the result to the general two-player case through the
corollary.

Again, we are able to lift this corollary to the finite-memory case, as
follows.

###### Corollary 1

Let $\sqsubseteq$ be a preference relation and
$\mathcal{M}_{1},\mathcal{M}_{2}$ be two memory skeletons. Assume that

  1. 1.

for all one-player arenas $\mathcal{A}=(S_{1},S_{2}=\emptyset,E)$,
$\mathcal{P}_{1}$ has a UFM strategy
$\sigma_{1}\in\Sigma^{\mathsf{FM}}_{1}(\mathcal{A})$ based on memory skeleton
$\mathcal{M}_{1}$ in $\mathcal{G}=(\mathcal{A},\sqsubseteq)$;

  2. 2.

for all one-player arenas $\mathcal{A}=(S_{1}=\emptyset,S_{2},E)$,
$\mathcal{P}_{2}$ has a UFM strategy
$\sigma_{2}\in\Sigma^{\mathsf{FM}}_{2}(\mathcal{A})$ based on memory skeleton
$\mathcal{M}_{2}$ in $\mathcal{G}=(\mathcal{A},\sqsubseteq)$.

Then, for all two-player arenas $\mathcal{A}=(S_{1},S_{2},E)$, both
$\mathcal{P}_{1}$ and $\mathcal{P}_{2}$ have UFM strategies
$\sigma_{i}\in\Sigma^{\mathsf{FM}}_{i}(\mathcal{A})$ based on memory skeleton
$\mathcal{M}=\mathcal{M}_{1}\otimes\mathcal{M}_{2}$ in
$\mathcal{G}=(\mathcal{A},\sqsubseteq)$.

We highlight the two (possibly different) skeletons of the two players to
maintain a compositional approach, but if the same skeleton $\mathcal{M}$
works in both one-player versions, it also suffices in the two-player version.

###### Proof

By Theorem 4.1 and Theorem 4.2 — which essentially state that the left-to-
right implication of Theorem 3.1 holds already in one-player games, the
hypothesis yields that $\sqsubseteq$ is $\mathcal{M}_{1}$-monotone and
$\mathcal{M}_{1}$-selective, while ${\sqsubseteq}^{-1}$ is
$\mathcal{M}_{2}$-monotone and $\mathcal{M}_{2}$-selective. Now it suffices to
apply Corollary 2 — essentially the right-to-left implication of Theorem 3.1 —
to get the claim. ∎

###  3.3 Example of application

$m_{\mathsf{init}}^{\mathsf{p}}$$m^{\mathsf{p}}_{2}$$T_{1}$$C\setminus
T_{1}$$C$

$m_{\mathsf{init}}^{\mathsf{c}}$$m^{\mathsf{c}}_{2}$$m^{\mathsf{c}}_{3}$$T_{2}\setminus
T_{1}$$T_{1}$$T_{1}$$C\setminus(T_{1}\cup T_{2})$$C$$C\setminus T_{1}$

Figure 2: Memory skeletons $\mathcal{M}^{\mathsf{p}}$ (left) and
$\mathcal{M}^{\mathsf{c}}$ (right) for two-target reachability games.

We present an illustrative application of our results, thereby proving the
existence of UFM strategies for a specific preference relation: the
conjunction of two reachability objectives, a subcase of generalized
reachability games, studied extensively in [20]. Let $C$ be an arbitrary set
of colors, and $T_{1},T_{2}\subseteq C$ be two target sets of colors that have
to be reached at least once. Formally, let the winning condition $W\subseteq
C^{\omega}$ be the set of infinite words $w=c_{1}c_{2}\ldots$ such that

$\exists\,i,j\in\mathbb{N},\,c_{i}\in T_{1}\land c_{j}\in T_{2}.$

This winning condition induces a preference relation $\sqsubseteq$ as
discussed in Example 1. We exhibit two memory skeletons
$\mathcal{M}^{\mathsf{p}}=(M^{\mathsf{p}},m_{\mathsf{init}}^{\mathsf{p}},\alpha_{\mathsf{upd}}^{\mathsf{p}})$
and
$\mathcal{M}^{\mathsf{c}}=(M^{\mathsf{c}},m_{\mathsf{init}}^{\mathsf{c}},\alpha_{\mathsf{upd}}^{\mathsf{c}})$
such that $\sqsubseteq$ is $\mathcal{M}^{\mathsf{p}}$-monotone and
$\mathcal{M}^{\mathsf{c}}$-selective: they are pictured in Figure 2. Note that
such skeletons are obviously not unique.

Let us prove that $\sqsubseteq$ is $\mathcal{M}^{\mathsf{p}}$-monotone. Let
$m\in M^{\mathsf{p}}$, $K_{1},K_{2}\in\mathcal{R}(C)$; we want to show that
Equation (7) is satisfied. We assume that there exists $w\in
L_{m_{\mathsf{init}}^{\mathsf{p}},m}$ such that $[wK_{1}]\sqsubset[wK_{2}]$:
this means that all words of $[wK_{1}]$ are losing, and that there exists a
winning word in $[wK_{2}]$. Let $w^{\prime}\in
L_{m_{\mathsf{init}}^{\mathsf{p}},m}$; we show that we necessarily have that
$[w^{\prime}K_{1}]\sqsubseteq[w^{\prime}K_{2}]$. Note that if $[K_{1}]$ is
empty, this always holds; we now assume that $[K_{1}]$ is non-empty. We study
the two possible values of $m$ separately.

  * •

If $m=m_{\mathsf{init}}^{\mathsf{p}}$, then $w$ and $w^{\prime}$ do not reach
$T_{1}$. If $w$ does not reach $T_{2}$ either, as there is a winning word in
$[wK_{2}]$, then there must be a winning word in $[K_{2}]$. This word is still
winning after prepending $w^{\prime}$ to it, so there is a winning word in
$[w^{\prime}K_{2}]$, and $[w^{\prime}K_{1}]\sqsubseteq[w^{\prime}K_{2}]$. If
$w$ reaches $T_{2}$, then $[K_{1}]$ cannot have a word reaching $T_{1}$. As
$w^{\prime}$ does not reach $T_{1}$ either, all words of $[w^{\prime}K_{1}]$
are losing, so $[w^{\prime}K_{1}]\sqsubseteq[w^{\prime}K_{2}]$.

  * •

If $m=m^{\mathsf{p}}_{2}$, then $w$ and $w^{\prime}$ reach $T_{1}$. Clearly,
$w$ cannot reach $T_{2}$ (as $[wK_{1}]$ would be winning). This implies that
$[K_{2}]$ must contain a word reaching $T_{2}$; as $w^{\prime}$ reaches
$T_{1}$, the concatenation of $w^{\prime}$ with the word of $[K_{2}]$ reaching
$T_{2}$ means that there is a winning word in $[w^{\prime}K_{2}]$, so
$[w^{\prime}K_{1}]\sqsubseteq[w^{\prime}K_{2}]$.

Let us now prove that $\sqsubseteq$ is $\mathcal{M}^{\mathsf{c}}$-selective.
Let $w\in C^{*}$,
$m=\widehat{\alpha_{\mathsf{upd}}^{\mathsf{c}}}(m_{\mathsf{init}}^{\mathsf{c}},w)$,
$K_{1},K_{2}\in\mathcal{R}(C)$ such that $K_{1},K_{2}\subseteq L_{m,m}$, and
$K_{3}\in\mathcal{R}(C)$. We show that Equation (8) is satisfied, i.e., that

$[w(K_{1}\cup
K_{2})^{*}K_{3}]\sqsubseteq[wK_{1}^{*}]\cup[wK_{2}^{*}]\cup[wK_{3}].$

If all words of $[w(K_{1}\cup K_{2})^{*}K_{3}]$ are losing, this equation
trivially holds; we thus assume that this set contains a winning word. We
therefore have to show that there is a winning word in $[wK_{1}^{*}]$,
$[wK_{2}^{*}]$, or $[wK_{3}]$. We study the three possible values of $m$
separately.

  * •

If $m=m_{\mathsf{init}}^{\mathsf{c}}$, then $w$ does not reach $T_{1}$ nor
$T_{2}$, and the same holds for all words of $K_{1}$ and $K_{2}$, as
$K_{1},K_{2}\subseteq
L_{m_{\mathsf{init}}^{\mathsf{c}},m_{\mathsf{init}}^{\mathsf{c}}}$. Therefore,
if a word of $[w(K_{1}\cup K_{2})^{*}K_{3}]$ is winning, this must be because
a word of $[wK_{3}]$ is winning.

  * •

If $m=m^{\mathsf{c}}_{2}$, then $w$ reaches $T_{2}$ but not $T_{1}$, and
$K_{1},K_{2}$ do not reach $T_{1}$. Thus, a word of $[K_{3}]$ must reach
$T_{1}$; in particular, a word of $[wK_{3}]$ must reach both $T_{1}$ and
$T_{2}$.

  * •

If $m=m^{\mathsf{c}}_{3}$, we distinguish two cases. If $w$ reaches $T_{2}$
and $T_{1}$, then $[wK_{1}^{*}]\cup[wK_{2}^{*}]\cup[wK_{3}]$ trivially
contains only winning words. If $w$ reaches $T_{1}$ but not $T_{2}$, then
there must be a word reaching $T_{2}$ in $[(K_{1}\cup K_{2})^{*}K_{3}]$.
Hence, at least one set among $[K_{1}^{*}]$, $[K_{2}^{*}]$, and $[K_{3}]$ must
contain a word reaching $T_{2}$, so $[wK_{1}^{*}]$, $[wK_{2}^{*}]$, or
$[wK_{3}]$ contains a winning word.

$s_{1}$$s_{2}$$s_{3}$$t_{1}$$t_{2}$

$m_{1}$$m_{2}$$m_{3}$$T_{2}\setminus T_{1}$$T_{1}$$T_{1}$$C\setminus(T_{1}\cup
T_{2})$$C$$C\setminus T_{1}$

$s_{1},m_{1}$$s_{2},m_{1}$$s_{3},m_{1}$$s_{1},m_{2}$$s_{2},m_{2}$$s_{3},m_{3}$$t_{2}$$t_{1}$$t_{2}$$t_{1}$

Figure 3: Arena $\mathcal{A}$ (left), memory skeleton $\mathcal{M}$ (center;
with $m_{\mathsf{init}}=m_{1}$), and their product arena
$\mathcal{A}\ltimes\mathcal{M}$ (right; only states reachable from
$S\times\\{m_{\mathsf{init}}\\}$ are depicted). We assume that
$T_{1}=\\{t_{1}\\}$, $T_{2}=\\{t_{2}\\}$. The
$(S\times\\{m_{\mathsf{init}}\\})$-optimal memoryless strategy is highlighted
with bold arrows.

Similar arguments can be laid out to show that the preference relation
${\sqsubseteq}^{-1}$ of $\mathcal{P}_{2}$ is
$\mathcal{M}^{\mathsf{p}}$-monotone and
$\mathcal{M}_{\mathsf{triv}}$-selective (where $\mathcal{M}_{\mathsf{triv}}$
is the trivial memory skeleton with only one state defined earlier). Let
$\mathcal{M}=\mathcal{M}^{\mathsf{p}}\otimes\mathcal{M}^{\mathsf{c}}\otimes\mathcal{M}_{\mathsf{triv}}$
be the product of all the considered skeletons. Although $\mathcal{M}$
formally has six states, only three of them are reachable, and it is similar
to skeleton $\mathcal{M}^{\mathsf{c}}$. By Lemma 6, we have that both
$\sqsubseteq$ and ${\sqsubseteq}^{-1}$ are $\mathcal{M}$-monotone and
$\mathcal{M}$-selective. Using Theorem 3.1, we obtain that both players have
UFM strategies based on skeleton $\mathcal{M}$ in all games
$\mathcal{G}=(\mathcal{A},\sqsubseteq)$. Note that memory skeleton
$\mathcal{M}$ is minimal (no memory skeleton with two states or less suffices
for $\mathcal{P}_{1}$ to play optimally in all arenas [20]).

We provide an example of a one-player arena
$\mathcal{A}=(S_{1},S_{2}=\emptyset,E)$ in Figure 3, and show that there is a
UFM strategy for the preference relation $\sqsubseteq$ based on skeleton
$\mathcal{M}$. To do so, we invoke Lemma 3: we show equivalently that the
product $\mathcal{A}\ltimes\mathcal{M}$ admits an
$(S\times\\{m_{\mathsf{init}}\\})$-optimal memoryless strategy for
$\sqsubseteq$. Notice that no memoryless strategy suffices to play optimally
in $\mathcal{G}=(\mathcal{A},\sqsubseteq)$, as when starting in $s_{2}$,
$\mathcal{P}_{1}$ should first visit $s_{1}$ before going to $s_{3}$. Also,
the $(S\times\\{m_{\mathsf{init}}\\})$-optimal memoryless strategy for the
product arena is only optimal if the initial state is in
$S\times\\{m_{\mathsf{init}}\\}$; it is for instance not optimal from state
$(s_{2},m_{2})$.

In this example, we used Theorem 3.1 directly in order to provide one thorough
illustration of the definitions of $\mathcal{M}$-monotony and
$\mathcal{M}$-selectivity. However, in practice, using Corollary 1 is
preferable, as it yields a much shorter proof. By exhibiting the right
skeletons for $\mathcal{P}_{1}$ and $\mathcal{P}_{2}$, we would simply have to
show that these skeletons are sufficient to play optimally on both players’
one-player arenas, which amounts to graph reasoning.

##  4 From finite memory based on $\mathcal{M}$ to $\mathcal{M}$-monotony and
$\mathcal{M}$-selectivity

Monotony. We want to keep our approach as compositional as possible, hence we
consider the two notions separately. Let us start with $\mathcal{M}$-monotony.

###### Theorem 4.1

Let $\mathcal{M}=(M,m_{\mathsf{init}},\alpha_{\mathsf{upd}})$ be a memory
skeleton and $\sqsubseteq$ be a preference relation. Assume that for all one-
player arenas $\mathcal{A}=(S_{1},S_{2}=\emptyset,E)$, for all
$s,s^{\prime}\in S$, $\mathcal{P}_{1}$ has an $s$-optimal and
$s^{\prime}$-optimal strategy
$\sigma\in\Sigma^{\mathsf{FM}}_{1}(\mathcal{A})$, encoded as a Mealy machine
$\Gamma_{\sigma}=(\mathcal{M},\alpha_{\mathsf{nxt}})$, in
$\mathcal{G}=(\mathcal{A},\sqsubseteq)$. Then $\sqsubseteq$ is
$\mathcal{M}$-monotone.

Note that the same holds for $\mathcal{P}_{2}$ and ${\sqsubseteq}^{-1}$
symmetrically. As discussed in Section 3, we always go for the weakest
hypotheses whenever possible to obtain the most general results: in this case,
we do not require full uniformity of the strategy, but only uniformity with
regard to the fixed pair of states (i.e., strategy $\sigma$ does not need to
be optimal from other states).

$\mathcal{N}^{w}\setminus\\{q_{\mathsf{fin}}^{w}\\}$$\mathcal{N}^{w^{\prime}}\setminus\\{q_{\mathsf{fin}}^{w^{\prime}}\\}$$\mathcal{N}^{K_{1}}\setminus\\{q_{\mathsf{init}}^{K_{1}}\\}$$\mathcal{N}^{K_{2}}\setminus\\{q_{\mathsf{init}}^{K_{2}}\\}$$t$
Figure 4: Automaton $\mathcal{N}$ built to establish $\mathcal{M}$-monotony.

Our proof can be sketched as follows. We need to establish that Equation (7)
holds. We first instantiate the four languages involved in it: $\\{w\\}$,
$\\{w^{\prime}\\}$, $K_{1}$ and $K_{2}$. We take NFAs recognizing them and
build an NFA $\mathcal{N}$ that joins them in such a way that, when
$\mathcal{N}$ is considered as a game arena (see Lemma 2), its plays
correspond exactly to the languages of infinite words considered in Equation
(7). This arena is essentially composed of two chains emulating the two
prefixes $w$ and $w^{\prime}$ and leading to a state $t$ where
$\mathcal{P}_{1}$ has to pick a side corresponding to the two languages
$[K_{1}]$ and $[K_{2}]$ (Figure 4). Now, establishing the
$\mathcal{M}$-monotony of $\sqsubseteq$ boils down to invoking an optimal
strategy $\sigma$ in the corresponding game, the crux being that this strategy
always picks the same edge in $t$ (i.e., the same side between subarenas
corresponding to $[K_{1}]$ and $[K_{2}]$) as both prefixes $w$ and
$w^{\prime}$ are deemed equivalent by the memory skeleton $\mathcal{M}$.

###### Proof

Let $\mathcal{M}=(M,m_{\mathsf{init}},\alpha_{\mathsf{upd}})$ be a memory
skeleton and $\sqsubseteq$ be a preference relation satisfying the hypothesis.
Let us prove that $\sqsubseteq$ is $\mathcal{M}$-monotone, i.e., that for all
$m\in M$, for all $K_{1},K_{2}\in\mathcal{R}(C)$,

$\exists\,w\in
L_{m_{\mathsf{init}},m},\,[wK_{1}]\sqsubset[wK_{2}]\implies\forall\,w^{\prime}\in
L_{m_{\mathsf{init}},m},\,[w^{\prime}K_{1}]\sqsubseteq[w^{\prime}K_{2}].$ (11)

Let $m\in M$, $K_{1},K_{2}\in\mathcal{R}(C)$. We assume that
$K_{1},K_{2}\neq\emptyset$, otherwise Equation (11) holds trivially: if
$K_{1}$ is empty, the conclusion of the implication is true regardless of
$K_{2}$; and if $K_{2}$ is empty, the premise is false. Now, assume there
exists $w\in L_{m_{\mathsf{init}},m}$ such that $[wK_{1}]\sqsubset[wK_{2}]$,
and let $w^{\prime}$ be another prefix in $L_{m_{\mathsf{init}},m}$. We will
prove that $[w^{\prime}K_{1}]\sqsubseteq[w^{\prime}K_{2}]$.

Let
$\mathcal{N}^{w}=(Q^{w},B^{w},\delta^{w},q_{\mathsf{init}}^{w},Q_{\mathsf{fin}}^{w})$,
$\mathcal{N}^{w^{\prime}}=(Q^{w^{\prime}},B^{w^{\prime}},\delta^{w^{\prime}},q_{\mathsf{init}}^{w^{\prime}},Q_{\mathsf{fin}}^{w^{\prime}})$,
$\mathcal{N}^{K_{1}}=(Q^{K_{1}},B^{K_{1}},\delta^{K_{1}},q_{\mathsf{init}}^{K_{1}},Q_{\mathsf{fin}}^{K_{1}})$
and
$\mathcal{N}^{K_{2}}=(Q^{K_{2}},B^{K_{2}},\delta^{K_{2}},q_{\mathsf{init}}^{K_{2}},Q_{\mathsf{fin}}^{K_{2}})$
respectively denote NFAs recognizing languages $\\{w\\}$, $\\{w^{\prime}\\}$,
$K_{1}$ and $K_{2}$. They exist since all these languages are regular. We
assume w.l.o.g. that automaton $\mathcal{N}^{w}$ (resp.
$\mathcal{N}^{w^{\prime}}$, $\mathcal{N}^{K_{1}}$, $\mathcal{N}^{K_{2}}$) is
coaccessible and has only one initial state $q_{\mathsf{init}}^{w}$ (resp.
$q_{\mathsf{init}}^{w^{\prime}}$, $q_{\mathsf{init}}^{K_{1}}$,
$q_{\mathsf{init}}^{K_{2}}$) with no ingoing transition. We can do this since
$K_{1}$ and $K_{2}$ are non-empty. We also assume w.l.o.g. that
$\mathcal{N}^{w}$ (resp. $\mathcal{N}^{w^{\prime}}$) has only one final state
$q_{\mathsf{fin}}^{w}$ (resp. $q_{\mathsf{fin}}^{w^{\prime}}$) with no
outgoing transition. Actually, $\mathcal{N}^{w}$ and
$\mathcal{N}^{w^{\prime}}$ can be taken as “chains” recognizing a unique word,
and being coaccessible and deterministic.

We build an automaton
$\mathcal{N}=(Q,B,\delta,Q_{\mathsf{init}},Q_{\mathsf{fin}})$ by “merging”
states $q_{\mathsf{init}}^{K_{1}}$, $q_{\mathsf{init}}^{K_{2}}$,
$q_{\mathsf{fin}}^{w}$, and $q_{\mathsf{fin}}^{w^{\prime}}$. We call this new
merged state $t$. Formally, we built it as follows.

  * •

$Q=(Q^{w}\cup Q^{w^{\prime}}\cup Q^{K_{1}}\cup
Q^{K_{2}}\cup\\{t\\})\setminus\\{q_{\mathsf{init}}^{K_{1}},q_{\mathsf{init}}^{K_{2}},q_{\mathsf{fin}}^{w},q_{\mathsf{fin}}^{w^{\prime}}\\}$;

  * •

$B=B^{w}\cup B^{w^{\prime}}\cup B^{K_{1}}\cup B^{K_{2}}$;

  * •

$Q_{\mathsf{init}}=\\{q_{\mathsf{init}}^{w},q_{\mathsf{init}}^{w^{\prime}}\\}$
and $Q_{\mathsf{fin}}=Q_{\mathsf{fin}}^{K_{1}}\cup Q_{\mathsf{fin}}^{K_{2}}$;

  * •

and finally, the transition relation simply takes into account the merging on
$t$:

$\displaystyle\delta=$
$\displaystyle\left\\{(q,c,q^{\prime})\mid(q,c,q^{\prime})\in(\delta^{w}\cup\delta^{w^{\prime}}\cup\delta^{K_{1}}\cup\delta^{K_{2}})\wedge
q,q^{\prime}\not\in\\{q_{\mathsf{init}}^{K_{1}},q_{\mathsf{init}}^{K_{2}},q_{\mathsf{fin}}^{w},q_{\mathsf{fin}}^{w^{\prime}}\\}\right\\}$
$\displaystyle\cup$
$\displaystyle\left\\{(q,c,t)\mid(q,c,q^{\prime})\in(\delta^{w}\cup\delta^{w^{\prime}})\wedge
q^{\prime}\in\\{q_{\mathsf{fin}}^{w},q_{\mathsf{fin}}^{w^{\prime}}\\}\right\\}$
$\displaystyle\cup$
$\displaystyle\left\\{(t,c,q^{\prime})\mid(q,c,q^{\prime})\in(\delta^{K_{1}}\cup\delta^{K_{2}})\wedge
q\in\\{q_{\mathsf{init}}^{K_{1}},q_{\mathsf{init}}^{K_{2}}\\}\right\\}.$

This construction is illustrated in Figure 4. The language recognized by
$\mathcal{N}$ from $q_{\mathsf{init}}^{w}$ is $w(K_{1}\cup K_{2})$, whereas
from $q_{\mathsf{init}}^{w^{\prime}}$, it is $w^{\prime}(K_{1}\cup K_{2})$.
Observe that $\mathcal{N}$ is coaccessible since both $\mathcal{N}^{K_{1}}$
and $\mathcal{N}^{K_{2}}$ are coaccessible.

Recall that we assume $[wK_{1}]\sqsubset[wK_{2}]$. By definition, this implies
that $[wK_{2}]\neq\emptyset$, hence we also have that $[K_{2}]\neq\emptyset$.
From this, we get that $t$ is essential in $\mathcal{N}$ (Lemma 2). Thus, it
is also the case of $q_{\mathsf{init}}^{w}$ and
$q_{\mathsf{init}}^{w^{\prime}}$.

We will now interpret this NFA as an arena and use the hypothesis. Let
$\mathcal{A}=\mathsf{Arena}(\mathcal{N})$. By Lemma 2, we have that
$\mathsf{\widehat{col}}(\mathsf{Plays}(\mathcal{A},q_{\mathsf{init}}^{w}))=\left[w(K_{1}\cup
K_{2})\right]$ and
$\mathsf{\widehat{col}}(\mathsf{Plays}(\mathcal{A},q_{\mathsf{init}}^{w^{\prime}}))=\left[w^{\prime}(K_{1}\cup
K_{2})\right]$. By hypothesis, $\mathcal{P}_{1}$ has a
$q_{\mathsf{init}}^{w}$-optimal and $q_{\mathsf{init}}^{w^{\prime}}$-optimal
strategy $\sigma\in\Sigma^{\mathsf{FM}}_{1}(\mathcal{A})$, encoded as a Mealy
machine $\Gamma_{\sigma}=(\mathcal{M},\alpha_{\mathsf{nxt}})$, in
$\mathcal{G}=(\mathcal{A},\sqsubseteq)$.

Let $\pi\in\mathsf{Plays}(\mathcal{A},q_{\mathsf{init}}^{w},\sigma)$ be the
only play consistent with strategy $\sigma$ from $q_{\mathsf{init}}^{w}$. By
definition of $\mathcal{A}$, this play $\pi$ necessarily contains a history
$\rho=e_{1}\ldots{}e_{n}$ such that $\mathsf{out}(e_{n})=t$ and for all $i$,
$1\leq i<n$, $\mathsf{out}(e_{i})\neq t$. Observe that
$\mathsf{\widehat{col}}(\rho)=w$. Recall that
$m=\widehat{\alpha_{\mathsf{upd}}}(m_{\mathsf{init}},w)$ is the memory state
reached after reading $w$ since $w\in L_{m_{\mathsf{init}},m}$. Let
$e=\alpha_{\mathsf{nxt}}(m,t)$ be the edge chosen by $\sigma$ in $t$ when $t$
is visited (note that $t$ will be visited only once by construction of
$\mathcal{A}$).

We will show that $e$ belongs to the part generated by $\mathcal{N}^{K_{2}}$.
By contradiction, assume it belongs to $\mathcal{N}^{K_{1}}$. Then,
$\pi=\rho\cdot\pi^{\prime}$, with
$\mathsf{\widehat{col}}(\pi^{\prime})\in[K_{1}]$, hence
$\mathsf{\widehat{col}}(\pi)\in[wK_{1}]$. First, observe that

$\displaystyle[wK_{2}]$
$\displaystyle\sqsubseteq\mathsf{\widehat{col}}(\mathsf{Plays}(\mathcal{A},q_{\mathsf{init}}^{w}))$

since $[wK_{2}]\subseteq[wK_{1}]\cup[wK_{2}]$,
$[wK_{1}]\cup[wK_{2}]=\left[w(K_{1}\cup K_{2})\right]$ by Lemma 1, and, as
noted above, $\left[w(K_{1}\cup
K_{2})\right]=\mathsf{\widehat{col}}(\mathsf{Plays}(\mathcal{A},q_{\mathsf{init}}^{w}))$.
Now since $\sigma$ is optimal111One can easily get from the definition using
the $\mathsf{UCol}$-operator that, in this one-player game, $\sigma$ is
$q_{\mathsf{init}}^{w}$-optimal if and only if for all
$\sigma^{\prime}\in\Sigma(\mathcal{A})$,
$\mathsf{\widehat{col}}(\mathsf{Plays}(\mathcal{A},q_{\mathsf{init}}^{w},\sigma^{\prime}))\sqsubseteq\mathsf{\widehat{col}}(\mathsf{Plays}(\mathcal{A},q_{\mathsf{init}}^{w},\sigma))$.
from $q_{\mathsf{init}}^{w}$, we have

$\displaystyle[wK_{2}]$ $\displaystyle\sqsubseteq\mathsf{\widehat{col}}(\pi).$

Finally, we assumed that $\mathsf{\widehat{col}}(\pi)\in[wK_{1}]$, hence we
can conclude that

$\displaystyle[wK_{2}]$ $\displaystyle\sqsubseteq[wK_{1}],$

which contradicts the hypothesis that $[wK_{1}]\sqsubset[wK_{2}]$. Hence, we
have established that $e$ belongs to $\mathcal{N}^{K_{2}}$.

Now let us consider
$\pi^{\prime\prime}\in\mathsf{Plays}(\mathcal{A},q_{\mathsf{init}}^{w^{\prime}},\sigma)$,
the only play consistent with strategy $\sigma$ from
$q_{\mathsf{init}}^{w^{\prime}}$. Again, by definition of $\mathcal{A}$, this
play $\pi^{\prime\prime}$ necessarily contains a history
$\rho^{\prime\prime}=e_{1}\ldots{}e_{n}$ such that $\mathsf{out}(e_{n})=t$ and
for all $i$, $1\leq i<n$, $\mathsf{out}(e_{i})\neq t$. Observe that
$\mathsf{\widehat{col}}(\rho^{\prime\prime})=w^{\prime}$. Since $w^{\prime}\in
L_{m_{\mathsf{init}},m}$, we also have that
$\widehat{\alpha_{\mathsf{upd}}}(m_{\mathsf{init}},w^{\prime})=m$, i.e., the
memory state reached after reading $w^{\prime}$ is the same as the one reached
after reading $w$. Recall that $\alpha_{\mathsf{nxt}}$ is deterministic by
definition: i.e., for a given memory state and state of the arena, it always
prescribes the same edge. Hence, we have that $e=\alpha_{\mathsf{nxt}}(m,t)$
is exactly the same as before, and therefore belongs to $\mathcal{N}^{K_{2}}$.
Thus, $\mathsf{\widehat{col}}(\pi^{\prime\prime})\in[w^{\prime}K_{2}]$.

Finally, since $\sigma$ is also $q_{\mathsf{init}}^{w^{\prime}}$-optimal and
applying the same reasoning as above, we have that

$\displaystyle[w^{\prime}K_{1}]\sqsubseteq[w^{\prime}K_{1}]\cup[w^{\prime}K_{2}]=\left[w^{\prime}(K_{1}\cup
K_{2})\right]$
$\displaystyle=\mathsf{\widehat{col}}(\mathsf{Plays}(\mathcal{A},q_{\mathsf{init}}^{w^{\prime}}))$
$\displaystyle\sqsubseteq\mathsf{\widehat{col}}(\pi^{\prime\prime})$
$\displaystyle\sqsubseteq[w^{\prime}K_{2}],$

which proves Equation (11) and concludes our proof.∎

Selectivity. We now turn to selectivity, which focuses on stability with
regard to cycle mixing.

###### Theorem 4.2

Let $\mathcal{M}=(M,m_{\mathsf{init}},\alpha_{\mathsf{upd}})$ be a memory
skeleton and $\sqsubseteq$ be a preference relation. Assume that for all one-
player arenas $\mathcal{A}=(S_{1},S_{2}=\emptyset,E)$, for all $s\in S$,
$\mathcal{P}_{1}$ has an $s$-optimal strategy
$\sigma\in\Sigma^{\mathsf{FM}}_{1}(\mathcal{A})$, encoded as a Mealy machine
$\Gamma_{\sigma}=(\mathcal{M},\alpha_{\mathsf{nxt}})$, in
$\mathcal{G}=(\mathcal{A},\sqsubseteq)$. Then $\sqsubseteq$ is
$\mathcal{M}$-selective.

Note that the same holds for $\mathcal{P}_{2}$ and ${\sqsubseteq}^{-1}$
symmetrically. Again, observe that our hypothesis is as weak as possible as no
uniformity is required.

Our proof bears similarities with the monotone case. We need to establish that
Equation (8) holds. We first instantiate the four languages involved in it:
$\\{w\\}$, $K_{1}$, $K_{2}$ and $K_{3}$. We take NFAs recognizing them and
build an NFA $\mathcal{N}$ that joins them in such a way that, when
$\mathcal{N}$ is considered as a game arena (see Lemma 2), its plays
correspond exactly to the languages of infinite words considered in Equation
(8). This arena is essentially composed of a chain emulating the prefix $w$
and leading to a state $t$ where $\mathcal{P}_{1}$ can visit sides that
generate cycles from $K_{1}$ and $K_{2}$ — forever or for a finite time — or
branch to a side corresponding to $K_{3}$ (Figure 5). Now, establishing the
$\mathcal{M}$-selectivity of $\sqsubseteq$ boils down to invoking an optimal
strategy $\sigma$ in the corresponding game, the crux being that this strategy
always picks the same edge in $t$ (i.e., side between subarenas corresponding
to $[K^{\ast}_{1}]$, $[K_{2}^{*}]$ and $[K_{3}]$) as all cycles on $t$ are
deemed equivalent by the memory skeleton $\mathcal{M}$. The main difference
with the previous construction is transparent in the last sentence: it is now
possible to come back to $t$, possibly infinitely often, and our proof takes
that into account.

###### Proof

Let $\mathcal{M}=(M,m_{\mathsf{init}},\alpha_{\mathsf{upd}})$ be a memory
skeleton and $\sqsubseteq$ a preference relation satisfying the hypothesis.
Let us prove that $\sqsubseteq$ is $\mathcal{M}$-selective, i.e., that for all
$w\in C^{*}$, $m=\widehat{\alpha_{\mathsf{upd}}}(m_{\mathsf{init}},w)$, for
all $K_{1},K_{2}\in\mathcal{R}(C)$ such that $K_{1},K_{2}\subseteq L_{m,m}$,
for all $K_{3}\in\mathcal{R}(C)$,

$[w(K_{1}\cup
K_{2})^{*}K_{3}]\sqsubseteq[wK_{1}^{*}]\cup[wK_{2}^{*}]\cup[wK_{3}].$ (12)

Let $w\in C^{\ast}$ and
$m=\widehat{\alpha_{\mathsf{upd}}}(m_{\mathsf{init}},w)$. Let
$K_{1},K_{2},K_{3}\in\mathcal{R}(C)$, with $K_{1},K_{2}\subseteq L_{m,m}$. In
the following, we assume all three languages $K_{1}$, $K_{2}$ and $K_{3}$ to
be non-empty. Indeed, if $K_{3}$ is empty, so is the left-hand side of
Equation (12), hence it trivially holds. If both $K_{1}$ and $K_{2}$ are
empty, Equation (12) compares $[wK_{3}]$ to itself, hence it trivially holds
again. Finally, if $K_{1}$ is the only empty language among the three, then
Equation (12) can be restated as follows:

$[w(K_{1}\cup K_{2})^{*}K_{3}]=[w(K_{2}\cup
K_{2})^{*}K_{3}]\sqsubseteq[wK_{2}^{*}]\cup[wK_{2}^{*}]\cup[wK_{3}]=[wK_{1}^{*}]\cup[wK_{2}^{*}]\cup[wK_{3}],$

where the middle inequality — the one to prove — involves three non-empty
sets. A symmetric argument holds if $K_{2}$ is the only empty language. We
also assume that $K_{1}$ and $K_{2}$ do not contain the empty word for
technical convenience: this is w.l.o.g. thanks to the Kleene stars used in the
regular expressions to consider.

As for monotony, we start by considering NFAs for all these languages: let
$\mathcal{N}^{w}=(Q^{w},B^{w},\delta^{w},q_{\mathsf{init}}^{w},Q_{\mathsf{fin}}^{w})$,
$\mathcal{N}^{K_{1}}=(Q^{K_{1}},B^{K_{1}},\delta^{K_{1}},q_{\mathsf{init}}^{K_{1}},Q_{\mathsf{fin}}^{K_{1}})$,
$\mathcal{N}^{K_{2}}=(Q^{K_{2}},B^{K_{2}},\delta^{K_{2}},q_{\mathsf{init}}^{K_{2}},Q_{\mathsf{fin}}^{K_{2}})$
and
$\mathcal{N}^{K_{3}}=(Q^{K_{3}},B^{K_{3}},\delta^{K_{3}},q_{\mathsf{init}}^{K_{3}},Q_{\mathsf{fin}}^{K_{3}})$
respectively denote NFAs recognizing languages $\\{w\\}$, $K_{1}$, $K_{2}$ and
$K_{3}$. They exist since all these languages are regular. We assume w.l.o.g.
that automaton $\mathcal{N}^{w}$ (resp. $\mathcal{N}^{K_{1}}$,
$\mathcal{N}^{K_{2}}$, $\mathcal{N}^{K_{3}}$) is coaccessible and has only one
initial state $q_{\mathsf{init}}^{w}$ (resp. $q_{\mathsf{init}}^{K_{1}}$,
$q_{\mathsf{init}}^{K_{2}}$, $q_{\mathsf{init}}^{K_{3}}$) with no ingoing
transition. We can do this since $K_{1}$, $K_{2}$ and $K_{3}$ are non-empty.
We also assume w.l.o.g. that $\mathcal{N}^{w}$ (resp. $\mathcal{N}^{K_{1}}$,
$\mathcal{N}^{K_{2}}$) has only one final state $q_{\mathsf{fin}}^{w}$ (resp.
$q_{\mathsf{fin}}^{K_{1}}$, $q_{\mathsf{fin}}^{K_{2}}$) with no outgoing
transition. Again $\mathcal{N}^{w}$ can simply be a “chain” recognizing a
unique word, being both coaccessible and deterministic.

Similarly to Theorem 4.1, we build an automaton
$\mathcal{N}=(Q,B,\delta,Q_{\mathsf{init}},Q_{\mathsf{fin}})$ by “merging”
states $q_{\mathsf{init}}^{K_{1}}$, $q_{\mathsf{init}}^{K_{2}}$,
$q_{\mathsf{init}}^{K_{3}}$, $q_{\mathsf{fin}}^{w}$,
$q_{\mathsf{fin}}^{K_{1}}$, and $q_{\mathsf{fin}}^{K_{2}}$. We call this new
merged state $t$. Formally, we build it as follows.

  * •

$Q=(Q^{w}\cup Q^{K_{1}}\cup Q^{K_{2}}\cup
Q^{K_{3}}\cup\\{t\\})\setminus\\{q_{\mathsf{init}}^{K_{1}},q_{\mathsf{init}}^{K_{2}},q_{\mathsf{init}}^{K_{3}},q_{\mathsf{fin}}^{w},q_{\mathsf{fin}}^{K_{1}},q_{\mathsf{fin}}^{K_{2}}\\}$;

  * •

$B=B^{w}\cup B^{K_{1}}\cup B^{K_{2}}\cup B^{K_{3}}$;

  * •

$Q_{\mathsf{init}}=Q_{\mathsf{init}}^{w}=\\{q_{\mathsf{init}}^{w}\\}$ and
$Q_{\mathsf{fin}}=Q_{\mathsf{fin}}^{K_{3}}$;

  * •

and finally, the transition relation simply takes into account the merging on
$t$:

$\displaystyle\delta=$
$\displaystyle\left\\{(q,c,q^{\prime})\mid(q,c,q^{\prime})\in(\delta^{w}\cup\delta^{K_{1}}\cup\delta^{K_{2}}\cup\delta^{K_{3}})\wedge
q,q^{\prime}\not\in\\{q_{\mathsf{init}}^{K_{1}},q_{\mathsf{init}}^{K_{2}},q_{\mathsf{init}}^{K_{3}},q_{\mathsf{fin}}^{w},q_{\mathsf{fin}}^{K_{1}},q_{\mathsf{fin}}^{K_{2}}\\}\right\\}$
$\displaystyle\cup$
$\displaystyle\left\\{(q,c,t)\mid(q,c,q^{\prime})\in(\delta^{w}\cup\delta^{K_{1}}\cup\delta^{K_{2}})\wedge
q^{\prime}\in\\{q_{\mathsf{fin}}^{w},q_{\mathsf{fin}}^{K_{1}},q_{\mathsf{fin}}^{K_{2}}\\}\right\\}$
$\displaystyle\cup$
$\displaystyle\left\\{(t,c,q^{\prime})\mid(q,c,q^{\prime})\in(\delta^{K_{1}}\cup\delta^{K_{2}}\cup\delta^{K_{3}})\wedge
q\in\\{q_{\mathsf{init}}^{K_{1}},q_{\mathsf{init}}^{K_{2}},q_{\mathsf{init}}^{K_{3}}\\}\right\\}.$

This construction is illustrated in Figure 5. The language recognized by
$\mathcal{N}$ is $w(K_{1}\cup K_{2})^{\ast}K_{3}$. Observe that $\mathcal{N}$
is coaccessible since $\mathcal{N}^{K_{1}}$, $\mathcal{N}^{K_{2}}$ and
$\mathcal{N}^{K_{3}}$ are coaccessible. Also observe that $t$ is essential by
construction: by merging the initial and final states of $K_{1}$ (resp.
$K_{2}$), we created cycles on $t$. Thus, $q_{\mathsf{init}}^{w}$ is also
essential.

$\mathcal{N}^{w}\setminus\\{q_{\mathsf{fin}}^{w}\\}$$t$$\mathcal{N}^{K_{1}}\setminus\\{q_{\mathsf{init}}^{K_{1}},q_{\mathsf{fin}}^{K_{1}}\\}$$\mathcal{N}^{K_{2}}\setminus\\{q_{\mathsf{init}}^{K_{2}},q_{\mathsf{fin}}^{K_{2}}\\}$$\mathcal{N}^{K_{3}}\setminus\\{q_{\mathsf{init}}^{K_{3}}\\}$
Figure 5: Automaton $\mathcal{N}$ built to establish
$\mathcal{M}$-selectivity.

We will now interpret this NFA as an arena and use the hypothesis. Let
$\mathcal{A}=\mathsf{Arena}(\mathcal{N})$. By Lemma 2, we have that
$\mathsf{\widehat{col}}(\mathsf{Plays}(\mathcal{A},q_{\mathsf{init}}^{w}))=\left[w(K_{1}\cup
K_{2})^{\ast}K_{3}\right]$. By hypothesis, $\mathcal{P}_{1}$ has a
$q_{\mathsf{init}}^{w}$-optimal strategy
$\sigma\in\Sigma^{\mathsf{FM}}_{1}(\mathcal{A})$, encoded as a Mealy machine
$\Gamma_{\sigma}=(\mathcal{M},\alpha_{\mathsf{nxt}})$, in
$\mathcal{G}=(\mathcal{A},\sqsubseteq)$.

Let $\pi\in\mathsf{Plays}(\mathcal{A},q_{\mathsf{init}}^{w},\sigma)$ be the
only play consistent with strategy $\sigma$ from $q_{\mathsf{init}}^{w}$. By
$q_{\mathsf{init}}^{w}$-optimality, we have that

$\left[w(K_{1}\cup
K_{2})^{\ast}K_{3}\right]\sqsubseteq\mathsf{\widehat{col}}(\pi).$ (13)

By definition of $\mathcal{A}$, this play $\pi$ necessarily contains a history
$\rho=e_{1}\ldots{}e_{n}$ such that $\mathsf{out}(e_{n})=t$ and for all $i$,
$1\leq i<n$, $\mathsf{out}(e_{i})\neq t$. Observe that
$\mathsf{\widehat{col}}(\rho)=w$. Recall that
$m=\widehat{\alpha_{\mathsf{upd}}}(m_{\mathsf{init}},w)$ is the memory state
reached after reading $w$ since $w\in L_{m_{\mathsf{init}},m}$. Let
$e=\alpha_{\mathsf{nxt}}(m,t)$ be the edge chosen by $\sigma$ in $t$ when $t$
is first visited. Note that in contrast to the construction in Theorem 4.1,
$t$ could be visited many times here, and even infinitely often (using cycles
from $K_{1}$ and $K_{2}$). We consider two cases in the following.

First, assume that $e$ belongs to the part of the arena generated by
$\mathcal{N}^{K_{3}}$. Since $t$ (originally $q_{\mathsf{init}}^{K_{3}}$) has
no incoming transition in $\mathcal{N}^{K_{3}}$, we conclude that $\pi$ never
visits $t$ again, and that $\mathsf{\widehat{col}}(\pi)\in[wK_{3}]$. By
Equation (13), we verify Equation (12).

Now, assume that $e$ belongs to the part of the arena generated by
$\mathcal{N}^{K_{1}}$ (the same reasoning will apply symmetrically for
$\mathcal{N}^{K_{2}}$). We want to show that
$\mathsf{\widehat{col}}(\pi)\in[wK^{\ast}_{1}]$, i.e., that $\sigma$ never
switches to another part of the arena. Two cases are possible: either $(a)$
$\pi$ visits $t$ only once, or $(b)$ $\pi$ visits $t$ at least twice.

Case $(a)$. Since $\pi$ visits $t$ only once and $t$ is the only state where
the play could switch to a different automaton, we have that
$\pi=\rho\cdot\pi^{\prime}$ for a suffix $\pi^{\prime}$ starting in $t$ and
entirely contained in $\mathcal{N}^{K_{1}}$. Hence, we have
$\mathsf{\widehat{col}}(\pi)=w\cdot\mathsf{\widehat{col}}(\pi^{\prime})$ with
$\mathsf{\widehat{col}}(\pi^{\prime})\in[K_{1}]$. Thus,
$\mathsf{\widehat{col}}(\pi)\in[wK_{1}]\subseteq[wK^{\ast}_{1}]$.

Case $(b)$. Let $\pi=\rho\cdot\rho^{\prime}\cdot\pi^{\prime}$, such that
$\rho^{\prime}$ ends with the second visit of $t$. Recall that
$w=\mathsf{\widehat{col}}(\rho)$,
$m=\widehat{\alpha_{\mathsf{upd}}}(m_{\mathsf{init}},w)$, and
$e=\alpha_{\mathsf{nxt}}(m,t)$. Now, by definition of $K_{1}$, we have that
$\mathsf{\widehat{col}}(\rho^{\prime})\in L_{m,m}$. Hence,
$\widehat{\alpha_{\mathsf{upd}}}(m,\mathsf{\widehat{col}}(\rho^{\prime}))=m$.
Intuitively, the memory skeleton is back to the same memory state after
reading the cycle $\rho^{\prime}$. As argued in Theorem 4.1,
$\alpha_{\mathsf{nxt}}$ is deterministic, and both the state of the arena and
the memory state are identical after $\rho$ and after
$\rho\cdot\rho^{\prime}$. Therefore
$\sigma(\rho\cdot\rho^{\prime})=\sigma(\rho)=e$. Iterating this reasoning (as
all cycles on $t$ in $\mathcal{N}^{K_{1}}$ are read as cycles on $m$ in the
memory), we conclude that $\pi=\rho\cdot(\rho^{\prime})^{\omega}$. This
implies that $\mathsf{\widehat{col}}(\pi)\in[wK_{1}^{\ast}]$.

Hence, in both cases, we have that
$\mathsf{\widehat{col}}(\pi)\in[wK_{1}^{\ast}]$. Now, by Equation (13), we
verify Equation (12).

Wrapping everything up, we have that whatever the part of the arena to which
$e$ belongs, Equation (12) is verified. Therefore, we have shown that
$\sqsubseteq$ is indeed $\mathcal{M}$-selective.∎

Wrap-up. Through Theorem 4.1 and Theorem 4.2, we have established that the
existence of finite-memory optimal strategies based on a skeleton
$\mathcal{M}$ in one-player games implies both $\mathcal{M}$-monotony and
$\mathcal{M}$-selectivity of the preference relation, under very mild
uniformity assumption. It is interesting to observe that this holds already
for one-player games (a fortiori, for two-player games too). In the next
section, we consider the converse: we will prove that $\mathcal{M}$-monotony
and $\mathcal{M}$-selectivity implies the existence of finite-memory optimal
strategies, not only in one-player games, but even in two-player ones.

##  5 From $\mathcal{M}$-monotony and $\mathcal{M}$-selectivity to finite
memory based on $\mathcal{M}$

Induction step. To prove the coveted implication (Theorem 5.1), we first focus
on memoryless strategies in “covered” arenas, as discussed in Section 2.
Intuitively, a “covered” arena is akin to a product arena (with a memory
skeleton): hence studying memoryless strategies on such arenas is very close
to studying finite-memory strategies on general arenas.

We will proceed by induction on the number of choices in an arena, as sketched
in Section 2. This induction will require us to mix different Nash equilibria
(one for each player) in a proper way, to maintain the desired property. For
the sake of readability, we thus start by proving the induction step for one
player.

For an arena $\mathcal{A}=(S_{1},S_{2},E)$, we write $n_{\mathcal{A}}=|E|-|S|$
for its number of choices.

###### Lemma 8

Let $\sqsubseteq$ be a preference relation and $\mathcal{M}^{\mathsf{p}}$,
$\mathcal{M}^{\mathsf{c}}$ be two memory skeletons. Assume that $\sqsubseteq$
is $\mathcal{M}^{\mathsf{p}}$-monotone and
$\mathcal{M}^{\mathsf{c}}$-selective. Let $n\in\mathbb{N}$. Assume that for
all arenas $\mathcal{A}^{\prime}=(S^{\prime}_{1},S^{\prime}_{2},E^{\prime})$
such that $n_{\mathcal{A}^{\prime}}<n$, for all subsets of states
$S_{\mathsf{cov}}^{\prime}\subseteq S^{\prime}$ for which
$\mathcal{M}^{\mathsf{p}}$ is a prefix-cover and $\mathcal{M}^{\mathsf{c}}$ is
a cyclic-cover, there exists a memoryless Nash equilibrium
$(\sigma^{\prime}_{1},\sigma^{\prime}_{2})\in\Sigma^{\mathsf{ML}}_{1}(\mathcal{A}^{\prime})\times\Sigma^{\mathsf{ML}}_{2}(\mathcal{A}^{\prime})$
from $S_{\mathsf{cov}}^{\prime}$ in
$\mathcal{G}^{\prime}=(\mathcal{A}^{\prime},\sqsubseteq)$.

Then, for all arenas $\mathcal{A}=(S_{1},S_{2},E)$ such that
$n_{\mathcal{A}}=n$, for all subset of states $S_{\mathsf{cov}}\subseteq S$
for which $\mathcal{M}^{\mathsf{p}}$ is a prefix-cover and
$\mathcal{M}^{\mathsf{c}}$ is a cyclic-cover, there exists a Nash equilibrium
$(\sigma_{1},\sigma_{2})\in\Sigma^{\mathsf{ML}}_{1}(\mathcal{A})\times\Sigma_{2}(\mathcal{A})$
from $S_{\mathsf{cov}}$ in $\mathcal{G}=(\mathcal{A},\sqsubseteq)$ such that
$\sigma_{1}$ is memoryless.

Note that the same holds for $\mathcal{P}_{2}$ and ${\sqsubseteq}^{-1}$
symmetrically.

Intuitively, Lemma 8 states that under the hypotheses of
$\mathcal{M}^{\mathsf{p}}$-monotony and
$\mathcal{M}^{\mathsf{c}}$-selectivity, if both players can play optimally
with memoryless strategies in “small” and “covered” arenas, the same property
holds for at least $\mathcal{P}_{1}$ in “covered” arenas where an additional
choice exists.

This lemma has to be commented. First, observe that the property is about Nash
equilibria. Indeed, as explained in Section 2, the result we prove is actually
slightly stronger than the existence of optimal strategies, as it can be
stated for Nash equilibria.

Second, this lemma is focused on proving the existence of an NE in which
$\mathcal{P}_{1}$’s strategy is memoryless: proving that this holds for both
players will be done in Theorem 5.1.

Third, as motivated in Section 2, we state our result as the existence of
memoryless optimal strategies in “covered” arenas: the existence of UFM
strategies in general arenas will follow (Corollary 2), but taking this road
allows us to keep optimal strategies memoryless for many arenas (which already
share the “classifying” properties that a product with a memory skeleton would
grant).

Fourth, we use two different skeletons, one for monotony (i.e., dealing with
prefixes) and one for selectivity (i.e., dealing with cycles). Obviously, one
can use a single combined skeleton using Lemma 6 and Lemma 7, but our approach
has the advantage of being compositional and highlighting how each skeleton /
property impacts the reasoning in the proof: we will see that they have very
different uses.

Lastly, the notions of prefix-covers and cyclic-covers are defined with regard
to a covered set of states $S_{\mathsf{cov}}$ in order to keep the need for
uniformity minimal, in the same spirit as what we did in Section 4.

As mentioned above, our proof is essentially an induction step. Starting from
an arena $\mathcal{A}$ with $n_{\mathcal{A}}=n$ choices, we identify a state
$t$ in which $\mathcal{P}_{1}$ has at least two choices (the proof is
symmetric for $\mathcal{P}_{2}$). By splitting the edges in $t$ in two sets,
we obtain two corresponding subarenas $\mathcal{A}_{a}$ and $\mathcal{A}_{b}$
such that $n_{\mathcal{A}_{a}},n_{\mathcal{A}_{b}}<n$, along with the
corresponding subgames. The induction hypothesis gives us two memoryless Nash
equilibria (from $S_{\mathsf{cov}}$) in these subgames:
$(\sigma^{a}_{1},\sigma^{a}_{2})$ and $(\sigma^{b}_{1},\sigma^{b}_{2})$. The
arguments can then be unfolded intuitively as follows. First, using
$\mathcal{M}^{\mathsf{p}}$-monotony and $\mathcal{M}^{\mathsf{p}}$ being a
prefix-cover, we identify one subarena (say $\mathcal{A}_{a}$) which is
clearly at least as good as the other for $\mathcal{P}_{1}$. Second, we build
a strategy profile $(\sigma^{\\#}_{1},\sigma^{\\#}_{2})$, that we claim to be
an NE in $\mathcal{G}$, in the following way: $\mathcal{P}_{1}$ uses strategy
$\sigma_{1}^{a}$ (the one from the best subarena) and $\mathcal{P}_{2}$ reacts
to $\mathcal{P}_{1}$’s actions by playing the corresponding best-response
strategy. I.e., if $\mathcal{P}_{1}$ plays in $\mathcal{A}_{a}$,
$\mathcal{P}_{2}$ plays according to $\sigma_{2}^{a}$, and otherwise he plays
according to $\sigma_{2}^{b}$. Third, it remains to prove the two inequalities
of Equation (4). The rightmost one is easy, as well as the leftmost one in the
subcase where the unique play
$\pi\in\mathsf{Plays}(\mathcal{A},s,\sigma^{\\#}_{1},\sigma^{\\#}_{2})$ does
not visit state $t$: they can both be proved essentially thanks to the
induction hypothesis and easy construction arguments. The crux of the proof is
thus in the last step: proving that the leftmost inequality holds when the
play visits $t$. This can be achieved thanks to
$\mathcal{M}^{\mathsf{c}}$-selectivity and $\mathcal{M}^{\mathsf{c}}$ being a
cyclic-cover, Lemma 1, inherent properties of the preference relation,
$\mathcal{A}_{a}$ being the best subarena thanks
$\mathcal{M}^{\mathsf{p}}$-monotony, and the induction hypothesis, in that
order.

Obviously, $\mathcal{M}$-monotony (Definition 1), $\mathcal{M}$-selectivity
(Definition 2), prefix-covers and cyclic-covers (Definition 3) were defined to
be sufficient to provide Lemma 8: one of the main challenges was to have them
not too powerful as to keep them also necessary, as proved in Section 4.

###### Proof

Let
$\mathcal{M}^{\mathsf{p}}=(M^{\mathsf{p}},m_{\mathsf{init}}^{\mathsf{p}},\alpha_{\mathsf{upd}}^{\mathsf{p}})$
and
$\mathcal{M}^{\mathsf{c}}=(M^{\mathsf{c}},m_{\mathsf{init}}^{\mathsf{c}},\alpha_{\mathsf{upd}}^{\mathsf{c}})$.
Let $\sqsubseteq$ be a preference relation that is
$\mathcal{M}^{\mathsf{p}}$-monotone and $\mathcal{M}^{\mathsf{c}}$-selective.
Let $n\in\mathbb{N}$ and assume that for all arenas
$\mathcal{A}^{\prime}=(S^{\prime}_{1},S^{\prime}_{2},E^{\prime})$ such that
$n_{\mathcal{A}^{\prime}}<n$, for all subsets of states
$S_{\mathsf{cov}}^{\prime}\subseteq S^{\prime}$ for which
$\mathcal{M}^{\mathsf{p}}$ is a prefix-cover and $\mathcal{M}^{\mathsf{c}}$ is
a cyclic-cover, there exists a memoryless Nash equilibrium
$(\sigma^{\prime}_{1},\sigma^{\prime}_{2})\in\Sigma^{\mathsf{ML}}_{1}(\mathcal{A}^{\prime})\times\Sigma^{\mathsf{ML}}_{2}(\mathcal{A}^{\prime})$
in $\mathcal{G}^{\prime}=(\mathcal{A}^{\prime},\sqsubseteq)$.

Now, let $\mathcal{A}=(S_{1},S_{2},E)$ be an arena such that
$n_{\mathcal{A}}=n$, and let $S_{\mathsf{cov}}\subseteq S$ be a subset of
states for which $\mathcal{M}^{\mathsf{p}}$ is a prefix-cover and
$\mathcal{M}^{\mathsf{c}}$ is a cyclic-cover. Our goal is to prove that there
exists an NE
$(\sigma_{1},\sigma_{2})\in\Sigma^{\mathsf{ML}}_{1}(\mathcal{A})\times\Sigma_{2}(\mathcal{A})$
from $S_{\mathsf{cov}}$ in $\mathcal{G}=(\mathcal{A},\sqsubseteq)$ such that
$\sigma_{1}$ is memoryless. The same proof can be done with respect to
$\mathcal{P}_{2}$ symmetrically, using its preference relation
$\sqsubseteq^{-1}$ and the appropriate skeletons.

If $\mathcal{A}$ is such that $\mathcal{P}_{1}$ has no choice (i.e., all his
states have only one outgoing edge), the proof is trivial. Hence, let us
assume this is not the case and let $t\in S_{1}$ be a state with at least two
edges, i.e., $|\\{e\in E\mid\mathsf{in}(e)=t\\}|>1$. We partition $\\{e\in
E\mid\mathsf{in}(e)=t\\}$ in two (non-empty) sets $E_{a}$ and $E_{b}$, and we
define two corresponding subarenas, $\mathcal{A}_{a}=(S_{1},S_{2},E\setminus
E_{b})$, and $\mathcal{A}_{b}=(S_{1},S_{2},E\setminus E_{a})$. Observe that it
remains true that $\mathcal{M}^{\mathsf{p}}$ is a prefix-cover and
$\mathcal{M}^{\mathsf{c}}$ is a cyclic-cover of $S_{\mathsf{cov}}$, both in
$\mathcal{A}_{a}$ and $\mathcal{A}_{b}$, by definition of prefix- and cyclic-
covers (intuitively, we quantify universally over fewer histories than in
$\mathcal{A}$).

Thus, by induction hypothesis (since
$n_{\mathcal{A}_{a}},n_{\mathcal{A}_{b}}<n_{\mathcal{A}}=n$), we have
memoryless NE from $S_{\mathsf{cov}}$ in the subgames
$\mathcal{G}_{a}=(\mathcal{A}_{a},\sqsubseteq)$ and
$\mathcal{G}_{b}=(\mathcal{A}_{b},\sqsubseteq)$. Let us denote them by
$(\sigma_{1}^{j},\sigma^{j}_{2})$ for game $\mathcal{G}_{j}$, $j\in\\{a,b\\}$.

Since $\mathcal{M}^{\mathsf{p}}$ is a prefix-cover of $S_{\mathsf{cov}}$ in
$\mathcal{A}$, there exists $m^{\mathsf{p}}_{t}\in M^{\mathsf{p}}$ such that,
for all $\rho\in\mathsf{Hists}(\mathcal{A})$ such that $\mathsf{in}(\rho)\in
S_{\mathsf{cov}}$ and $\mathsf{out}(\rho)=t$,
$\widehat{\alpha_{\mathsf{upd}}}(m_{\mathsf{init}}^{\mathsf{p}},\mathsf{\widehat{col}}(\rho))=m^{\mathsf{p}}_{t}$.
Now, let
$K^{\mathsf{p}}_{j}=\mathsf{\widehat{col}}\big{(}\mathsf{Hists}(\mathcal{A}_{j},t,\sigma^{j}_{2})\big{)}$,
for $j\in\\{a,b\\}$, that is, $K^{\mathsf{p}}_{j}$ contains all (projections
to colors of) histories consistent with $\sigma_{2}^{j}$ and starting in $t$
in subarena $\mathcal{A}_{j}$.

By $\mathcal{M}^{\mathsf{p}}$-monotony, we can easily deduce that we have

$\displaystyle\forall\,w\in
L^{\mathsf{p}}_{m_{\mathsf{init}}^{\mathsf{p}},m_{t}^{\mathsf{p}}},\;[wK^{\mathsf{p}}_{a}]\sqsubseteq[wK^{\mathsf{p}}_{b}],$
or $\displaystyle\forall\,w\in
L^{\mathsf{p}}_{m_{\mathsf{init}}^{\mathsf{p}},m_{t}^{\mathsf{p}}},\;[wK^{\mathsf{p}}_{b}]\sqsubseteq[wK^{\mathsf{p}}_{a}]$
(14)

where $L^{\mathsf{p}}_{m_{\mathsf{init}}^{\mathsf{p}},m_{t}^{\mathsf{p}}}$
stands for the usual language of sequences of colors read from
$m_{\mathsf{init}}^{\mathsf{p}}$ to $m_{t}^{\mathsf{p}}$, the additional
superscript being used to highlight that we are considering skeleton
$\mathcal{M}^{\mathsf{p}}$ here. From now on, we assume w.l.o.g. that (14)
holds, i.e., that $\forall\,w\in
L^{\mathsf{p}}_{m_{\mathsf{init}}^{\mathsf{p}},m_{t}^{\mathsf{p}}},\;[wK^{\mathsf{p}}_{b}]\sqsubseteq[wK^{\mathsf{p}}_{a}]$.
Intuitively, this means that, for $\mathcal{P}_{1}$, committing to the
subarena $\mathcal{A}_{a}$ is always at least as good as committing to the
subarena $\mathcal{A}_{b}$. Note that this does not imply anything with regard
to alternating between the two subarenas, which could a priori be beneficial:
we will deal with that soon thanks to $\mathcal{M}^{\mathsf{c}}$-selectivity.

Let us define the strategy
$\sigma^{\\#}_{1}\in\Sigma^{\mathsf{ML}}_{1}(\mathcal{A})$ of
$\mathcal{P}_{1}$ in the game $\mathcal{G}=(\mathcal{A},\sqsubseteq)$ as
$\sigma^{\\#}_{1}=\sigma^{a}_{1}$, the strategy used in the NE from
$S_{\mathsf{cov}}$ in the subgame $\mathcal{G}_{a}$ (we chose this one because
of assumption (14): $\mathcal{G}_{a}$ is the better subgame of the two for
$\mathcal{P}_{1}$). Strategy $\sigma^{\\#}_{1}$ is thus memoryless by
definition. Note that $\sigma^{\\#}_{1}$ is well-defined on $\mathcal{A}$ even
though the original strategy was on $\mathcal{A}_{a}$, since it is memoryless
(i.e., whether the prefix did visit $\mathcal{A}_{b}$ or not does not matter).
Now we define a corresponding strategy
$\sigma^{\\#}_{2}\in\Sigma_{2}(\mathcal{A})$ for $\mathcal{P}_{2}$ in
$\mathcal{G}$ that uses a small amount of memory, as follows:

$\forall\,\rho\in\mathsf{Hists}_{2}(\mathcal{A}),\;\sigma^{\\#}_{2}(\rho)=\begin{cases}\sigma^{a}_{2}(\rho)\text{
if }\rho\text{ never visited }t,\\\ \sigma^{a}_{2}(\rho)\text{ if the last
visit of }t\text{ was followed by an edge in }\mathcal{A}_{a},\\\
\sigma^{b}_{2}(\rho)\text{ otherwise}.\end{cases}$

Again this strategy is well-defined on $\mathcal{A}$. Our goal is to show that
the strategy profile $(\sigma^{\\#}_{1},\sigma^{\\#}_{2})$ is an NE from all
states in $S_{\mathsf{cov}}$ in the larger game $\mathcal{G}$. In particular,
Lemma 5 implies that this profile is a couple of $S_{\mathsf{cov}}$-optimal
strategies.

Formally, we will establish that for all $s\in S_{\mathsf{cov}}$, for all
$\sigma_{1}\in\Sigma_{1}(\mathcal{A})$, for all
$\sigma_{2}\in\Sigma_{2}(\mathcal{A})$, we have

$\mathsf{\widehat{col}}(\mathsf{Plays}(\mathcal{A},s,\sigma_{1},\sigma^{\\#}_{2}))\sqsubseteq\mathsf{\widehat{col}}(\mathsf{Plays}(\mathcal{A},s,\sigma^{\\#}_{1},\sigma^{\\#}_{2}))\sqsubseteq\mathsf{\widehat{col}}(\mathsf{Plays}(\mathcal{A},s,\sigma^{\\#}_{1},\sigma_{2})).$
(15)

We begin with the rightmost inequality of Equation (15). Let $s\in
S_{\mathsf{cov}}$ and let $\sigma_{2}\in\Sigma_{2}(\mathcal{A})$ be an
arbitrary strategy for $\mathcal{P}_{2}$ in $\mathcal{G}$. We denote by
$\sigma_{2}[\mathcal{A}_{a}]$ its restriction to (histories of)
$\mathcal{A}_{a}$: note that this strategy is well-defined as only edges
belonging to $\mathcal{P}_{1}$ have been removed in $\mathcal{A}_{a}$.

We have

$\displaystyle\mathsf{\widehat{col}}(\mathsf{Plays}(\mathcal{A},s,\sigma^{\\#}_{1},\sigma^{\\#}_{2}))$
$\displaystyle=\mathsf{\widehat{col}}(\mathsf{Plays}(\mathcal{A}_{a},s,\sigma^{a}_{1},\sigma^{a}_{2}))$
$\displaystyle\text{because these strategies stay in }\mathcal{A}_{a},$
$\displaystyle\sqsubseteq\mathsf{\widehat{col}}(\mathsf{Plays}(\mathcal{A}_{a},s,\sigma^{a}_{1},\sigma_{2}[\mathcal{A}_{a}]))$
$\displaystyle\text{because }(\sigma_{1}^{a},\sigma^{a}_{2})\text{ is an NE
from }s\text{ in }\mathcal{A}_{a},$
$\displaystyle=\mathsf{\widehat{col}}(\mathsf{Plays}(\mathcal{A},s,\sigma^{\\#}_{1},\sigma_{2}))$
$\displaystyle\text{because these strategies stay in }\mathcal{A}_{a},$

hence the rightmost inequality is verified.

Now, consider the leftmost inequality of Equation (15). Let $s\in
S_{\mathsf{cov}}$ and let $\sigma_{1}\in\Sigma_{1}(\mathcal{A})$ be an
arbitrary strategy for $\mathcal{P}_{1}$ in $\mathcal{G}$. Let
$\pi\in\mathsf{Plays}(\mathcal{A},s,\sigma_{1},\sigma^{\\#}_{2})$ be the only
play consistent with $\sigma_{1}$ and $\sigma^{\\#}_{2}$ from $s$. We first
consider the case where $\pi$ never visits $t$. If this is the case, then
$\pi$ is also a play in $\mathcal{A}_{a}$. Let
$\sigma^{\prime}_{1}\in\Sigma_{1}(\mathcal{A}_{a})$ be a strategy of
$\mathcal{P}_{1}$ that mimics $\sigma_{1}$ on all histories that belong to
$\mathcal{A}_{a}$, except the ones ending in $t$, where it plays an arbitrary
edge in $E_{a}$. We have