I remembered this interesting question about game theory from a job application, and would like to get some verification on the solution I came up with (since I didn't get to know if it was correct). Not sure if I should present this as a Q&A style but I think I should stick to the traditional format.
Three players A, B, C play the following game. First, A picks a real number between 0 and 1 (both inclusive), then B picks a number in the same range (different from A’s choice) and finally C picks a number, also in the same range, (different from the two chosen numbers). We then pick a number in the range uniformly randomly. Whoever’s number is closest to this random number wins the game. Assume that A, B and C all play optimally and their sole goal is to maximise their chances of winning. Also assume that if one of them has several optimal choices, then that player will randomly pick one of the optimal choices.
There are 3 parts to this question – the parts which I'm unsure of are 2 and 3. (Although I'm most interested if part 3 is solvable without any computation)
Part 1: If A chooses 0, then what is the best choice for B?
Begin by defining $M_X$ as the minimum probability of winning for player $X$. The problem can then be reformulated as follows: how does player B pick $b\in (0,1)$ such that $M_B$ is maximized? \
Suppose B chooses $b\in (0,1)$ (We omit the possibility of B choosing 1 since $M_B = 0$ in this case). \
Then, C has two regions to choose from: either $(0,b)$ or $(b,1)$. \
If C chooses the region $(0,b)$, this implies that it has a $b/2$ chance of winning and that
$$\frac{b}{2} \geq 1- b \implies M_B = 1-b \leq \frac{1}{3}$$
Conversely, if C chooses the region $(b,1)$ (i.e. C chooses $b+\epsilon$ for some small $\epsilon$), this implies that it has a $1-b – \frac{\epsilon}{2}$ chance of winning and that
$$1-b \geq \frac{b}{2} \implies M_B = \frac{b}{2} \leq \frac{1}{3}$$
Thus, we require that
$$ 1-b = \frac{b}{2}$$
Hence, Player B should choose ${b = \frac{2}{3}}$.
Part 2: What is the best choice for A?
For simplification, let us restrict the choice of A to $[0,\frac{1}{2}]$ since the converse arguments will work via symmetry. Denote the choice of player A as $a$.
Observe that A cannot choose any value of $a$ which is larger than $\frac{1}{4}$. An argument is provided below:
Suppose $a = \frac{1}{4} + k$ such that $k\in (0,\frac{1}{4})$, then $M_B$ is maximized by choosing $b = \frac{1}{4} + k – \epsilon_1$ for some $\epsilon_1 > 0$ (Since B has to choose $b = \frac{3}{4} + \frac{k}{3}$ if $b \in (\frac{1}{4}+k, 1)$ (same reasoning from Part 1), which means that $ M_B =\frac{1}{4} – \frac{k}{3} < \frac{1}{4} + k – \frac{\epsilon_1}{2}$). $M_C$ will thus be maximized by choosing $c = \frac{1}{4} + k + \epsilon_2$ for some $\epsilon_2 > 0$. This will result in $M_A = \frac{\epsilon_1 + \epsilon_2}{2}$.
Thus, we see that player A needs to choose $a \in [0, \frac{1}{4}]$. But choosing anything other than $a = \frac{1}{4}$ is equivalent to `leaving money on the table'. I.e. if $a = \frac{1}{4} – \epsilon$, $\epsilon \in [0,\frac{1}{4}]$, then we can argue that player B will always choose a value $b \in (\frac{1}{4} – \epsilon,1)$, since by doing so B would obtain $M_B \geq \frac{1}{4}$, guaranteeing that $M_A > \frac{1}{4} – \epsilon$, which is arbitrarily small.
Hence, the best choice for A is $a = \frac{1}{4}$ (or $a = \frac{3}{4}$ by symmetry)
Can you write a program to figure out the best choice for the first player when the game is played among four players?
I was wondering if it might be possible to do this without using a computer, so I provided the following line of reasoning – Is this correct?
Using the arguments of part 2 (and induction), the best choice for the first player would be $\frac{1}{5}$ (or $\frac{4}{5}$ by symmetry).
Best Answer
In part(B), $P_1 = \frac{1}{4}, P_2=\frac{3}{4}$
So length that $(1,2,3)$ obtain is $(\frac{1}{4}+x, \frac{1}{4}, \frac{1}{2} -x)$
i.e. FACT they get min $\frac{1}{4}$
Now, in 4-Player case:
Suppose, $P_1$ takes position $x$.
$P_2, P_3, P_4$ would choose the length $(x, 1)$ as per division in Part-B $ \ \ $ iff
length $($ left of $x) \leq \frac{1}{4}*(1-x) \ \ \ \ ...$ Using FACT
$x \leq \frac{1}{4}*(1-x)$
Thus, $x = \frac{1}{5}$