# Uniform strategy on Kastanas' game

I think my question applies to most games, but for the sake of concreteness, I shall consider one specific game in this question. We consider the game posed by Ilias Kastanas in his paper On the Ramsey property for sets of reals: We first fix some $$X \subseteq [\omega]^\omega$$.

1. Player I start by choosing an infinite subset $$A_0 \subseteq \omega$$.
2. Player II responds by choosing $$x_0 \in A_0$$, and then some $$B_0 \subseteq A_0$$ with $$x_0 < \min(B_0)$$.
3. Player I responds by choosing some $$A_1 \subseteq B_0$$.
4. Player II responds by choosing $$x_1 \in A_1$$, and then some $$B_1 \subseteq A_1$$ with $$x_1 < \min(B_1)$$.
5. Etc.

Player I wins iff $$\{x_0,x_1,\dots\} \in X$$.

Assume that Player I has a winning strategy $$\sigma$$. If $$(A_0,x_0,B_0,\dots,A_n,x_n,B_n)$$ is a partial play, then clearly the only things that determine what Player I should respond with are the finite sequence $$(x_0,\dots,x_n)$$ and $$B_n$$, Player II's last played set. However, it appears to me that we cannot assume that $$\sigma$$ satisfies this property. Let's say that $$\sigma$$ is uniform if $$\sigma(A_0,x_0,B_0,\dots,A_n,x_n,B_n)$$ only depends on $$x_0,x_1,\dots,x_n,B_n$$.

If Player I has a winning strategy, does Player I necessarily have a uniform strategy?

I'm also interested in how much the axiom of choice plays a part in the above statement.

• Here is another game where there is a winning strategy, but no uniform strategy: The Chocolatier's game mathoverflow.net/a/401136/1946. Aug 23 at 17:51
• Other variations of the Chocolatier's game, for nearly uniform winning strategies, do depend on the axiom of choice. See mathoverflow.net/q/401151/1946 Aug 23 at 17:54

This is a great question — definitely enjoyed.

Assuming the axiom of choice, then the answer is yes.

Theorem. Assume there is a well ordering of the real numbers. If player I has a winning strategy, then there is a uniform winning strategy.

Proof. Suppose that $$\sigma$$ is a winning strategy for player I. Fix a well ordering of the collection of sets $$B\subseteq\omega$$.

Now, suppose that we are playing the game, faced with the actual position $$(A_0, x_0, B_0, \ldots,A_n,x_n,B_n)$$. But let us look now only at the allowed information for a uniform strategy $$(x_0,\ldots,x_n,B_n)$$. Consider the least with respect to the well ordering subset $$B_n'\subseteq B_n$$, such that there is an imaginary play of $$B_i'$$ that accords with $$\sigma$$ and the data $$(x_0,\ldots,x_n,B_n')$$, such that furthermore each $$B_i'\subseteq A_i'$$ is chosen as least at that stage, subject to being compatible with the data up to $$n$$. Let $$\sigma$$ respond to this imaginary play to give us a set $$A_{n+1}$$, which we now play as the result for this new strategy.

Since the play depended only on $$(x_0,\ldots,x_n,B_n)$$, I have described a uniform strategy. Let me prove that it is winning. What I claim is that every sequence $$x_0,x_1,x_2,\ldots$$ arising from a play according to this uniform strategy can be realized as arising in a play according to $$\sigma$$. The key point is that as $$n$$ increases, the imaginary sets $$B_i'$$ will eventually stabilize for each $$i$$. To see this, consider what happens at stage $$n+1$$, after we've played $$A_{n+1}$$. The actual play will respond with some $$x_{n+1}\in A_{n+1}$$ and $$B_{n+1}\subseteq A_{n+1}$$, and we will forget about the actual $$B_n$$ and find some minimal $$B_{n+1}''\subset B_{n+1}$$ and new imaginary sets $$B_i''$$ that produce a play according with $$\sigma$$ and the data $$(x_0,\ldots,x_{n+1},B_{n+1}'')$$, and is minimal at each stage $$i$$. But the point now is that the requirement on $$B_i''$$ is a bit lighter than that on the imaginary set $$B_i'$$ chosen at stage $$n$$, provided that $$x_{n+1}$$ is in $$B_n$$, which it is. Earlier, we needed $$B_i'$$ to contain $$B_n'$$, but now we only need it to contain $$B_{n+1}''$$, which is strictly smaller. So the set $$B_i''$$ will be either equal to $$B_i'$$ or preceed it in the well order. But it can only go down in the well order finitely often, and so eventually, for any given $$i$$, the imaginary versions of $$B_i'''$$ will stabilize. In other words, if we have an infinite play according to the uniform strategy, we can find choices of $$B_i'''$$ that give rise to the whole play. And since this imaginary play accords with $$\sigma$$, the set $$\{x_0,x_1,\ldots\}$$ will be in $$X$$, as desired. $$\Box$$

• Thanks Joel, very nice! Do you have any clue on how necessary choice is? Aug 24 at 3:03
• This argument clearly uses choice in a fundamental way. I don't have a good idea for what happens when choice fails. Aug 24 at 18:29