The Chocolatier's game: can the Glutton win with a restricted form of strategy?

Question

I have a question about the Chocolatier's game, which I had introduced in my recent answer to a question of Richard Stanley.

To recap the game quickly, the Chocolatier offers up at each stage a finite assortment of chocolates, and the Glutton chooses one to eat. At each stage of play, the Chocolatier can extend finitely the chocolate assortment on offer, and the Glutton chooses from those currently available. After infinite play, the Glutton wins if every single chocolate that was offered is eventually consumed.

In this post, I am interested in the version of the game where the Chocolatier is not allowed to repeat chocolate types — each new chocolate on offer is a uniquely exquisite new creation.

As I explain at the other the post, the Glutton clearly has a winning strategy, simply by keeping track of when new chocolates are added and making sure to organize the consumption so that every chocolate is eventually eaten. (And this idea works even when the Chocolatier is allowed to extend the offers countably infinitely, and not necessarily just finitely.)

Furthermore, in the case where there are only countably many possible chocolate types, then the Glutton has a winning strategy that depends only on the chocolates currently on offer, not requiring any knowledge of the game history. The strategy is simply to fix an enumeration of all the possible chocolate types and then eat the chocolate available that appears earliest in that enumeration. None could be left at the limit, since it would have been chosen once the earlier ones had been consumed.

Meanwhile, in the case where there are uncountably many chocolate types available, I had proved that the Glutton has no such strategy that depends only on the chocolates currently on offer.

My question is whether we can extend this argument also to allow the strategy to depend on the set of chocolates already eaten.

Question. Does the Glutton have a winning strategy in the Chocolatier's game which depends only on the set of chocolates currently on offer and the set of chocolates already eaten?

I conjecture a negative answer on sufficiently large uncountable sets and perhaps on all uncountable sets.

Here is an alternative equivalent formulation of the game, the catch-up covering game on a set $X$. The first player plays an increasing chain of finite subsets $$A_0\subset A_1\subset A_2\subset\cdots\subset X$$ and the second player chooses elements $a_n\in A_n$. After infinite play, the second player wins if $\bigcup_n A_n=\{a_0,a_1,a_2,\ldots\}$. Of course, the second player can win, by looking at the history of how elements were added to the sets, but the question is whether there is a winning strategy that at move $n$ depends only on the current set $A_n$ and the set of already-chosen elements $\{a_k\mid k<n\}$. The argument on the previous post shows that on an uncountable set $X$ there can be no such winning strategy that depends only on the difference set $A_n\setminus\{a_k\mid k<n\}$, which is the set of elements currently available for choosing anew.

Answer 1

(Not an answer; promoted from a comment on another answer)

If we modify the game so that the glutton can remember (only) the last chocolate they ate, they have a winning strategy as follows:

Well-order $X$. At each step, let $c\in X$ be the last chocolate we ate. If, among the chocolates offered to us, there is any less than $c$, eat the greatest offered chocolate which is less than $c$. If not, eat the greatest chocolate offered overall.

This strategy means that "most" of the time, we eat chocolate in decreasing sequences, only jumping upwards in the order when we have nowhere further to decrease to. This works because each decreasing sequence includes every chocolate that was available at the start of the sequence and each sequence is finite because of well-ordering.

---

This strategy might extend to the original problem - if one could come up with a choice function $f:P_{>0}(X) \rightarrow X$ such that, for every sequence of distinct terms $x_0,x_1,x_2,\ldots$ from $X$ and every $n\in\mathbb N$, there were infinitely many $m\in \mathbb N$ such that $$f(\{x_0,x_1,\ldots,x_m\})=x_n.$$ Using such a function, one could replace "last chocolate we ate" in the strategy with "$f$ applied to the set of chocolates we've eaten" - and we would then find similar decreasing sequences by, whenever we eat a chocolate, looking for when we next choose that chocolate as $c$ in the strategy, and looking for which chocolate we eat at that step (if smaller) and so on. I'm not sure whether finding such a function is easier than solving the original problem, however (or even possible).

Answer 2

Yes. See Theorem 1.2 in K. Ciesielski and R. Laver, A game of D. Gale in which one of the players has limited memory, Period. Math. Hungar. 21 (1990), no. 2, 153–158

Answer 3

Instead of looking at the unordered set of previously eaten chocolates, let's consider a slight modification, where the Glutton knows the finite sequence of previously eaten chocolates. That is, I want the Glutton to remember both what they've eaten and when they ate it. I claim that in this version of the game, the Glutton can win when the set of all possible chocolates has size $\aleph_1$.

Let $\{c_\alpha \colon \alpha < \omega_1\}$ be an enumeration of all possible chocolate types. In the $n^{\mathrm{th}}$ round of the game, if $n$ is odd then the Glutton eats the chocolate with the largest index from our enumeration. (Note that the Glutton can deduce what round of the game it is by knowing the set of chocolates already consumed, so we're not using my extra requirement yet.) If $n$ is even, say at turn $2^{k+1}(2m+1)$, then the Glutton proceeds as follows. First, they look back at their $k^{\mathrm{th}}$ selection, which had some index $\alpha_k$. Then they consult a (pre-determined) enumeration $\{\beta_m \colon m < \omega\}$ of the countably many ordinals below $\alpha_k$. Then they eat the chocolate with index $\beta_m$, if it is currently available. If not, they eat whatever they like.

EDIT: In my modification of the game, the Glutton can always win, no matter how large the set of chocolates is.

Let us prove this by induction on the cardinality of the set of chocolates. Fix a cardinal $\mu$, and suppose the Glutton has a winning strategy whenever the set of chocolates has size ${}<\mu$.

Consider a $\mu$-sized set of chocolates, and enumerate it with order type $\mu$, say $\{c_\alpha \colon \alpha < \mu\}$. In the $n^{\mathrm{th}}$ round of the game, if $n$ is odd then the Glutton eats the chocolate with the largest index from our enumeration. If $n$ is even, say at turn $2^{k+1}(2m+1)$, then the Glutton proceeds as follows. First, they look back at their $k^{\mathrm{th}}$ selection, which had some index $\alpha_k$. Then they consider the game $G_k$ played on the $<\!\mu$-sized set of chocolates $\{c_\xi :\, \xi < \alpha_k\}$. By the induction hypothesis, the Glutton has a winning strategy for this game: suppose they fix some such strategy at move $k$ of the actual game, right after selecting $c_{\alpha_k}$. They then consider their previous moves $2^{k+1}$, $2^{k+1} \cdot 3$, . . . , $2^{k+1}(2m-1)$ of the actual game, and pretend that these are instead the first $m$ moves of $G_k$. They then consult their fixed winning strategy for $G_k$ to determine what their $(m+1)^{\mathrm{st}}$ move should be in $G_k$. While consulting this strategy, they ignore any currently available chocolates with index above $\alpha_k$, since these are not part of the game $G_k$. They then play this as move $2^{k+1}(2m+1)$ of the actual game.

Answer 4

If the chocolate space is $[0,1]$, then Glutton can't win with a positional measurable strategy, where positional means knowing what was eaten when and what is currently on offer; and moreover we restrict Chocolatier to have two chocolates on offer.

If Glutton plays in a measurable way, then there is a chocolate $d_0$ such that $d_0$ gets eaten in the first round when paired with at least $1 - \varepsilon_0$-many other chocolates (and we will only consider those in the following).

We then pick $d_1$ such that if $d_0$ was eaten in the first round, and $d_1$ is offered together with at least a $(1-\varepsilon_1)$-many of the "surviving" chocolates, $d_1$ gets eaten in the second round. We keep going like this, with the $\varepsilon_i$ being sufficiently tiny that in the limit, $1/2$ of the chocolates survive.

Offering a surviving chocolate $c$ together with $d_0$, and then always adding the next $d_i$ will cause $c$ to never be eaten. By design, Glutton can deduce anything else about the history of the game beyond what he ate when, as any permutation of Chocolatiers choices that makes each chocolate available before it was eaten would play out the very same way.