Explicit examples of undetermined games

Question

Suppose we have a game between two players in which they take alternating turns. The game can have finite length, length $\omega$ or any transfinite number of steps (however, I'm not concerning games which are continuous). Every game has a winning condition, which can be interpreted as the set of all game histories possible which result in a win for player 1, and other such set which specifies winning for player 2. Here we are only interested in games which always end (possibly after transfinite time) and which have no ties (if player 1 doesn't win, then player 2 wins).

We define a strategy for player 1 as a function from the possible partial (i.e. up to some move of 1) history of the game to an allowed move which 1 can make. We say that strategy for player 1 is winning if it guarantees him a win in the game provided that he follows the strategy. Same for strategy and winning strategy for player 2. The game is determined if one of the players has a winning strategy. Otherwise, the game is undetermined.

It's a well-known result that, if we assume axiom of choice, then there is an undetermined game of length $\omega$ with allowed moves being elements of $\Bbb N$. This is necessarilly a non-constructive proof. It's also known that there is an undetermined game in which players play for time $\omega_1$ with moves being bits, or they play countable ordinals for time $\omega$, or they play elements of $\mathcal{P}(\Bbb R)$ for time $\omega$, without assuming AC. However, only proofs of these facts which I know of are by contradiction.

A game which is somewhat closer to being constructive example is the following game which uses non-principal ultrafilter on $\Bbb N$: players alternatingly form increasing sequence of numbers $a_1,a_2,...\in\Bbb N$. Then we partition $\Bbb N$ into two sets, $[0,a_1)\cup[a_2,a_3)\cup...$ which belongs to player 1, and $[a_1,a_2)\cup[a_3,a_4)\cup...$ which belongs to player 2. The winner is the player whose set is in the non-principal ultrafilter. Simple strategy-stealing shows that neither player has a winning strategy.

All other examples of games which are undetermined are heavily non-constructive, which made me ask the following question:

Are there any explicit examples of games which are not determined?

With "explicit" I mean that we can provide the example without assuming existence of any sets beyond these which ZF can prove are existing.

Answer 1

Here is an amusing concrete non-determined game, under the assumption that the dependent choice principle fails.

Assume DC fails. This means that there is a set $X$ and a binary relation $R$ on $X$, such for every $x\in X$ there is $y$ with $x\mathrel{R} y$, but there is no sequence $\langle x_n\mid n\in\omega\rangle$ with $x_n\mathrel{R} x_{n+1}$ for all $n$. In other words, the tree of finite sequences that accord with $R$ has no leaves — every node can be extended one more step — but there is no way to iterate these steps and the tree has no infinite branch.

Consider the game on $X$ where player I plays a point $a$ from $X$ and player II responds with $b$, and player II wins just in case $a\mathrel{R} b$; otherwise player I wins. So the game is over very quickly, after just one move for each player. (If you insist that games should have infinitely many plays, then you can continue with infinitely many irrelevant moves.)

Player I obviously cannot have a winning strategy, since whatever point $a$ is played, there is a way for II to defeat it by playing some $b$ with $a\mathrel{R} b$.

But player II also cannot have a winning strategy, since any such strategy would provide a choice function on the $R$-successors of the points in $X$, and any such function could be iterated to thread $R$, whereas there is no such infinite thread.

Since the game is an open game (in fact clopen), this argument shows that one cannot prove open determinacy without DC. The usual proof of open determinacy uses DC, when showing that if a position does not have an ordinal rank, then the closed player can avoid losing by maintaining rank. But in order to do so, that player needs DC to find the infinite thread of rank-maintaining moves.

Update. As noted in wojowu's comment below, this example can be adapted to prove the following theorem.

Theorem. ZF proves that there is a non-determined set. Specifically, in ZF we can prove that $\text{AD}_{P(\mathbb{R})}$ fails.

Proof. First, let $F$ be any family of non-empty sets, and consider the game where player I selects some $A\in F$ and player II selects some $a\in A$, and the first player to violate either requirement loses. Clearly, there can be no winning strategy for player I, since if such a strategy directed player I to play a particular $A$ in $F$, then it would be defeated by the strategy for player II to always play some particular element $a\in A$. Conversely, observe that if player II has a winning strategy for the game, then we would have a choice function for $F$. So any violation of AC leads immediately to a non-determined game. In particular, if choice fails for families of nonempty sets of reals, then we get a violation of $\text{AD}_{P(\mathbb{R})}$. On the other hand, if choice holds for such families, then the reals are well-orderable, and we may construct a non-determined set for binary play. So in either case, $\text{AD}_{P(\mathbb{R})}$ fails. QED

Regarding the remarks below about constructing an "explicit" game, one can easily do this as follows.

Corollary. In ZF we can write down an explicit definition of a non-determined set.

Proof. Consider the game where player I chooses either (1) a well-ordering of the reals, and then the rest of the payoff set is as would be constructed for a non-determined set by the usual argument given such a well-ordering; or (2) a family $F$ of nonempty sets of reals having no choice function, with player II then picking an element of the family and player I playing an element of that set, as in the theorem (but with the players reversed). This gives altogether one big payoff set, explicitly defined.

Note that player I cannot have a winning strategy, since he cannot have a strategy for the resulting play in case (1), as the game is undetermined, and he cannot have a strategy that wins by placing him in case (2), since any such strategy would have to provide a choice function for $F$.

Conversely, player II cannot have a winning strategy, since player I can play either a family with no choice function, in which case it is hopeless for II to play with particular element of the family, or else AC holds for all such families in which case player I can play a well-ordering and a non-determined game, for which player II can have no responding strategy. QED

Answer 2

Here's another example of an explicit undetermined game on $\mathcal{P}(\omega^\omega)$ (presented in more detail at MSE):

From the incompatibility of $\mathsf{AD}$ and "$\mathbb{R}$ can be well-ordered" we get the outright falsity of the uniform determinacy principle "There is a functional $\mathcal{F}$ assigning to each game on $\omega$ a winning strategy in that game." Given this, the following game $\mathfrak{U}$ must be undetermined:

Player 1 plays a set $A\subseteq \omega^\omega$. Player $2$ then picks either "First" or "Second." For the remaining moves, players $1$ and $2$ play the usual game associated to $A$, with P2 taking on the role of first player iff they said "First."

The existence of a winning strategy for P2 would imply uniform determinacy. Meanwhile, P1 clearly can't have a winning strategy that involves playing a determined $A$, and if P1 plays an undetermined $A$ then P2 can win by replying "Second" and just playing barely well enough. So $\mathfrak{U}$ itself is undetermined as claimed.

Of course, given what goes into the disproof of uniform determinacy, this is not substantively different from Joel's example above. That said, I think it's still neat.