Memory Requirements in Non-Zero-Sum Games

For $k\ge 1$, let $[k]=\{1,\mathrm{\dots },k\}$. A $k$-player (turn-based) game graph is a tuple $G=⟨{\{V_i\}}_{i\in [k]},v_0,E⟩$, where $V_1,\mathrm{\dots },V_k$ are disjoint sets of vertices. For every $i\in [k]$, the vertices in $V_i$ are owned by Player $i$, and we let $V={\bigcup }_{i\in [k]}{V}_i$. Then, $v_0\in V$ is an initial vertex, and $E\subseteq V\times V$ is a total edge relation, thus for every $v\in V$, there is $u\in V$ such that $⟨v,u⟩\in E$. For $v\in V$, we denote by $\mathrm{𝗈𝗐𝗇𝖾𝗋}(v)$ the player $i\in [k]$ such that $v\in V_i$. The size of $G$, denoted $|G|$, is $|E|$, namely the number of edges in it.

A game is a tuple $𝒢=⟨G,{\{{\alpha }_i\}}_{i\in [k]}⟩$, where $G$ is a $k$-player game graph, and ${\alpha }_i$, for $i\in [k]$, is a winning condition (a.k.a. objective) for Player $i$. In the beginning of a play in the game, a token is placed on $v_0$. Then, in each turn, the player that owns the vertex that hosts the token chooses a successor vertex and moves the token to it. Together, the players generate a play $\rho =v_0,v_1,v_2\mathrm{\dots }\in V^{\omega }$ in $𝒢$, namely an infinite path that starts in $v_0$ and respects $E$: for all $i\ge 0$, we have that $⟨v_i,v_{i+1}⟩\in E$.

Each winning condition ${\alpha }_i$ defines a subset of $V^{\omega }$. The objective of Player $i$ is to cause the interaction to generate a play that satisfies ${\alpha }_i$. We describe some types of winning conditions below. For a play $\rho =v_0,v_1\mathrm{\dots }$, we denote by $\mathrm{𝗋𝖾𝖺𝖼𝗁}(\rho )$ the set of vertices visited at least once along $\rho$, and by $\mathrm{𝗂𝗇𝖿}(\rho )$ the set of vertices visited infinitely often along $\rho$. That is, $\mathrm{𝗋𝖾𝖺𝖼𝗁}(\rho )=\{v\in V:\text{there exists some }i\ge 0\text{ such that }{v}_i=v\}$ and $\mathrm{𝗂𝗇𝖿}(\rho )=\{v\in V:$ there are infinitely many $i\ge 0$ such that $v_i=v\}$. A reachability objective is given by a set of vertices $\alpha \subseteq V$, and it requires some vertex in $\alpha$ to be visited at least once; thus a play $\rho \in V^{\omega }$ satisfies $\alpha$ iff $\mathrm{𝗋𝖾𝖺𝖼𝗁}(\rho )\cap \alpha \ne \mathrm{\varnothing }$. A Büchi objective is given by a set of vertices $\alpha \subseteq V$, and it requires some vertex in $\alpha$ to be visited infinitely often; thus $\rho$ satisfies $\alpha$ iff $\mathrm{𝗂𝗇𝖿}(\rho )\cap \alpha \ne \mathrm{\varnothing }$. The objectives dual to reachability and Büchi are avoid (also known as safety) and co-Büchi, respectively. Formally, a play $\rho$ satisfies an avoid objective $\alpha \subseteq V$ iff $\mathrm{𝗋𝖾𝖺𝖼𝗁}(\rho )\cap \alpha =\mathrm{\varnothing }$, and satisfies a co-Büchi objective $\alpha \subseteq V$ iff $inf(\rho )\cap \alpha =\mathrm{\varnothing }$. A generalized Büchi objective is a set $\alpha =\{{\alpha }_1,\mathrm{\dots },{\alpha }_m\}$ of Büchi objectives. A play $\rho \in V^{\omega }$ satisfies $\alpha$ if it satisfies all the objectives in $\alpha$; thus if for all $j\in [m]$, we have that $\mathrm{𝗂𝗇𝖿}(\rho )\cap {\alpha }_j\ne \mathrm{\varnothing }$. Generalized reachability objectives are defined similarly, requiring all underlying reachability objectives to be satisfied.

