Gale-Stewart Theorem (open games are determined) implies closed games are determined

1.1k Views Asked by At

A Gale-Stewart game $G(A)$ is played on a set $A\subseteq\mathbb N^\mathbb N$. In this game, players p0 and p1 alternately pick a natural number, forming a sequence $\alpha:=\alpha_0\alpha_1\alpha_2\ldots$ The goal of p0 is to form a sequence that is in $A$, p1's goal is to prevent this. A strategy for p0 then is a function that maps all finite sequences (words) of even length onto a natural number indicating p0's next move. Analogously, a strategy for p1 can be defined. A game $G(A)$ is called determined if there exists a strategy for either p0 or p1 that yields a certain win for him.

Now the Gale-Stewart theorem says that if $A$ is an open set, then $G(A)$ is determined. It seems logical (and is indeed true) that if $A$ is closed, then $G(A)$ is also determined, by considering a winning strategy $f$ in $G(\mathbb N^\mathbb N\setminus A)$ for p0, $f$ can be a winning strategy for p1 in $G(A)$. However, $f$ is a function from all words of even length to $\mathbb N$, and for it to be a strategy for p1, it must be a functions over words of odd length.

Now my question is, how can I easily see that if $A$ is closed, then also $G(A)$ is determined, as a corollary of the Gale-Stewart Theorem

1

There are 1 best solutions below

6
On BEST ANSWER

As I mentioned in the comments, it is not generally true that if a game is determined, then its complement is determined (unless all games are determined).

So one doesn't prove closed determinacy simply by moving to the complement like that. Rather, what you do is prove open determinacy by the usual method by considering the open player, regardless of whether that player is first or second. When the open player is second, then this is technically a closed game.

Another way to think about it is that a closed game is really a whole spectrum of open games, one for each possible move for the first player. Each first play leads in effect to an open game whose "first" move is really the second move in the first game, and by considering the various possibilities, you can get determinacy that way. This is what user49640 was suggesting in the comments.

My favorite way to prove open/closed determinacy is by means of assigning ordinal game values to positions, from the perspective of the open player (regardless of whether that player is first or second). The already-won positions have value $0$, and then a position is value $\alpha+1$ if the open player can move to a position with (minimal) value $\alpha$, and when it is the other player's turn, take suprema. From any position with a value, the open player can win by playing to reduce value. If a position has no value, the closed player can win by maintaining that.

One can read a little more about the concrete meaning of ordinal game values in section 1 of my paper: