25
$\begingroup$

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.

$\endgroup$
7
  • $\begingroup$ Here is a non-deterministic winning strategy for the Glutton, when the set of chocolates has size $\aleph_1$. Just like in my answer, let $\{c_\alpha :\, \alpha < \omega_1\}$ enumerate the chocolate types. On even-numbered turns, the Glutton plays the chocolate with the largest index. On odd-numbered turns, the Glutton first selects an index $\alpha$ of an already-played chocolate, completely randomly. Then he looks at an enumeration $\{\beta_m :\, m < \omega\}$ of the ordinals below $\alpha$, and plays the chocolate with index $\beta_m$ with probability $1/2^m$, if it is available to play.... $\endgroup$
    – Will Brian
    Aug 7, 2021 at 1:05
  • 5
    $\begingroup$ It reminds me of something that my colleague Marion Scheepers has (and others have) written about, e.g., mathscinet.ams.org/mathscinet-getitem?mr=1617957. $\endgroup$ Aug 7, 2021 at 5:47
  • 4
    $\begingroup$ @ZachTeitler It is exactly the same game! Thanks very much. Evidently, everything in the world is already known. $\endgroup$ Aug 7, 2021 at 6:03
  • 8
    $\begingroup$ In each round, player I invents a set of games, and player II writes a paper about one game, but it turns out that player III already wrote papers about all the games. :-) $\endgroup$ Aug 7, 2021 at 6:15
  • 10
    $\begingroup$ No matter how many chocolates he is offered, he takes only one. And yet you call him a glutton. Seems a bit harsh to me. Judge not lest ye be judged. $\endgroup$
    – bof
    Aug 7, 2021 at 7:42

4 Answers 4

13
$\begingroup$

(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).

$\endgroup$
15
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ Thank you! And theorem 1.1 of this paper is argument of Milo Brandt. $\endgroup$ Aug 7, 2021 at 18:15
  • 4
    $\begingroup$ Perhaps this is precisely the game Richard was thinking of (with Gale instead of Specker)? $\endgroup$ Aug 7, 2021 at 21:25
11
$\begingroup$

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.

$\endgroup$
12
  • 2
    $\begingroup$ But I do still wonder if you can get rid of the need to know the order of the previously eaten chocolates. It is only the set and not the order that restricts future play of the Chocolatier. So the order is closer to the history, which we know enables the Glutton to win. Also, in the case that the assortment on offer is always a pair, then the order of eating completely determines the history. $\endgroup$ Aug 6, 2021 at 18:12
  • 2
    $\begingroup$ @JoelDavidHamkins: No, I'm saying the Glutton has a winning strategy regardless of how big the set of all possible chocolates is. $\endgroup$
    – Will Brian
    Aug 6, 2021 at 18:45
  • 2
    $\begingroup$ That is great, thanks for posting this. Very nice! Huge progess, even though it doesn't yet answer the question I asked. $\endgroup$ Aug 6, 2021 at 18:46
  • 6
    $\begingroup$ There's a simpler strategy that works based only on the last thing you ate: Well-order $X$. At each step, if there is any chocolate offered smaller than the last one you ate, eat the greatest such chocolate offered. Otherwise, eat the greatest chocolate offered. Doing this, you end up eating a bunch of decreasing sequences of chocolates - each decreasing sequence containing every chocolate that was available when the sequence started (and each decreasing sequence being finite because of the well-order). $\endgroup$ Aug 7, 2021 at 4:49
  • 3
    $\begingroup$ @MiloBrandt That is great! Please post it as an answer. $\endgroup$ Aug 7, 2021 at 6:06
10
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ When you say "what was eaten when" then do you mean that we know the history of eating? In this case, with pairs, we know the entire history (with one parameter), and so the Glutton has a strategy by the prior analysis in my post. $\endgroup$ Aug 6, 2021 at 18:28
  • $\begingroup$ @JoelDavidHamkins In Round 2, Glutton knows that he ate $d_0$ in the first round, and currently has $d_1$ and $c$ on offer. He doesn't know which of $c$ and $d_1$ is left-over from the previous round, and which is new in this round (because he'd have eaten $d_0$ either way. Then in Round 3, he gets to choose between $c$ and $d_2$, but again has no clue how old these are. $\endgroup$
    – Arno
    Aug 6, 2021 at 18:31
  • $\begingroup$ @JoelDavidHamkins But in Round $k$, Glutton knows that he ate $d_0$, $d_1$, ..., $d_k$ in this order. $\endgroup$
    – Arno
    Aug 6, 2021 at 18:32
  • $\begingroup$ Yes, thank you, and +1. By the parameter, I had meant the other part of the initial offer. But you are right, the order doesn't completely determine the history without that. $\endgroup$ Aug 6, 2021 at 18:36

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.