For $i\in [k]$, a strategy for Player $i$ is a function $f_i:V^{\ast }\cdot V_i\to V$ that maps prefixes of plays that end in a vertex owned by Player $i$ to possible extensions in a way that respects $E$. That is, for every history $h\in V^{\ast }$ and $v\in V_i$, we have that $⟨v,f_i(h\cdot v)⟩\in E$. Intuitively, a strategy for Player $i$ directs her how to move the token, and the direction may depend on the history of the play so far.

A profile is a tuple $\pi =⟨f_1,\mathrm{\dots },f_k⟩$ of strategies, one for each player. The outcome of a profile $\pi =⟨f_1,\mathrm{\dots },f_k⟩$ is the play obtained when the players follow their strategies. Formally, $\mathrm{𝗈𝗎𝗍𝖼𝗈𝗆𝖾}(\pi )=v_0,v_1,v_2,\mathrm{\dots }\in V^{\omega }$ is such that for all $j\ge 0$, we have that $v_{j+1}=f_{\mathrm{𝗈𝗐𝗇𝖾𝗋}(v_j)}(v_0\mathrm{\cdots }{v}_j)$. Consider a game $𝒢$ and a profile $\pi$. The set of winners in $𝒢$ when the players follow $\pi$, denoted $\mathrm{𝖶𝗂𝗇}(𝒢,\pi )$, is the set of players whose objectives are satisfied in $\mathrm{𝗈𝗎𝗍𝖼𝗈𝗆𝖾}(\pi )$. Formally, $i\in \mathrm{𝖶𝗂𝗇}(\pi ,𝒢)$ iff $\mathrm{𝗈𝗎𝗍𝖼𝗈𝗆𝖾}(\pi )$ satisfies ${\alpha }_i$. The set of losers in $\pi$, denoted $\mathrm{𝖫𝗈𝗌𝖾}(𝒢,\pi )$, is then $[k]\setminus \mathrm{𝖶𝗂𝗇}(\pi )$, namely the set of players whose objectives are not satisfied in $\mathrm{𝗈𝗎𝗍𝖼𝗈𝗆𝖾}(\pi )$. When $𝒢$ is known from the context we write $\mathrm{𝖶𝗂𝗇}(\pi )$ and $\mathrm{𝖫𝗈𝗌𝖾}(\pi )$ respectively.

For a subset $S\subseteq [k]$ of players, an $S$-profile is a set of strategies, one for each player in $S$. We say that a profile $\pi$ extends an $S$-profile ${\pi }^{\prime }$ if the players in $S$ use in $\pi$ their strategies in ${\pi }^{\prime }$. For a profile $\pi =⟨f_1,\mathrm{\dots },f_k⟩$, a non-empty subset $C\subseteq [k]$, and a $C$-profile ${\pi }_C^{\prime }={\bigcup }_{i\in C}\{f_i^{\prime }\}$, we denote by $\pi [C\leftarrow {\pi }_C^{\prime }]$ the profile in which the players in $C$ follow their strategies in ${\pi }_C^{\prime }$ and the players in $[k]\setminus C$ follow their strategies in $\pi$. Formally, $\pi [C\leftarrow {\pi }_C^{\prime }]=⟨g_1,\mathrm{\dots },g_k⟩$, where for every $i\in [k]$, we have that $g_i=f_i^{\prime }$, if $i\in C$, and $g_i=f_i$, otherwise. When $C=\{i\}$ is a singleton, for some $i\in [k]$, we simplify the notation and use $\pi [i\leftarrow f_i^{\prime }]$ rather than $\pi [\{i\}\leftarrow \{f_i^{\prime }\}]$.

A profile $\pi =⟨f_1,\mathrm{\dots },f_k⟩$ is a Nash Equilibrium (NE, for short) [26] if no single player has an incentive to deviate from $\pi$. Formally, $\pi$ is an NE if for every $i\in [k]$, if $i\in \mathrm{𝖫𝗈𝗌𝖾}(\pi )$, then for every strategy $f_i^{\prime }$ for Player $i$, we have that $i\in \mathrm{𝖫𝗈𝗌𝖾}(\pi [i\leftarrow f_i^{\prime }])$. The notion of an NE assumes deviation by single players. In some applications, a coalition of players may deviate together. The different applications induce different definitions of stability. We consider three definitions. First, a profile $\pi$ is a Strong Nash Equilibrium (SNE, for short) [3] if no coalition of players can jointly deviate in a way that strictly benefits all its members. Formally, $\pi$ is an SNE if for every non-empty subset $C\subseteq \mathrm{𝖫𝗈𝗌𝖾}(\pi )$, and every $C$-profile ${\pi }_C^{\prime }$, there exists $j\in C$ such that $j\in \mathrm{𝖫𝗈𝗌𝖾}(\pi [C\leftarrow {\pi }_C^{\prime }])$. Note that an NE is a special case of an SNE in which only deviations of coalitions of size $1$ are possible. Then, for $b_1,b_2\ge 0$, a profile is a $(b_1,b_2)$-robust equilibrium if no coalition of size $b_1$ can deviate in a way that benefits at least one of its members without harming at least one of the other members, and no coalition of size $b_2$ can deviate in a way that harms at least one of the other players [6].¹¹1The setting in [6] considers weighted objectives, where rather than winning or losing, each profile induces a payoff for each player, which enables also a quantitative definition of “harm” and “benefit”. Here we consider $\omega$-regular Boolean objectives, inducing a Boolean interpretations for “harm” and “benefit”. Formally, $\pi$ is $(b_1,b_2)$-robust if $\pi$ is $b_1$-resilient: for every subset $C\subseteq [k]$ of size at most $b_1$, and every $C$-profile ${\pi }_C^{\prime }$, if $\mathrm{𝖫𝗈𝗌𝖾}(\pi )\cap \mathrm{𝖶𝗂𝗇}(\pi [C\leftarrow {\pi }_C^{\prime }])\ne \mathrm{\varnothing }$, then $\mathrm{𝖶𝗂𝗇}(\pi )\cap \mathrm{𝖫𝗈𝗌𝖾}(\pi [C\leftarrow {\pi }_C^{\prime }])\ne \mathrm{\varnothing }$, and $\pi$ is $b_2$-immune: for every subset $C\subseteq [k]$ of size at most $b_2$, and every $C$-profile ${\pi }_C^{\prime }$, we have that $\mathrm{𝖶𝗂𝗇}(\pi )\cap \mathrm{𝖫𝗈𝗌𝖾}(\pi [C\leftarrow {\pi }_C^{\prime }])\cap ([k]\setminus C)\ne \mathrm{\varnothing }$. Finally, a profile is a strong secure equilibria (SSE) if every deviation of a coalition of players that harms some player, also harms a player in the coalition [7]. Formally, $\pi$ is an SSE if for every subset $C\subseteq [k]$, and every $C$-profile ${\pi }_C^{\prime }$, if $\mathrm{𝖶𝗂𝗇}(\pi )\cap \mathrm{𝖫𝗈𝗌𝖾}(\pi [C\leftarrow {\pi }_C^{\prime }])\cap ([k]\setminus C)\ne \mathrm{\varnothing }$, then $\mathrm{𝖶𝗂𝗇}(\pi )\cap \mathrm{𝖫𝗈𝗌𝖾}(\pi [C\leftarrow {\pi }_C^{\prime }])\cap C\ne \mathrm{\varnothing }$.

For a subset $W\subseteq [k]$ of players, we say that $\pi$ is a $W$-NE if $\pi$ is an NE with $W=\mathrm{𝖶𝗂𝗇}(\pi )$, and similarly for the other solution concepts.

We consider a setting in which the players model a controllable system and its rational environment. Technically, we assume that Player $1$ models the system (a system may be composed from several components, but since the system is controllable, we can merge them to a single player), and the other players model the components of the environment. Let $\mathrm{𝖤𝗇𝗏}=\{2,\mathrm{\dots },k\}$. The basic problem we consider is the existence and finding stable profiles that satisfy the objective of the system.

We refine the notions of NE and SNE to take into account our ability to control the system. For a profile $\pi$, we say that $\pi$ is a $1$-fixed NE if no player in $\mathrm{𝖤𝗇𝗏}$ can benefit from unilaterally changing her strategy. Likewise, we say that $\pi$ is a $1$-fixed SNE if no coalition of players in $\mathrm{𝖤𝗇𝗏}$ can jointly deviate in a way that strictly benefits all its members.

