Mathematicians wearing hats on arbitrary total orders

Question

I've been pondering the following generalisation of a famous problem (the special case where $T = \mathbb{N})$:

Question: We have some totally-ordered set $T$ of mathematicians, each wearing a hat which is either red or blue. The mathematician $x$ can see the colour of $y$'s hat if and only if $x < y$. The mathematicians each simultaneously guess the colour of his or her own hat. Under what conditions on $T$ can the mathematicians pre-arrange a strategy such that, independently of the colouring, only finitely many guess incorrectly?

---

I've made the following progress, which suggests the problem is quite tractable:

Clearly $T$ must be well-ordered, since otherwise we would have an infinite decreasing sequence $a_1 > a_2 > a_3 > \cdots$ of mathematicians. Then we choose all other hat colours arbitrarily (for concreteness, all blue) and sequentially set the hat colour of $a_i$ to make the mathematician guess incorrectly.

So we're only interested in the case where $T$ is an ordinal. Clearly if $T' > T$, then a winning strategy for $T'$ implies a winning strategy for $T$. So the problem reduces to:

What is the minimal ordinal $\alpha$ such that the mathematicians do not have a winning strategy?

It is trivial that $\alpha \geq \omega$, since for finite ordinals, it is impossible for the mathematicians to lose. It's not too difficult (indeed, it is a famous exercise) to show in ZFC that the mathematicians have a winning strategy for $\omega$. This implies $\alpha \geq \omega^2$ since the sum of two 'winning ordinals' is necessarily another winning ordinal (so $\alpha$ is a power of $\omega$).

So far I have no upper bound on $\alpha$ (indeed, it could be the case that the mathematicians have a winning strategy for any ordinal, in which case $\alpha$ is undefined), and I have no lower bound beyond $\omega^2$. Thus an easier (and much more concrete, since you only have two possible answers instead of a proper class) question is:

Do the mathematicians have a winning strategy for $\omega^2$?

Answer 1

It's a great problem!

Theorem. The mathematicians have a winning strategy in the game for every ordinal $\alpha$.

Proof. Let's prove the theorem by transfinite induction. Suppose that the mathematicians have winning strategies in the games of any particular length $\beta$ less than $\alpha$, and let us fix agreed-upon strategies for those games. Consider now the case of $\alpha$ many mathematicians. I shall describe a winning strategy. In the space of all possible assignments of hat colors to the $\alpha$ many mathematicians, define that two such assignments are equivalent $s\sim t$, if they agree from some ordinal onward; that is, they agree on a tail segment $[\beta,\alpha)$ of $\alpha$. Let the mathematicians agree on a choice of representative for each $\sim$-equivalence class. Now, suppose that the hats are given out. Each mathematician (except the last one, in the case that $\alpha$ is a successor ordinal) is able to observe a tail segment of the actual assignment given, and thus knows the $\sim$-class of the actual assignment. Let the mathematician at any particular position $\gamma$ compare the observed assignment beyond $\gamma$ with the assignment of the pre-chosen representative from that class. If they agree perfectly beyond $\gamma$, then let mathematician $\gamma$ announce the color of the hat that he or she would wear according to the chosen representative assignment. Otherwise, mathematician $\gamma$ observes some errors at positions beyond $\gamma$. Let $\beta$ be the supremum of the positions of these errors, so that $\gamma<\beta$ but also $\beta<\alpha$ since the observed assignment definitely agrees with the representative from some point on. In this case, let mathematician $\gamma$ ignore the part of the assignment beyond $\beta$, and instead use the fixed strategy for the game of assignments of length $\beta$, using only the information about the hats up to $\beta$.

Notice that if $\beta$ is the supremum of the places where the actual assignment differs from the representative, then everyone beyond $\beta$ will guess correctly, and everyone before $\beta$ will compute $\beta$ correctly and therefore use the agreed-upon strategy for the length $\beta$ game. So by the induction hypothesis, only finitely many will be wrong. QED

Let me also describe another strategy, in the style of Alan Taylor, from what I recall from a talk he gave at our seminar in New York several years ago. See also Christopher S. Hardin and Alan D. Taylor, A Peculiar Connection Between the Axiom of Choice and Predicting the Future, which was mentioned in the comments.

We prove directly that there is a strategy for $\alpha$ many mathematicians. First of all, let the mathematicians agree upon a fixed well-ordering $\triangleleft$ of the space of all hat $\alpha$-assignments. Now, suppose the hats are given out. Let each mathematician observe the portion of the hat assignment given to the mathematicians ahead, and let each mathematician compute the $\triangleleft$-least total assignment that agrees with the portion of the actual assignment that they observe. Each mathematician should predict that their own hat color is the same as it in in the $\triangleleft$-least assignment that they compute.

We now argue that only finitely many mathematicians are wrong. The main point is that if $\gamma<\beta$, then the $\triangleleft$-least assignment that mathematician $\gamma$ computes is at least as high in the $\triangleleft$ order as the $\triangleleft$-least assignment that mathematician $\beta$ computes, since mathematician $\gamma$ observes all the information that $\beta$ observes and more about the actual assignment of hats. That is, as you move up higher in the mathematicians, the computed $\triangleleft$-least approximation can only move down in the $\triangleleft$ order if it changes. Every time there is an incorrect guess as we move up in the mathematicians, we drop strictly lower in the $\triangleleft$-well-ordering. And since $\triangleleft$ is a well-order, this can happen only finitely many times. Thus, only finitely many mathematicians guess incorrectly.

The argument is extremely general, and leads to the conclusion that in any partial order, where the mathematicians are looking upward, then the collection of incorrect guesses forms a converse well-founded subset. And one can even generalize further than this, as Hardin and Taylor do.