4
$\begingroup$

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?

$\endgroup$
3
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ If $x \in UA^{\mathbb N}$, then $x = uy$ with $u \in U$, and $\rho(u) = 0$, hence we have a prefix where the value of $\rho$ is finite, so by contraposition if $\rho(u) = \infty$ for each prefix, then the infinite word with these prefixes could not be in $X$. But just that some prefix $u$ of $x$ has the property that $\rho(u) = k <\infty$ does not imply $x \in X$, ist just says that $u$ could be completed to give a word from $U$, but in $x$ the tokens behind $u$ does not have to equal this completion from $U$, hence this is somewhat broad. $\endgroup$ – StefanH Aug 2 '16 at 17:07
  • $\begingroup$ Also if $A$ is finite, for example $A = \{a,b\}$, and $\rho(\sigma a) = i$ and $\rho(\sigma b) = j$ where $\sigma$ has odd length, then take $k := \max\{i,j\}$ which gives $\sigma a, \sigma b \in W_k$, hence $\sigma \in W_{k-1}$. This gives your second property which might break down for infinite $A$ (unfortunately I do not know ordinals so I could not follow all your remarks, but maybe will get them in the future). $\endgroup$ – StefanH Aug 2 '16 at 17:09
  • $\begingroup$ The assumption that $A$ is finite is in the first sentence of the question. $\endgroup$ – Andreas Blass Jun 24 '18 at 21:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.