Question on proof that Gale-Stewart game is determined for open sets

371 Views Asked by At

An infinite game of perfect information consists of a finite set $A$ of moves, two players and a set $X \subseteq A^{\mathbb N}$ of winning conditions for player I. By convention player I makes the first move by choosing some $x_1 \in A$, then player I chooses some $x_2 \in A$, then player I some $x_3 \in A$ and so on, and by this we get a sequence $x = x_1 x_2 x_3 \cdots$. We say that player I wins if $x \in X$, otherwise player II wins. A game is determined if some player possesses a winning strategy, i.e. a selection of moves which makes him a winning player regardless of the action of the other player. More information could be read on wikipedia.

Now if $X$ is open in the product topology on $A^{\mathbb N}$, i.e. if $X = U\cdot A^{\mathbb N}$ for some set $U$ of finite sequence over $A$ (i.e. every infinite sequence from $X$ has some finite initial prefix in $U$, and converse if some finite prefix is in $U$ the sequence belongs to $X$) then the game is determined.

Proof. Let $X = UA^{\mathbb N}$ We define a sequence $W_i$ of finite sequence over $A$ by $W_0 := U$ and for $i \ge 0$ \begin{align*} W_{i+1} = W_i & \cup \{ w \mbox{ has even length } \mid wa \in W_i \mbox{ for some } a \in A \} \\ & \cup \{ w \mbox{ has odd length } \mid wa \in W_i \mbox{ for every } a \in A \} \end{align*} and then define $\rho(x) := \min\{ i \ge 0 \mid x \in W_i\}$ with the convention $\min \emptyset = \infty$. Denote by $1$ the empty sequence, then player I has a winning strategy if $\rho(1)$ is finite, and player II has a winning strategy if $\rho(1) = \infty$. $\square$

(the proof is taken from here).

I do not understand why if $\rho(1) = \infty$, that player II has a winning strategy? If $\rho(1) = i$, then by definition $a \in W_i$ for some $a \in A$ and $a \notin W_0 \cup \cdots \cup W_{i-1}$. Then $a \in W_i \setminus (W_0 \cup \ldots \cup W_{i-1})$ implies $ab \in W_{i-1}$ for all $b \in A$, and continuing we have $ab \in W_{i-1} \setminus (W_0 \cup \cdots W_{i-2})$ which gives $abc \in W_{i-2}$ for some $c \in A$, and so on giving some finite sequence $w$ in $W_0 = U$, hence any sequence with prefix $w$ is a run of the game that player I wins. But I do not see that if $\rho(1) = \infty$ that player II has a winning strategy?

1

There are 1 best solutions below

3
On BEST ANSWER

The proof as given actually looks wrong to me - I think they need to continue the construction of the $W_i$s into the transfinite (that is, they need $W_\omega$, $W_{\omega+1}$, etc.). The other possibility is that there is an assumption somewhere that $A$ is finite, in which case the proof does work.

Specifically, we define $W_\alpha$ for $\alpha$ an ordinal similarly to the finite case; the exception being at limit stages, where - for $\lambda$ limit - we set $W_\lambda=\bigcup_{\alpha<\lambda}W_\alpha$.

We then write "$\rho(\sigma)=\alpha$" if $\sigma\in W_\alpha$ and $\alpha$ is the least such ordinal, and we write "$\rho(\sigma)=\infty$" as an abbreviation for "$\sigma$ is not in $W_\alpha$ for any ordinal $\alpha$." If quantifying over all ordinals worries you - and it probably should! - note that we can show that we only need ordinals up to $\omega^{\vert A\vert}$.

Note that this broader definition makes it harder to show that player I wins if $\rho(1)\not=\infty$, but not too much harder: just show that player I can play to always make the rank decrease, and then use the fact that the ordinals are well-founded.


Here's how the proof goes with the broader class of $W_i$s in hand:

HINT: Show that:

  • If $\sigma$ is a string of even length (so it's I's turn) and $\rho(\sigma)=\infty$, then for every $a$ we have $\rho(\sigma a)=\infty$ as well.

  • If $\sigma$ is a string of odd length (so it's II's turn) and $\rho(\sigma)=\infty$, then there is some $a$ such that $\rho(\sigma a)=\infty$.

(Why does this break down with just the finite $W_i$s? Well, it could be that there is some node $\sigma$ of odd length such that no matter what II plays, they land in some $W_i$; but they get to choose which $W_i$ they land in (that is, they can play to land in $W_{17}$ but not $W_{16}$, for instance). Then this node has $\rho$ not finite, but we need $\rho\not=\infty$ here since the rank drops no matter what II does. This could be avoided if they assumed that the symbol set $A$ is finite, but I don't see that they do that. It is, however, a good exercise to show that if $A$ is finite, then the results above actually hold true even for the narrower class of $W_i$s they consider.)

With this in hand, player II's winning strategy is just to always keep $\rho=\infty$; that is, if it is player II's turn to play and the current state of the game is $\sigma$, player II will play some $a$ such that $\rho(\sigma a)=\infty$ if such an $a$ exists. (If no such $a$ exists, they'll do whatever.)

So what? Well, with the result from the hint, think about what happens if $\rho(1)=\infty$. If player II plays as above, and player I does anything, will the game ever reach a state $\sigma$ with $\rho(\sigma)\not=\infty$? What does this say about who wins the play?