Higher or lower? (#2)

Question

$N \geq 2$ players play a game - at the start of the game, they are each given independently and uniformly a number from $[0, 1]$. On each round, they are to guess whether their number is higher or lower than the average of the remaining players. All who guess wrongly are eliminated before the next round starts.

Assumptions:

• Players only know their own number, and not anyone else’s.

• Players are myopic and play only to optimise their survival probability in the present round.

• Players all follow an optimal strategy.

• The players are given full information on the actions of other players in previous rounds and subsequent eliminations.

Without any analysis, we know that the optimal strategy is to guess "higher" if one's number exceeds a certain value depending on the information available to the player so far.

Question: What is the optimal strategy?

Answer 1

Here is an attempt to get started on finding the optimal strategy. In fact, it seems to get much harder to find as the number of rounds increases - even the second round is tricky. My analysis focuses only on this second round.

First to discard some trivialities. Should the players all guess correctly in any particular round, the optimal strategy is obviously to repeat the guesses in that round, in which case the players all survive indefinitely. Next, the optimal strategy in the first round is obviously to guess "higher" if and only if your number $X_0 \geq \frac{1}{2}$.

Now we begin the analysis of the second round. We suppose there are $N$ other players with numbers $X_1, \dots X_N$. Let $S$ be the index set of surviving players by the second round, $L$ the set of players that guessed "lower", and $H$ the set of players that guessed "higher" in the first round.

If we are eliminated by the second round, the question is moot, so we are a priori in the situation where $X_0 \geq \frac{1}{N}\sum_{i = 1}^N X_i$. Thus the probability distribution is that conditioned on this event.

To the best of our knowledge, the probability of surviving upon guessing "higher" in the second round, is given by

$$\mathbb P(X_0 \geq \frac{1}{|S| }\sum_{i \in S} X_i \, \big | \{\, X_0 \geq \frac{1}{N}\sum_{i = 1}^N X_i \}, \, |L|, |H|, |L \cap S|, |H\cap S|),$$

and we will guess "higher" if this conditional probability is greater than $\frac{1}{2}$.

Now we know that each player $i$ guesses "higher" in the first round iff $X_i \geq \frac{1}{2}$, thus actually with certainty we have either one of $|L \cap S| = |L|$ or $|H \cap S| = |H|$, depending on if the average $\frac{1}{N+1}\sum_{i = 0}^N X_i$ is higher or lower than $\frac{1}{2}$ respectively. We illustrate the former case only.

In the former case, we have instead now the conditional probability

$$\mathbb P(X_0 \geq \frac{1}{|S| }\sum_{i \in S} X_i \, \big | \,\{\frac{1}{2}\big ( \frac{N+1}{N} \big ) - \frac{X_0}{N} \leq \frac{1}{N}\sum_{i = 1}^N X_i \leq X_0 \}, \, |L|, |H|, |H\cap S|),$$

and at this point I will give up, as it is unclear how to analyse this fearsome expression. In the end it seems I have done little but illustrate the complexity of the problem...