4
$\begingroup$

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

$\endgroup$
6
  • 1
    $\begingroup$ If $A$ is closed, then for each $n$ the set of outcomes that start with $n$ is also closed. So no matter what $P_0$ plays, the game is open from the perspective of $P_1$ starting from the second move, hence determined. Now it's just a matter of putting this information together for the different possible first moves. It really all boils down to pointing out that $A \cap \{n\} \times \mathbf{N}^{\mathbf{N} - \{0\}}$ is closed in $\{n\} \times \mathbf{N}^{\mathbf{N} - \{0\}} \approx \mathbf{N}^{\mathbf{N} - \{0\}}$. $\endgroup$
    – user49640
    Jun 13, 2017 at 14:38
  • 2
    $\begingroup$ @AsafKaragila That implication is not necessarily true. If there are non-determined games, then there are some whose complement is determined. For example, consider the non-determined game with a dummy first move, where player I must play $0$ or lose immediately, and then the real game starts. The complement of this game is determined, since player I can simply fail to play $0$ and now win immediately. $\endgroup$
    – JDH
    Jun 13, 2017 at 15:15
  • $\begingroup$ @JDH: Hmm. That didn't occur to me as a possibility. $\endgroup$
    – Asaf Karagila ♦
    Jun 13, 2017 at 15:17
  • 1
    $\begingroup$ @AsafKaragila Extending that, in general, just because a set satisfies some dichotomy doesn't mean its complement does; e.g. if $X$ is a Bernstein subset of $[0, 1]$, then $(-\infty, 0]\cup X\cup [1, \infty)$ has the perfect set property but its complement is uncountable and doesn't have the perfect set property. And so on. $\endgroup$
    – Noah Schweber
    Jun 13, 2017 at 17:03
  • $\begingroup$ @Noah: Yeah, okay okay, I get it. :-) $\endgroup$
    – Asaf Karagila ♦
    Jun 13, 2017 at 17:08

1 Answer 1

Reset to default
5
$\begingroup$

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:

$\endgroup$
6
  • $\begingroup$ I understand your point about values (well not quite so well, if you read the question that follows) but how does this use the fact that the game is closed/open ? $\endgroup$
    – Maxime Ramzi
    Jun 13, 2017 at 15:37
  • $\begingroup$ If a game is not open, the game value idea doesn't work at all, since there might not be any positions with value $0$, where the game is won already at a finite stage of play. The argument only works because for an open/closed game, the only way for the open player to win is by getting to a position with value $0$. In other words, the closed player wins simply by always avoiding losing. $\endgroup$
    – JDH
    Jun 13, 2017 at 15:50
  • $\begingroup$ Ok I get it. And so in your definition, say for instance player one is the open player, then position $a_0,...,a_{2n}$ has value $\sup_{a \in \omega} \operatorname{value}(a_0,...,a_{2n},a)$, is that right ? And position $a_0...a_{2n+1}$ has value $\alpha +1$ if there is $a$ such that position $a_0...a_{2n+1},a$ has value $\alpha$ ? (I'm trying to make sure I understand) $\endgroup$
    – Maxime Ramzi
    Jun 13, 2017 at 16:23
  • 1
    $\begingroup$ Yes, that's right, except that you should use the smallest possible $\alpha$. $\endgroup$
    – JDH
    Jun 13, 2017 at 17:23
  • $\begingroup$ You said that 'if a game is not open, the game value idea doesn't work at all'. Then, are there other interesting applications of the valuation idea? $\endgroup$
    – Michael
    Aug 15, 2022 at 11:57

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .