14
$\begingroup$

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?

$\endgroup$
1
  • $\begingroup$ Have you heard of Schmidt's game? $\endgroup$
    – 喻 良
    Apr 16 at 0:43

3 Answers 3

19
$\begingroup$

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:

enter image description here

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.
$\endgroup$
2
  • 1
    $\begingroup$ OK, that meets my stated conditions, but concerning (3) I was hoping for a game whose borelness would be much easier to see — if I understand what you say, it's not at all obvious, so it's hard to give this as an illustrative example of Borel determinacy. $\endgroup$
    – Gro-Tsen
    Apr 15 at 14:17
  • 2
    $\begingroup$ Yes, it was an open question whether it is Borel, and the answer is nontrivial. And yet, the only reason we know in ZFC that infinite Hex is determined in the general case is because of Borel determinacy, so it seems relevant. $\endgroup$ Apr 15 at 14:33
12
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ Your first example isn't necessarily just about graphs, but really the truth of any $\mathcal{L}_{\omega_1,\omega}$ sentence in a countable model of any signature type. I imagine the players collectively defining the atomic structure of the model, with Alice trying to make the sentence true and Bob trying to make it false. This way of thinking includes the case of any first-order theory in a countable language, since the conjunction is a sentence of $\mathcal{L}_{\omega_1,\omega}$. For example, I think Bob wins the attempt to make a model of ZFC, by ruining any set as empty. $\endgroup$ Apr 16 at 1:11
  • $\begingroup$ @JoelDavidHamkins True, I was focusing on graphs to keep it easy to describe. $\endgroup$ Apr 16 at 1:21
  • $\begingroup$ I find it natural also to consider the game where the players determine which (finite) part of the atomic diagram that are revealing at each turn, rather than having this determined by parity as in your description. This makes it something like the EF games, and also similar to the truth-telling game, where the interrogator asks questions about what is true and the truth teller answers, winning if the Tarski conditions are never violated. $\endgroup$ Apr 16 at 1:36
  • $\begingroup$ @JoelDavidHamkins Yes, that's the sort of variation I had in mind with "this is robust to changes of the structure of the game." Really all of the games appearing here are extremely flexible in this way since that sort of tweaking won't affect Borel-ness of the payoff set. $\endgroup$ Apr 16 at 1:38
3
$\begingroup$

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

$\endgroup$

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.