Consider a $k$-player game $𝒢$. The problem of NE (SNE) cooperative rational synthesis, denoted NE-CRS (resp., SNE-CRS) is to return a $1$-fixed NE (resp., SNE) in $𝒢$ in which Player $1$ wins. As in traditional synthesis, one can also define the corresponding decision problems, of rational realizability, where we only need to decide whether the desired strategies exist. In order to avoid additional notations, we sometimes refer to NE-CRS and SNE-CRS also as decision problems.

A strategy $f_i:V^{\ast }\to V$ is finite-memory if it is possible to replace the unbounded histories in $V^{\ast }$ by finitely many memories. Formally, a memory structure for a game $𝒢=⟨G,{\{{\alpha }_i\}}_{i\in [k]}⟩$ with $G=⟨{\{V_i\}}_{i\in [k]},v_0,E⟩$ is $ℳ=⟨M,{\mu }_0,\delta ⟩$, consisting of a finite set $M$ of memory states, an initial memory state ${\mu }_0\in M$, and an update function $\delta :M\times E\to$ $M$. A memory structure is similar to an automaton with alphabet $E$, which is executed in parallel to the game: it starts in ${\mu }_0$ and reads the edges traversed by the token. Then, a strategy for Player $i$ that relies on $ℳ$ replaces the dependency on the history of the play by dependency on the current memory state of $ℳ$. Thus, the strategy is given by a function $f_i:M\times V_i\to V$, such that for all $\mu \in M$ and $v\in V_i$, we have that $⟨v,f_i(\mu ,v)⟩\in E$. When the current memory state is $\mu$ and the token is in vertex $v\in V_i$, Player $i$ moves the token to $f_i(\mu ,v)$ and $ℳ$ moves to state $\delta (\mu ,⟨v,f_i(\mu ,v)⟩)$. A strategy $f_i$ is memoryless if it only depends on the current vertex. That is, if for every two histories $h,h^{\prime }\in V^{\ast }$ and vertex $v\in V_i$, we have that $f_i(h\cdot v)=f_i(h^{\prime }\cdot v)$. Note that a memoryless strategy can be viewed as a function $f_i:V_i\to V$, and corresponds to the case $|M|=1$. An objective type $\gamma$ is called memoryless if in every zero-sum game with an objective of type $\gamma$, if Player $1$ wins, then she has a memoryless winning strategy. Reachability, avoid, Büchi, and co-Büchi objectives are all memoryless [30].

For $l\ge 1$, we say that a strategy $f_i:V^{\ast }\cdot V_i\to V$ uses memory $l$ if a memory structure that generates $f_i$ needs $l$ states. Given a profile $\pi =⟨f_1,\mathrm{\cdots },f_k⟩$, we say that Player $i$ uses memory $l$ (in $\pi$) if $f_i$ uses memory $l$.

We describe ${𝒢}_1$ and ${𝒢}_2$ with Büchi objectives. The same games and considerations apply when the games have reachability objectives. Consider the Büchi game ${𝒢}_1$ in Figure 1 (left). Let ${\alpha }_1=\{v_3\}$ and ${\alpha }_2=\{v_1,v_4\}$. Drawing two-player games we use circles and boxes to describe the vertices in $V_1$ and $V_2$, respectively.

Consider the strategy $f_1$ for Player $1$ that, in $v_2$, alternates between $v_3$ and $v_4$. That is $f_1(v_0,v_2,{(v_3,v_2,v_4,v_2)}^{\ast })=v_3$ and $f_1(v_0,v_2,{(v_3,v_2,v_4,v_2)}^{\ast },v_3,v_2)=v_4$. Note that in order to implement the alternation, the strategy $f_1$ requires a memory of size $2$. Consider the strategy $f_2$ for Player $2$ that, in $v_0$, takes the token down to $v_2$. Note that the profile $⟨f_1,f_2⟩$ is a CRS solution. Indeed, its outcome is $v_0,{(v_2,v_3,v_2,v_4)}^{\omega }$, which visits both $v_3$ and $v_4$ infinitely often. Thus, both objectives are satisfied, and the profile is a CRS solution.

On the other hand, consider a memoryless strategy for Player $1$. If, in $v_0$, Player $2$ moves the token to $v_1$, then the play reaches and stays forever in $v_1$ no matter what the strategy of Player $1$ is, and ${\alpha }_1$ is not satisfied. If, in $v_0$, Player $2$ moves the token to $v_2$, then either, in $v_2$, Player $1$ always moves the token to $v_4$, in which case the play never visits $v_3$, and so ${\alpha }_1$ is not satisfied, or Player $1$ always moves the token to $v_3$, in which case ${\alpha }_2$ is not satisfied, causing Player $2$ to deviate in $v_0$. Thus, there is no CRS solution in which Player $1$ uses a memoryless strategy.

Consider now the Büchi game ${𝒢}_2$ in Figure 1 (right). Let ${\alpha }_1=\{v_3\}$ and ${\alpha }_2=\{v_1,v_4\}$. Note that all the vertices with more than one successor belong to Player $2$, and so there is a single strategy $f_1$ for Player $1$ in the game. Consider the strategy $f_2$ for Player $2$ that, in $v_0$, takes the token down to $v_2$, and, in $v_2$, alternates between $v_3$ and $v_4$. That is $f_2(v_0,v_2,{(v_3,v_2,v_4,v_2)}^{\ast })=v_3$ and $f_2(v_0,v_2,{(v_3,v_2,v_4,v_2)}^{\ast },v_3,v_2)=v_4$. Note that in order to implement the alternation, the strategy $f_2$ requires a memory of size $2$. It is easy to see that the profile $⟨f_1,f_2⟩$ is a CRS solution. Indeed, its outcome is $v_0,{(v_2,v_3,v_2,v_4)}^{\omega }$, which satisfies both objectives.

On the other hand, consider a memoryless strategy for Player $2$. If, in $v_0$, Player $2$ moves the token to $v_1$, then the play reaches and stays forever in $v_1$ and ${\alpha }_1$ is not satisfied. If, in $v_0$, Player $2$ moves the token to $v_2$, then either, in $v_2$, Player $2$ always moves the token to $v_4$, in which case ${\alpha }_1$ is not satisfied, or Player $2$ always moves the token to $v_3$, in which case ${\alpha }_2$ is not satisfied, causing Player $2$ to deviate in either $v_0$ or $v_2$. Thus, there is no CRS solution in which Player $2$ uses a memoryless strategy. $◀$

The example of ${𝒢}_2$ in Theorem 1 shows that increasing the memory of the environment may help the system to achieve a CRS solution. We continue and examine whether this is always the case. We first need some notations. Consider a non-zero-sum game $𝒢=⟨G,{\{{\alpha }_i\}}_{i\in [k]}⟩$. For $m\ge 1$, we say that a profile $\pi =⟨f_1,f_2,\mathrm{\dots },f_k⟩$ is an $m$-bounded $1$-fixed NE if for every $2\le i\le k$, the strategy $f_i$ uses memory at most $m$, and if $i\in \mathrm{𝖫𝗈𝗌𝖾}(\pi )$, then for every strategy $f_i^{\prime }$ for Player $i$ that uses memory at most $m$, we have that $i\in \mathrm{𝖫𝗈𝗌𝖾}(\pi [i\leftarrow f_i^{\prime }])$. Thus, environment players are restricted to strategies that use memory at most $m$, in both $\pi$ and their deviations. Likewise, $\pi$ is an $m$-bounded $1$-fixed SNE if all the strategies of the environment players in $\pi$ use memory at most $m$ and no coalition of environment players can jointly deviate to strategies that use memory at most $m$ in a way that strictly benefits all its members. Then, we say that $\pi$ is an $m$-bounded NE-CRS (SNE-CRS) solution if $\pi$ is an $m$-bounded $1$-fixed NE (SNE, respectively) that satisfies ${\alpha }_1$. Note that the usual CRS problem coincides with the case $m=\mathrm{\infty }$.

We first show that, unsurprisingly, when the objectives of the environment players require memory, in particular when they consist of a conjunction of objectives, then a system may have a CRS solution only thanks to bounds on the memory of the environment players.

We prove the theorem for the Büchi case. The same game and considerations apply for generalized-reachability objectives.²²2The application to reachability is less straightforward here. In particular, for Büchi, one could give up the vertex $v_2$ and let $v_0$ have three successors. For reachability, we need the decision of Player $2$ about not visiting $v_1$ in her first transition to be un-recoverable. Consider the generalized Büchi game ${𝒢}_3$ played on the graph of ${𝒢}_2$ (Figure 1, right), now with ${\alpha }_1=\{\{v_1\}\}$ and ${\alpha }_2=\{\{v_3\},\{v_4\}\}$. Note that Player $1$ has a Büchi objective.

