Memoryless determinacy of parity games

Mikołaj Bojańczyk

zajęcia / courses

Memoryless determinacy of parity games

In this page, we prove the following theorem:

Theorem (Memoryless Determinacy of Parity Games). In a parity game, one of the players has a memoryless winning strategy.

Recall that in a parity game, the positions are assigned ranks from a set $\set{0,\ldots,n}$ , and the goal of player 0 is to ensure that for infinite plays, the minimal number appearing infinitely often is even. The proof of the theorem is by induction on the number of ranks used in the parity game.

Attractors

Consider a set of positions $X$ in a parity game (actually the winning condition is irrelevant for the definition). For a player $i \in \set{0,1}$ , we define below the $i$ -attractor of $X$ , which intuitively represents positions where player $i$ can force a visit to the set $X$ . The attractor is approximated using ordinal numbers – for an ordinal number $\alpha$ , define $X_\alpha$ to be $X$ plus
• positions owned by player $i$ where some outgoing edge leads to $\bigcup_{\beta < \alpha} X_\beta$ ;
• positions owned by the opponent of $i$ where all outgoing edges lead to $\bigcup_{\beta < \alpha} X_\beta$ .
The set $X_\alpha$ grows as $\alpha$ grows, and therefore at some point it stabilises. This stable set is called the $i$ -attractor of $X$ . Over positions in the $i$ -attractor, player $i$ has a memoryless strategy which guarantees that after a finite number of steps, the game will end up in $X$ or in a terminal position owned by the opponent of player $i$ . This strategy, called the attractor strategy, is to go toward $X_\alpha$ with smaller and smaller index $\alpha$ .

Induction base.

The induction base is when only one rank is used. Let $i$ be the parity of the only rank, without loss of generality we assume $i \in \set{0,1}$ . This means that every infinite play is won by player $i$ . This does not necessarily mean that player $i$ wins the game, because the game might end up in a terminal position owned by player $i$ . Let $X$ be the $(1-i)$ -attractor of the empty set. We claim that on positions from $X$ , player $1-i$ has a memoryless winning strategy, and on positions outside $X$ , player $i$ has a memoryless winning strategy. For positions in $X$ , player $(1-i)$ plays the attractor strategy, which guarantees reaching a terminal position owned by player $i$ in a finite number of steps. For positions outside $X$ , we make the following observation, which follows immediately from the definition of $X$ :
• if player $i$ owns a position outside $X$ , then some outgoing edge leads to a position outside $X$ ;
• if player $1-i$ owns a position outside $X$ , then all outgoing edges lead to a position outside $X$ .
It follows that if the play begins outside $X$ , then player $i$ has a memoryless strategy that guarantees avoiding $X$ forever, in particular this strategy is winning.

Induction step

The proof is by induction on the number of ranks used

Consider a parity game. For $i \in \set{0,1}$ define $W_i$ to be the set of positions $v$ such that if the initial position is replaced by $v$ , then player $i$ has a memoryless winning strategy. Define $U$ to be the vertices that are in neither $W_0$ nor in $W_1$ . Our goal is to prove that $W$ is empty. Here is the picture:

Consider the minimal rank that appears in the entire game, let it be $n$ . By symmetry, we assume that this minimal rank is $0$ . (The symmetric case is when the minimal rank is $1$ .) Define $A$ to be the $0$ -attractor, inside the game limited to $U$ , of positions that are in $U$ and have minimal rank $0$ . Here is the picture of the game restricted to $U$ :

In the original game, if the play begins in a position from $A$ and player $0$ plays the attractor strategy on the set $A$ , then the play is bound to either end up in a position in $U$ that has rank $0$ , or in the set $W_0$ . Let us consider the game restricted to set $U-A$ . Since this game does not use rank $0$ , the induction assumption can be applied to get a partition of $U - A$ into two sets of positions $U_0$ and $U_1$ , such that on each $U_i$ player $U_i$ has a memoryless winning strategy, assuming that the game is limited to $U - A$ :

Here is how the sets $U_0,U_1$ can be interpreted in terms of the bigger original game. For every $i \in \set{0,1}$ , if in the original game, if the play begins in a position from $U_i$ and player $i$ uses the memoryless winning strategy corresponding to $U_i$ , then either the play stays forever in $U-A$ and player $i$ wins, or it eventually leaves $U-A$ .

Here is a picture of the original game with all sets:

Claim. $U_1$ is empty.

Proof. Consider the following memoryless strategy for player $1$ in the original game:
• in $U_1$ , use the winning memoryless strategy inherited from the game restricted to $U-A$ ;
• in $W_1$ , use the winning memoryless strategy from the definition of that set;
• on other positions do whatever.
We claim that the above memoryless strategy is winning for all positions from $U_1$ , and therefore $U_1$ must be empty by assumption on $W_1$ being all positions where player $1$ can win in a memoryless way. Suppose player $1$ plays the above strategy, and the play begins in $U_1$ . If the play never leaves $U - A$ , then player $1$ wins by assumption on the strategy. Suppose that the play does leave $U-A$ . If it enters $W_0$ or $A$ , this would have to be a choice of player $0$ , but positions with such a choice already belong to $W_0$ or $A$ . Therefore, if the play leaves $U-A$ , then it enters $W_1$ , where player $1$ wins as well. $\Box$

In the entire game, consider now the following memoryless strategy for player $0$ :
• in $U_0$ , use the winning memoryless strategy inherited from the game restricted to $U-A$ ;
• in $W_0$ , use the winning memoryless strategy from the definition of that set;
• in $A$ use the attractor strategy to reach rank $0$ inside $U$ ;
• on other positions, i.e. on $W_1$ , do whatever.

We claim that the above strategy wins on all positions except for $W_1$ , and therefore the theorem is proved. We first observe that the play can never enter $W_1$ , because this would have to be a choice of player $1$ , and such choices are only possible in $W_1$ . Next we observe that if the play enters $W_0$ , then player $0$ wins by assumption on $W_0$ . Other plays will reach positions of rank $0$ infinitely often, by using the attractor, or will stay in $U_0$ from some point on. In the first case, player $0$ will win by the assumption on $0$ being the minimal rank. In the second case, player $0$ will win by the assumption on $U_0$ being winning for the game restricted to $U-A$ .

zajęcia / courses

Memoryless determinacy of parity games

Memoryless determinacy of parity games

Leave a Reply