Consider the following version of Zermelo's Theorem:
Theorem: Let $G$ be a finite-rank two-player game in extensive form with perfect information and without simultaneous moves. Let $\tau$ be a set of terminal histories. Then either player 1 has a strategy guaranteeing that an outcome in $\tau$ will occur or player 2 has a strategy guaranteeing that an outcome in $\tau^C$ will occur.
- The rank of a game is the length of its longest history.
- A terminal history is a history for which there exists no longer history succeeding it.
- $\tau^C$ is the set of terminal histories not contained in $\tau$.
The proof is by induction over the rank of the game, $r$. W.L.O.G. suppose that player 1 makes the first move. The induction step makes use of the fact that after player 1's first move all remaining subgames have rank strictly smaller than $r$ and that player 1 is free to choose which subgame to go to.
Question: I am looking for a counterexample to the theorem if the finite-rank condition is dropped.
I have thought about this for some time but have failed to come up with one so far.
You can construct a counterexample by transfinite induction. Let us say the game is that the two players take turns saying either $0$ or $1$ forever, so the set of terminal histories is $\{0,1\}^{\mathbb{N}}$. We will build a subset $\tau\subset\{0,1\}^{\mathbb{N}}$ such that player 1 has no strategy to guarantee an outcome in $\tau$ and player 2 has no strategy to guarantee an outcome in $\tau^C$.
First, note that there are $\mathfrak{c}$ different strategies for each player; fix an enumeration $(f_\alpha)_{\alpha<\mathfrak{c}}$ of all strategies for player 1 and an enumeration $(g_\alpha)_{\alpha<\mathfrak{c}}$ of all strategies for player 2. By induction on $\alpha<\mathfrak{c}$, we construct two sequences $(t_\alpha)_{\alpha<\mathfrak{c}}$ and $(u_\alpha)_{\alpha<\mathfrak{c}}$ of elements of $\{0,1\}^\mathbb{N}$, such that the sets $\{t_\alpha\}_{\alpha<\mathfrak{c}}$ and $\{u_\alpha\}_{\alpha<\mathfrak{c}}$ are disjoint. You can think of the $t_\alpha$ as the histories we have decided will be in $\tau$ so far, and the $u_\alpha$ as the histories we have decided must not be in $\tau$ so far.
Having defined $t_\beta$ and $u_\beta$ for all $\beta<\alpha$, we define $t_\alpha$ and $u_\alpha$ as follows. Let $A\subset\{0,1\}^{\mathbb{N}}$ be the set of all possible outcomes that can be obtained if player 1 follows strategy $f_\alpha$. Note that $A$ has cardinality $\mathfrak{c}$, since any sequence of player 2's moves is possible for elements of $A$. In particular, there exists some element of $A$ which is not equal to $t_\beta$ for any $\beta<\alpha$. Pick some such element and define it to be $u_\alpha$. Similarly, let $B$ be the set of all outcomes that can be obtained if player 2 follows strategy $g_\alpha$, and pick some element of $B$ which is not equal to any $u_\beta$ for any $\beta\leq\alpha$ and define it to be $t_\alpha$.
Now define $\tau=\{t_\alpha\}_{\alpha<\mathfrak{c}}$. Then player 1 has no strategy guaranteeing an outcome in $\tau$, since for any strategy $f_\alpha$ of player 1, $u_\alpha$ is one of the possible outcomes of this strategy, and $u_\alpha\not\in\tau$ (since we constructed the $u$'s and $t$'s to be disjoint sets). Similarly, player 2 has no strategy guaranteeing an outcome in $\tau^C$, since for any strategy $g_\alpha$, $t_\alpha$ is a possible outcome of the strategy and $t_\alpha\in\tau$.