Recall that all the vertices with more than one successor belong to Player $2$, and so there is a single strategy $f_1$ for Player $1$ in the game. Consider the strategy $f_2$ for Player $2$ that, in $v_0$, takes the token to $v_1$, where it loops forever. Clearly, the induced play satisfies ${\alpha }_1$. When Player $2$ is restricted to memoryless strategies, it cannot satisfy her objectives, making this profile a $1$-bounded CRS solution. On the other hand, when Player $2$ is not memoryless, she can take the token down to $v_2$ and then alternate between $v_3$ and $v_4$. Hence, when Player $2$ has memory $2$ or more, she would deviate from every profile that leads to $v_0$, and so there is no CRS solution in ${𝒢}_3$. $◀$

The example of ${𝒢}_3$ in the proof of Theorem 2 heavily relies on Player $2$ having an objective that requires memory. We now show that for SNE-CRSs, when a deviation of a player may need to be beneficial to several players, a system may have an SNE-CRS solution only thanks to bounds on the memory of the environment players, even when all players have memoryless objectives.

We prove the theorem for the Büchi case. The same game and considerations apply for reachability objectives. Consider the $3$-players Büchi game ${𝒢}_4$ in Figure 2. We use diamonds to denote vertices controlled by Player $3$. Let ${\alpha }_1=\{v_1\}$, ${\alpha }_2=\{v_3\}$, and ${\alpha }_3=\{v_4\}$.

Note that all the vertices with more than one successor belong to Player $2$ or Player $3$, and so there is a single strategy $f_1$ for Player $1$ in the game. We first describe a $1$-bounded SNE-CRS solution for ${𝒢}_4$. Let $f_2$ be the memoryless strategy for Player $2$ that, in $v_0$, takes the token to $v_1$ and, in $v_2$, take the token to $v_3$. Let $f_3$ be the memoryless strategy for Player $3$ that loops in $v_5$. Clearly, $\mathrm{𝗈𝗎𝗍𝖼𝗈𝗆𝖾}(\pi )=v_0,v_1^{\omega }$, and so $\mathrm{𝖶𝗂𝗇}(\pi )=\{1\}$. We prove that Player $2$ and Player $3$ cannot deviate to memoryless strategies in a way that causes their objectives to be satisfied. Clearly, a deviation by Player $3$ alone cannot affect the outcome of the game. Also, a deviation by Player $2$ alone may not cause the outcome to reach $v_3$ or $v_4$. Consider now a joint deviation of Player $2$ and Player $3$. When Player $2$ uses a memoryless strategy, it cannot cause the outcome of the profile to visit both $v_3$ and $v_4$ infinitely often. Thus, the deviation is not beneficial to either Player $2$ and Player $3$. Hence, $\pi$ is a $1$-bounded SNE-CRS solution.

On the other hand, when Player $2$ has memory $m\ge 2$, then for every profile whose outcome reaches $v_1$, Player $2$ and Player $3$ would deviate to an outcome that satisfies their both objectives, and so no SNE-CRS solution exists for ${𝒢}_4$. $◀$

We now complete the picture and show that when the objective of the environment players are memoryless and deviations are allowed only for single players, then adding memory to the environment may only help the system. Thus, for NE-CRS with memoryless objectives, we cannot have examples as those in Theorems 2 and 3.

Consider a Büchi (or reachability) game $𝒢=⟨G,{\{{\alpha }_i\}}_{i\in [k]}⟩$. Let $\pi =\{f_1,f_2,\mathrm{\dots },f_k\}$ be a $1$-bounded NE-CRS solution. We prove that there exists a strategy $g_1$ for Player $1$ such that the profile ${\pi }^{\prime }=\pi [1\leftarrow g_1]$ is an NE-CRS solution.³³3In Appendix A.1, we show that the transition to $g_1$ is essential, thus $\pi$ need not be an NE-CRS solution. In fact, the example is stronger, showing that a profile $\pi$ may be a $1$-bounded NE-CRS solution and still no profile in which the system follows its strategy in $\pi$ is an NE-CRS solution. We also show that the strategy of Player $1$ in a $1$-bounded NE-CRS solution may require memory of size $2$.

