Mikołaj Bojańczyk

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:

trojpodzial

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:

partition of 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:

partition of u

 

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:

ostateczny-podzial copy

 

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.

 

Leave a Reply

Your email address will not be published.