For the purpose of this post, I will say that the Gale-Stewart game is the infinite two-player game of perfect information where players I and II alternate playing natural numbers, with I going first. A round of the game looks like: I plays $n_0$, II plays $n_1$, I plays $n_2$, II plays $n_3$, etc. The outcome of this round is the sequence $(n_i)_{i\in\omega}\in\omega^\omega$.

Given a set $A\subseteq\omega^\omega$, I will speak of a player having a strategy for playing into $A$, rather than using the usual winning/losing terminology. If $\sigma$ is a strategy for one of the players, I denote by $[\sigma]\subseteq\omega^\omega$ the set of all outcomes of the game when that player follows $\sigma$.

Question: Suppose we are given a set $C\subseteq\omega^\omega\times\omega^\omega$. Under which circumstances do there exists strategies $\sigma$ and $\tau$ for players (either one) in the Gale-Stewart game such that one of $[\sigma]\times[\tau]\subseteq C$ or $([\sigma]\times[\tau])\cap C=\emptyset$ holds?

Is it sufficient that $C$ is determined? To put that another way, is there a game which encodes this property? Or is there a (reasonably definable) counterexample?

The first thing that comes to mind is the game where the two players alternate, with I going first, playing pairs of natural numbers $(n_i,m_i)$, and whose outcome is the pair $((n_i)_{i\in\omega},(m_i)_{i\in\omega})\in\omega^\omega\times\omega^\omega$. If $C$ is determined, then either I has a strategy for playing into $C$ or II has a strategy for playing into its complement in this game. Suppose player I has a strategy for playing into $C$. From this, it is easy to construct two strategies $\sigma$ and $\sigma'$ in the Gale-Stewart game for player I with $[\sigma]\subseteq\pi_0(C)$ and $[\sigma']\subseteq\pi_1(C)$, where $\pi_0$ and $\pi_1$ are the first and second coordinate projections, respectively: read off the first (or second) coordinate of I's play in the game with pairs while II plays their move in the Gale-Stewart in the first (or second) coordinate, and an arbitrary number in the other coordinate. However, I have no reason to suspect that $[\sigma]\times[\sigma']\subseteq C$. One issue seems to be a lack of independence in the coordinates played according to a strategy; each of played coordinates can depend on either of the previously played coordinates.

Edit: Joel's answer below precludes the possibility that the strategies are from the same player in the Gale-Stewart game, but I want to also address the possibility that alternate players have such strategies, e.g., I has a strategy $\sigma$ and II has a strategy $\tau$ such that $[\sigma]\times[\tau]\subseteq C$ or $([\sigma]\times[\tau])\cap C=\emptyset$.


1 Answer 1


It is a very nice question.

I claim that it is not sufficient that $C$ is determined, and indeed, there are counterexamples where $C$ is a game with only two moves.

Consider the two-dimensional game where player I plays $(x_0,y_0)$ and player II responds with $(x_1,y_1)$. Player I wins, if $y_1=x_0$. That is, player I wins, if player II copies on his second coordinate the first-coordinate move of player I. In your framework, the payoff set $C$ is the set of plays with projections to $(x,y)$, where $y(1)=x(0)$.

Clearly, player II has a winning strategy in this game, which is simply to make sure that $y_1$ is not the same as the already-played $x_0$.

But I claim that there can be no strategies $\sigma$ and $\tau$ for player I with $[\sigma]\times[\tau]\subset C$ or for player II, with $[\sigma]\times[\tau]\subset\neg C$.

In the first case, for any one-dimensional strategies $\sigma$ and $\tau$ for player I, we can devise a play that refutes them by having player II actually play so as to violate the move-copying requirement.

In the second case, for any one-dimensional strategies $\sigma$ and $\tau$ for player II, we can have player I first play $y_0$, in order to get $\tau$'s response, and then play $x_0$ using that information. In this way, player I can in effect look ahead in the second coordinate to see how player II will play, and then using that information complete the first move in the first coordinate by playing $x_0$ in such a way that player II will in effect have copied it. So this play will be in $C$, contrary to hypothesis.

So there are counterexamples with clopen games of very low complexity.

  • $\begingroup$ Your example precludes two strategies for the same player having this property, but what about for alternate players? For your set $C$, if $\sigma$ is any strategy for player I, then there is a strategy $\tau$ for player II which makes $[\sigma]\times[\tau]\subseteq\neg C$: Just ensure that II's first move using $\tau$ is different than I's first move using $\sigma$. I want to address this case as well, though I should have made that clearer in my original question. $\endgroup$ Nov 9, 2017 at 14:48
  • $\begingroup$ Yes, I had wondered whether you might have wanted to consider also that case. I suspect a variation of my example might work, but I haven't managed to find it yet. $\endgroup$ Nov 9, 2017 at 16:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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