For every $i\in \mathrm{𝖤𝗇𝗏}$, let $G^{\pi ,i}$ be the graph obtained from $G$ by removing edges that leave vertices in $V_j$ that do not agree with the memoryless strategy $f_j$, for all $j\in [k]\setminus \{1,i\}$. Consider the zero-sum two-player game ${𝒢}^{\pi ,i}=⟨G^{\pi ,i},{\alpha }_i⟩$ between Player $i$ and Player $1$. Let $W_i\subseteq V$ be the winning region of Player $i$ in ${𝒢}^{\pi ,i}$, and let $f_i^{\prime }$ be a memoryless strategy for Player $i$ for the vertices in $W_i$. That is, $v\in W_i$ iff for every strategy $f_1^{\prime }$ for Player $1$, the outcome in ${𝒢}^{\pi ,i}$ of $f_i^{\prime }$ and $f_1^{\prime }$ from $v$ satisfies ${\alpha }_i$. Likewise, let $f_1^i$ be a memoryless strategy for Player $1$ in ${𝒢}^{\pi ,i}$ that is winning in all vertices not in $W_i$. That is, $v\notin W_i$ iff for every strategy $g_i$ for Player $i$, the outcome in ${𝒢}^{\pi ,i}$ of $g_i$ and $f_1^i$ from $v$ does not satisfy ${\alpha }_i$. Note that since ${\alpha }_i$ is a Büchi objectives, memoryless strategies $f_i^{\prime }$ and $f_1^i$ exist.

Let $\rho =v_0,v_1,v_2,\mathrm{\dots }=\mathrm{𝗈𝗎𝗍𝖼𝗈𝗆𝖾}(\pi )$. We first argue that for all $i\in \mathrm{𝖫𝗈𝗌𝖾}(\pi )$ and vertices $v\in \mathrm{𝗋𝖾𝖺𝖼𝗁}(\rho )\cap V_i$, we have that $v\notin W_i$. To see this, assume by way of contradiction that there exists $i\in \mathrm{𝖫𝗈𝗌𝖾}(\pi )$ and a vertex $v\in \mathrm{𝗋𝖾𝖺𝖼𝗁}(\rho )\cap V_i$ such that $v\in W_i$. Let $v=v_j$ be the first such vertex. That is, $v_0,\mathrm{\dots },v_{j-1}$ are all not in $W_i$ and $v_j\in W_i$. Consider the strategy $g_i$ for Player $i$ that agrees with $f_i$ in the vertices $v_0,\mathrm{\dots },v_{j-1}$ and agrees with $f_i^{\prime }$ in all other vertices. Consider the profile ${\pi }_i^{\prime }=\pi [i\leftarrow g_i])$. Note that $g_i$ is memoryless, $\mathrm{𝗈𝗎𝗍𝖼𝗈𝗆𝖾}({\pi }_i^{\prime })$ has a prefix $v_0,\mathrm{\dots },v_j$, and, as $f_i^{\prime }$ is winning in ${𝒢}^{\pi ,i}$, the outcome continues in a way that satisfies ${\alpha }_i$. Thus, $i\in \mathrm{𝖶𝗂𝗇}(\pi [i\leftarrow g_i])$, contradicting the fact that $\pi$ is a $1$-bounded $1$-fixed NE.

We can now define the strategy $g_1$, as follows. As long as the generated play follows $\rho$, then $g_1$ agrees with $f_1$. If for some $i\in \mathrm{𝖤𝗇𝗏}$ and vertex $v\in \mathrm{𝗋𝖾𝖺𝖼𝗁}(\rho )\cap V_i$, Player $i$ deviates and moves the token to a successor of $v$ that is different from $f_i(v)$, then $g_1$ follows the strategy $f_1^i$ for the rest of the game. Note that $g_1$ need not be memoryless (even when $f_1$ is memoryless).

