Examples of concrete games to apply Borel determinacy to

Question

I'm teaching a course on various mathematical aspects of games, and I'd like to find some examples to illustrate Borel determinacy. Open or closed determinacy is easy to motivate because it proves the determinacy of a game like chess, idealized to make infinitely long games a draw. But I have a hard time trying to come up with examples of not-too-theoretical games to which I could apply Borel determinacy.

Specifically, I'm looking for examples of:

1. games that can be cast as Gale-Stewart games,

2. which don't look too much like an abstract theoretical construct but like an actual concrete game that people might play, at least granting them an infinite amount of time (but each step of the game should be more or less finitistic in nature),

3. whose determinacy follows from the Borel determinacy theorem,

4. but not from the open or closed determinacy theorem alone,

5. and whose winning strategy is not obvious by other means.

If we drop condition (4), then the idealized game of chess is a good example. If we drop condition (5), an example might be the game where Alice and Bob play binary digits and Alice wins if the proportion of 1's has a limit (this stretches condition (2) a bit but I'm willing to allow it… my problem is mostly that Alice's winning strategy is really too obvious).

Can anyone offer interesting examples with all these conditions?

Answer 1

The game of infinite Hex, proceeding from an arbitrary position, is a good example with all the features you seek. The game was the subject of my Oxford student Davide Leonessi's masters MFoCS dissertation work, and we give an introduction in our article:

• Joel David Hamkins, Davide Leonessi, Infinite Hex is a draw, Integers 23, (2023), #G6.

Our main result in the paper is that, when proceeding from an empty board, infinite Hex is a draw. But the game can be naturally considered from arbitrary starting positions, and in this case it is not known who wins even if Red is given a single extra stone at the start. There are many open questions about it.

The complexity of the winning condition was not completely known, and it was still an open question in our article whether this game was arithmetic, Borel, or analytic. The only bound known initially was that the game was analytic, which would bring the determinacy question outside of Borel determinacy and what is known in ZFC alone. I had asked the question on MathOverflow, What is the complexity of the winning condition in infinite Hex?.

The question was answered there by Ilkka Törmä, who showed that in fact the game has arithmetic complexity, thus bringing it within the fold of Borel determinacy. He gave a talk on the subject at the Infinite Games seminar.

But to summarize, the game has all your requested features:

• Infinite Hex can be cast as a Gale-Stewart game.
• It is a natural generalization of the familiar finite game.
• The determinacy of infinite Hex proceeding from an arbitrary position follows from Borel (and even arithmetic) determinacy, but this is a nontrivial result, to show that it is indeed a Borel game.
• It is not an open or closed game, except in trivial circumstances.
• In the general case, from many natural starting positions, the winning strategy and even the winner is not known.

Answer 2

Here are four, of various different flavors:

---

A silly one

I described in a different MO question a game where players work together to turn the harmonic series into an alternating (so conditionally convergent) series, with one player trying to make the sum of the resulting series land in a given set $X$. If $X$ is Borel, then Borel determinacy applies, but I don't see any easier argument.

Of course, this has the slight drawback of being completely artificial!

---

A graph-building game

For a property $\mathcal{P}$ of (directed) graphs, let $G_\mathcal{P}$ be the game where players 1 and 2 work together to build a graph with vertex set $\mathbb{N}$, where at move $s=\langle i,j\rangle$ the appropriate player (corresponding to the parity of $s$) decides whether or not there is an edge from $i$ to $j$. "Simple" graph properties yield obviously-determined games, but rather quickly determinacy becomes hard to establish.

Borel determinacy implies that $G_\mathcal{P}$ is determined even for very rich $\mathcal{P}$ - namely, any $\mathcal{P}$ which is expressible as an $\mathcal{L}_{\omega_1,\omega}$-sentence in the language of graph theory. And this is robust to changes of the structure of the game - e.g. allowing players to play finitely many "edge facts" at once, etc. - or to different sorts of structure.

---

"Road runner vs. coyote"

This is an elaboration on the previous example. Let $\mathbb{K}$ be a class of structures, and consider the following game: players 1 and 2 each build a structure in a "step-by-step" way, with player 2 winning iff their structure $\mathcal{B}$ is isomorphic to player 1's structure $\mathcal{A}$.

... assuming that $\mathcal{A}\in\mathbb{K}$ - if $\mathcal{A}\not\in\mathbb{K}$, then player 2 wins iff $\mathcal{B}\in\mathbb{K}$. Basically, $\mathbb{K}$'s complement is a sort of "cliff" which player 1 can safely run off but player 2 can't. This aspect is what prevents 2 from having the obvious "just copy what 1 does" strategy, and motivates the name above.

OK fine, Montalban didn't call them that and instead used the more serious-sounding term "copy-diagonalize game." Missed opportunity, that. Anyways, the point is that if $\mathbb{K}$ is Borel then Borel determinacy applies, but a winning strategy may be quite hard to find.

---

An instructive counterexample

For an instructive non-example, consider the perfect set game on a Borel $X\subseteq\mathbb{R}$. Prima facie its determinacy follows from Borel determinacy but not closed determinacy. Of course this quickly disintegrates since we can "unfold" such a game to get a closed game ... but this is instructive since that's exactly what we do to prove Borel determinacy itself, albeit at a much higher level of complexity.

Answer 3

May look at some of Andrew Marks papers, in particular ``A determinacy approach to Borel combinatorics''.