Three player combinatorial game - minimizing communication between Alice and Bob

Question

Consider the following game between three parties: Alice, Bob and a Referee. The game starts with $n$ closed boxes. For some fixed $k<n$ known to all parties, the Referee freely chooses $k$ distinct boxes and places a prize inside each of them. Alice sees the Referee do this and thus, she knows which boxes have a prize. Bob now enters the room. He can talk to Alice, then choose one box and if this box has a prize, he can keep it.

What is the smallest number of bits of information that Alice needs to convey to Bob such that Bob is guaranteed to win a prize?

The naive strategy is for Alice to pick a prize-containing box at random and give the ID of this box to Bob. This costs $\log n$ bits of information since she picks one box out of $n$ choices. But given that there are $k$ choices and any of them would do the job, can Alice and Bob win the game with less than $\log n$ bits of communication? If yes, what should their strategy be?

EDIT: I am happy to assume the Referee is not adversarial if that admits a better strategy for Alice and Bob.

Answer 1

An obvious strategy is: Alice picks the lowest box id and sends it. There are $n-k+1$ possible values, hence the information content is at most $\log(n-k+1)$

Actually, if we assume that the $k$ boxes are chosen at random, the distribution of the picked one will not be uniform, hence the information content will be less than that.

The pmf of the smallest member of a $(n,k)$ selection, indexed from $j=0\cdots n-k$ is

$$P(j)= \frac{1}{\binom{n}{k}}\binom{n-j}{k}\frac{k}{n-j}$$

I'm not sure if the entropy of this distribution can be put in a simple form.

Edited: for large $n$ the entropy (in nats) of the above gives me the following not-too-illuminating expression:

$$H\approx \frac{k}{n} \frac{e^{-k/n}}{1-e^{-k/n}} - \log(1- e^{-k/n})$$

For large $n$ and $k$, with $k/n \to 0$, this behaves as $\log(n)-\log(k)+ O(1)$

Answer 2

Here is a "negative" result under these assumptions:

1. The game is deterministic, i.e. all 3 have no access to any randomizer (dice etc).

2. The referee is adversarial and knows Alice & Bob's strategy.

3. There is only 1 round of interaction between Alice & Bob. So Bob doesn't even need to ask his question (since it's deterministic anyway) and can simply walk into the room and hears Alice's single answer, which is $b$-bits long.

Under these assumptions, the result is IMHO negative: $b$ must satisfy $k + 2^b > n$, or equivalently, $b \ge \log_2(n-k+1)$.

Reason: each of the $2^b$ possible answers deterministically maps to one box. So if $k + 2^b \le n$ the adversary can place all prizes in boxes which correspond to none of the possible answers.

I consider this a "negative" result because this shows the "obvious" strategy to be optimal. (The obvious strategy being: eliminate $k-1$ boxes before hand and then just encode the remaining $n-k+1$, since at least one of these must contain a prize. This is equivalent to the lowest-ID strategy of @leonbloy, which eliminates the highest $k-1$ boxes.)

---

In fact, I think assumption #3 is not needed. Suppose Alice & Bob can interact for multiple rounds, i.e. Bob asks a question, Alice answers, then based on the answer Bob chooses what question to ask in the next round. Some of the answers can be long, some can be short.

However, if we use worst-case (not "average" in some sense) total number of bits as the criterion, it is still true that the $b$ bits encode a particular sequence of questions and answers. (Remember: Bob has no access to random bits, so his questions are deterministically based on Alice's previous answers). Thus with $b$ total bits it is still only possible to encode $2^b$ different boxes at most.

Answer 3

What @antkam suggested is a good starting point, but not entirely correct (according to me). The question asks how long the longest message should be that Alice gives to Bob so that they are guaranteed to win. If we admit messages with at most $b$ bits, we actually have $2^{b+1}-1$ messages since they could also be shorter.

Now lets go deeper on @antkam's point. Assume his third assumption holds. Now for each of the $2^{b+1}-1$ messages Alice can give, Bob needs to have a response. If this response were non-deterministic, then just select an arbitrary (but fixed) response from Bob's considerations, since each possible decision of Bob must lead to a prize. Now if $2^{b+1} -1+ k \leq n$ we see that we have a problem if the referee chooses the $k$ boxes that this strategy cannot reach. For this it is sufficient that the referee plays each of the possible $\binom{n}{k}$ combinations with non-zero probability (but need not be 'adverserial'). Notice that this condition is also necessary: if there is just one combination that the referee never plays, Alice and Bob can do better! We also see that Alice playing a random strategy or not has no effect on the counting argument.

Conclusion: to be certain of a win, Alice and Bob need at least one message with $\lceil\log_2(n-k+2)\rceil - 1$ bits of information (and this bound can trivially be achieved).

---

This is however only minimizing the maximal message size. If you want the message size to be the lowest-possible on average against for example a referee playing uniformly, you need the techniques that @leonbloy suggested. If we consider a deterministic strategy $f$ for Alice, meaning on input $X=(X_1,\dots,X_k)$ she redirects Bob to the box with ID $f(X)$, then it might well be that not every ID has equal probability of being chosen. By agreeing on a renumbering of the boxes, Alice and Bob can make advantage of this by giving boxes with a high probability of being $f(X)$ a short message length.

The average number of bits needed with this strategy $f$ is best measured with the classical entropy-function $\sum{-p_i \log_2(p_i)}$ (if I'm not mistaken). Now we should minimize the entropy of the image of $f$. Some candidates for $f$ could be: $f(X) = \min(X)$, $f(X) = \text{median}(X)$,... My experiments for small $n$ and $k$ show that the minimum-function is best on average among several $f$, but I don't know if this could be proven analytically.