We argue that the profile ${\pi }^{\prime }=\pi [1\leftarrow g_1]$ is an NE-CRS solution. First, since $g_1$ agrees with $f_1$ as long as the environment players follow their strategies in $\pi$, then $\mathrm{𝗈𝗎𝗍𝖼𝗈𝗆𝖾}({\pi }^{\prime })=\mathrm{𝗈𝗎𝗍𝖼𝗈𝗆𝖾}(\pi )$, and so $\mathrm{𝖶𝗂𝗇}({\pi }^{\prime })=\mathrm{𝖶𝗂𝗇}(\pi )$. Thus, $1\in \mathrm{𝖶𝗂𝗇}({\pi }^{\prime })$. It is left to show that ${\pi }^{\prime }$ is a $1$-fixed NE. Consider a player $i\in \mathrm{𝖫𝗈𝗌𝖾}(\pi )$ and a strategy $f_i^{\prime }$ for Player $i$. Let $h\cdot v\in V^{\ast }\cdot V_i$ be the longest prefix of $\mathrm{𝗈𝗎𝗍𝖼𝗈𝗆𝖾}({\pi }^{\prime }[i\leftarrow f_i^{\prime }])$ that agrees with $\rho$. Thus, $f_i^{\prime }(h\cdot v)\ne f_i(v)$, and so, by its definition, the strategy $g_1$ starts to follow the strategy $f_1^i$ after the history $h\cdot v$. Since $v\in \mathrm{𝗋𝖾𝖺𝖼𝗁}(\rho )\cap V_i$, then $v\notin W_i$. Therefore, the strategy $f_1^i$ is winning in ${𝒢}^{\pi ,i}$ when the game starts in $v$. Hence, $\mathrm{𝗈𝗎𝗍𝖼𝗈𝗆𝖾}({\pi }^{\prime }[i\leftarrow f_i^{\prime }])$ does not satisfy ${\alpha }_i$, and so $f_i^{\prime }$ is not a beneficial deviation for Player $i$. Thus, ${\pi }^{\prime }$ is an NE-CRS solution, and we are done. $◀$

We define ${𝒢}_k$ as follows (see an illustration for the case $k=4$ in Figure 3).

A play in $G_k$ starts at the initial vertex $d_2$. For each $i\in \mathrm{𝖤𝗇𝗏}$, Player $i$ controls the vertex $d_i$ and decides whether to move the token to $d_{i+1}$ or to a vertex $c_j$ for some $j\in \mathrm{𝖤𝗇𝗏}\setminus \{i\}$. For each $j\in \mathrm{𝖤𝗇𝗏}$, Player $j$ also controls the vertex $c_j$. From $c_j$, Player $j$ chooses a successor $s_i$ for some $i\in \mathrm{𝖤𝗇𝗏}$. The vertex $s_i$ is a sink that satisfies the objectives of all players in $\mathrm{𝖤𝗇𝗏}\setminus \{i\}$. The vertex $d_{k+1}$ is a sink that satisfies the objective of Player $1$.

Note that the only play in which Player $1$ achieves her objective is $d_2,d_3,\mathrm{\dots },d_k,{(d_{k+1})}^{\omega }$, in which all players in $\mathrm{𝖤𝗇𝗏}$, when controlling their $d_i$ vertices, choose to move the token towards $d_{k+1}$. If for some $i\in \mathrm{𝖤𝗇𝗏}$, Player $i$ instead chooses to move the token to a vertex $c_j$ for some $j\in \mathrm{𝖤𝗇𝗏}\setminus \{i\}$, then Player $j$ can move the token from $c_j$ to $s_i$, making the deviation non-beneficial for Player $i$. Thus, an NE-CRS solution for ${𝒢}_k$ consists of strategies that direct the token to $d_{k+1}$ and “punish” players that do not follow such a direction. Consider $j\in \mathrm{𝖤𝗇𝗏}$. In order to punish Player $i$ by moving the token from $c_j$ to $s_i$, Player $j$ has to remember the vertex from which the token has reached $c_j$. Since there are $k-2$ such possible vertices, ${𝒢}_k$ has a NE-CRS solution where the strategy of each player uses $k-2$ memory. Also, if for some $i\in [k]$, the strategy of Player $i$ has a memory smaller than $k-2$, then there exists a player $j\in \mathrm{𝖤𝗇𝗏}\setminus \{i\}$ that can move from $d_j$ to $c_i$ without being punished, which implies that the profile is not an NE-CRS solution.

In Appendix A.2, we describe ${𝒢}_k$ and prove the bounds formally. $◀$