4
$\begingroup$

Two players (player C and player G) are playing a (modified) word guessing game. Both players share the same vocabulary $V$ and words in $V$ are grouped into $K$ bins, denoted as $b_1$, $b_2$, ..., $b_{K}$. Furthermore, we know that $b_{i} \subset V$ and $\cup_{i=1}^{K} b_i = V$. Note here we do not have $b_i \cap b_j = \emptyset$ for $i \neq j$.

The game protocol is described as follows:

  1. Player C uniformly chooses a word $w$ from the vocabulary $V$. Player G does not know which word $w$ is.

  2. Player G chooses one bin and asks Player C whether his/her chosen word $w$ is in the bin. If it is, the game ends. Otherwise, Player G will choose another bin.

Questions: What is the best bin choosing order and what is the expected number of times of choosing the bin, according to the best possible order?

Example:

Suppose we have a vocabulary consisting of ten words $V = \{w_1, w_2, ..., w_{10} \}$ and three bins $b_1 = \{w_1, w_2, ..., w_5\}$, $b_2 = \{w_6, w_7 \}$, and $b_3 = \{w_8, w_9, w_{10} \}$.

One possible bin choosing order is $b_1 \rightarrow b_3 \rightarrow b_2$ and the expected number of times of choosing the bin is $\frac{1}{2}*1 + \frac{1}{2}*\frac{3}{5}*2 + \frac{1}{2}*\frac{2}{5}*\frac{2}{2}*3 = 1.7$. I suspect this is the best bin choosing order but how can we prove this result?

Thanks.

Note

A related question (which has additional non-overlapping constraints on the bins) is asked in MO and in its comment, the user @DavidG.Stork gives a good answer (an intuitive proof of best ordering) for the case when those bins have no overlap.

$\endgroup$
  • 2
    $\begingroup$ No problem. Your use of the term "game" just had me thinking about strategies for each player, when in fact only one "player" can be said to have a strategy here. And the best strategy is not actually obvious. If the bins were $b_1 = \{1,2,3,4,5,6 \}$, $b_2 = \{1,2,3,7,8 \}$ and $b_3 = \{4,5,6,9,10 \}$, the "obvious" choice of selecting bin $b_1$ first would not be correct. $\endgroup$ – Jens Mar 25 '19 at 1:09
  • 2
    $\begingroup$ Simulposted to MO, mathoverflow.net/questions/326236/… with no notice to either site. $\endgroup$ – Gerry Myerson Mar 25 '19 at 3:49
  • 1
    $\begingroup$ @Jens, when you're hungry, do you order pizza from several different pizzerias at a time, or just from one? $\endgroup$ – Gerry Myerson Mar 25 '19 at 4:15
  • 1
    $\begingroup$ @Gerry Myerson: I ask everyone I know or can think of if they can satisfy my hunger. I could now say "you didn't answer my question", but it would distract from the question at hand. Do you have a relevant input to it? $\endgroup$ – Jens Mar 25 '19 at 4:19
  • 1
    $\begingroup$ @Jens, what do you do when three delivery boys show up at your door with pizzas for you? Do you tell two of them, sorry that I've wasted your time, but I already got the pizza from the first guy? $\endgroup$ – Gerry Myerson Mar 25 '19 at 4:23
0
$\begingroup$

Not an answer but too long for a comment.

For a given ordering of bins, lets say $a_{1}, a_{2}, ..., a_{K}$ (which is a permutation of the $b_i$'s), let $f(w)$ be the discovery time for word $w$. Then $f(w) = j$, i.e. it will be discovered during the $j$th bin, iff $w \in c_j$ where $c_j = a_{j} - \bigcup^{j-1}_{i=1} a_i$. I.e. $c_j$ are the new words introduced by bin $a_j$.

To calculate the expected number of turns, sum up all the discovery times $f(w)$ and then divide by the number of words. So the expected number is minimized when $\sum_{w \in V} f(w)$ is minimized.

In the OP's original example all $b_i$'s are disjoint, so it's pretty clear that $\sum_{w \in V} f(w)$ is minimized when you assign the most number of them as $1$s, then the next-most number of them as $2$s, etc. In this example the expected number of turns $= {5\times 1 + 3 \times 2 + 2 \times 3 \over 10} = 1.7$.

When the $b_i$'s are not disjoint, then as shown by the excellent example of @Jens in the comments, the greedy strategy can be suboptimal - it assigns the numbers $1,1,1,1,1,1,2,2,3,3$ for a total of $16$ when the optimal strategy assigns the numbers $1,1,1,1,1,2,2,2,2,2$ for a total of $15$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks for the complement! One might think the way forward was to find the smallest subset of bins which together contain all the words, but consider the following example: $b_1 = \{1,2,3,4,5,6,7 \}$, $b_2 = \{1,2,3, 8\}$, $b_3 = \{4,5,9 \}$, $b_4 = \{6,7,10 \}$. In this case, selecting $b_1$ first is actually the right strategy. $\endgroup$ – Jens Mar 25 '19 at 3:46
  • $\begingroup$ @Jens I had the exact same conjecture as yours and then also came up with a counterexample: $\{1,2,3,4,5\}, \{6,7,8,9,10\},\{1,2,3,4,6,7,8,9\}$ where $8 \times 1 + 2 + 3 = 13 < 15$. I'm quite curious what the answer is. Now that the first two obvious strategies don't work, I wonder if it might actually be NP complete. $\endgroup$ – antkam Mar 25 '19 at 3:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.