9
$\begingroup$

Suppose three players play the following game: Player 1 picks a number in $[0,1]$. Then player $2$ picks a number in the same range but different from the number player $1$ picked. Player $3$ also picks a number in the same range but different from the previous two. We then pick a random number in $[0,1]$ uniformly randomly. Whoever has a number closer to the random number we picked wins the game. Assume all players play optimally with the goal of maximizing their probability of winning. If one of them has several optimal choices, they pick one of them at random.

1)If Player 1 chooses zero, what is the best choice for player 2?

2)What is the best choice for player 1?

I have some trouble seeing how this problem is well-defined. For instance, if Player $1$ picks $0$ and Player $2$ picks 1, then I cannot see what the optimal choice would be for the last player since he has to pick different numbers. Can someone help?

EDIT: I now understand better how the problem works, but I still have no idea how to approach this. Can someone give me some hints?

$\endgroup$
4
  • 2
    $\begingroup$ If player 1 picks $0$ and player 2 picks $1$, then no matter what player 3 picks, he will have a $50\%$ chance of winning the game. $\endgroup$
    – Arthur
    Jul 4, 2018 at 8:35
  • $\begingroup$ I see. But what if player 2 picks 0.5? Obviously then player 3 should pick something bigger than 0.5 yet really close to it but I don't see which one is optimal? $\endgroup$
    – Ted
    Jul 4, 2018 at 8:41
  • 2
    $\begingroup$ That is true, there isn't a single "optimal" number. However, "pick a number really close to, but greater than $0.5$" is still in some sense a description of an optimal strategy. $\endgroup$
    – Arthur
    Jul 4, 2018 at 8:42
  • 1
    $\begingroup$ @Arthur players can be female too. Let's get this "he" unconscious bias out please. Thanks. $\endgroup$ Jul 4, 2018 at 10:15

5 Answers 5

5
$\begingroup$

The first part. Let the three players choose $x,y,z$ in order. Suppose that $x=0$ and consider the third player's choice.

Option A: Choose $z>y$. Then the optimal choice is arbitrarily close to $y$ to make the winning probability arbitrarily close to $1-y$. In this case, the winning probability for the second player is arbitrarily close to (and a little larger than) $y/2$.

Option B: Choose $z<y$. The winning probability is always $y/2$, so the choice is a random element in $(0,y)$. In this case, the winning probability for the second player is $(1-y)+y/2=(1-y)/2$. [The probability that the random element is $\geq y$) $+$ (the probability that it is nearer than $z$ to $y$ conditioned on it being less than $y$)$\times$(probability of random number being less than $y$)].

The third player will choose A if $1-y>y/2$, i.e. if $y<2/3$ and will choose B if $y \geq 2/3$.

Whether the third player is made to choose option A or B, we can see that the optimal choice of $y$ is $2/3$.

The second part. This is an intuitive rather than analytic solution. After the first two players have made their choice, the maximum probability that the third player can get is among $x,(y-x)/2,1-y$. Equating the three of them, we get $x=1/4,y=3/4$, so both $1/4$ and $3/4$ should be optimal for the first player.

$\endgroup$
1
  • $\begingroup$ Is the second part generalizable for N+1 players? I am approaching game theory myself and found this tricky exercise. If we want the choice of player N+1 to be indifferent we should just equate all the interval segment lengths, shouldn't we? $\endgroup$
    – FBruzzesi
    Jan 24, 2021 at 21:19
4
$\begingroup$

I thought about this some more and realized why the question is posed the way it is, in two steps. We can use the first case to solve the general case recursively.

As the existing answers have established, the answer to part $1$) is $2/3$, and the payoffs in this case are $(\frac16,\frac12,\frac13$).

In the general case, by playing at $x_1$ Player $1$ effectively creates two new games on either side of $x_1$, one scaled down by $x_1$ and one scaled down by $1-x_1$, and these subgames work like the game in part $1$), since they're both delimited by a play by Player $1$ on one end and a normal boundary on the other.

Again, without loss of generality assume $x_1\le\frac12$. Either the other two players play in the same subgame, or in different subgames. If they play in the same subgame, it must be the larger one, of size $1-x_1$, since Player $3$ wouldn't play in the smaller game if Player $2$ has already played there. From $1)$ we know that in this case the payoffs are $(1-x_1)(\frac16,\frac12,\frac13)$, plus $x$ for Player $1$ that she gets on the other side, for a total of $(5x_1+1)/6$ for Player $1$.

Player $3$ plays in the smaller subgame if Player $2$ has played in the larger one and the payoff $x_1-\epsilon$ in the smaller subgame is larger than the payoff $\frac13(1-x_1)$ in the larger subgame, and thus if $x_1\gt\frac14$. In this case, Player $2$ would play at $1-x_1+\delta$ to deter Player $3$ from playing at $x_2+\epsilon$, so the payoff for Player $1$ would be $\frac\epsilon2+\frac\delta2+\frac12((1-x_1)-x_1)=\frac\epsilon2+\frac\delta2+\frac12-x_1$.

Player $2$ plays in the smaller subgame if the payoff $x_1-\delta$ in the smaller subgame is larger than the payoff $\frac12(1-x_1)$ in the larger subgame, and thus if $x_1\gt\frac13$. Player $3$ would then play at $x_1+\epsilon$. This would leave Player $1$ with only $\frac\delta2+\frac\epsilon2$, so she'll avoid this outcome.

Since at $x_1=\frac14$ we already have $(5x_1+1)/6\gt\frac12-x_1$, Player $1$ plays at $x_1=\frac14$.

$\endgroup$
3
$\begingroup$

Let $x_1$ denote the number picked by player $i$. Let $x_\lt$ and $x_\gt$ be the lesser and greater of $x_1$ and $x_2$. Also, I will use $\delta$ and $\epsilon$ to represent arbitrarily small displacements.

Player $3$ picks either $x_\lt-\epsilon$ or $x_\gt+\epsilon$ or any number (it doesn't matter which) in $(x_<,x_>)$. The payoffs for Player $3$ in these cases are $x_\lt-\epsilon$, $1-x_\gt-\epsilon$ and $(x_\gt-x_\lt)/2$, respectively, and she picks the greatest among these three. Note that in the third case, the half of the interval $[x_\lt,x_\gt]$ that Player $3$ doesn't win goes to Players $1$ and $2$ in equal parts (i.e. they each get one quarter of the interval), since in this case Player $3$ chooses uniformly randomly within that interval.

We can assume without loss of generality that $x_1\le\frac12$.

Now assume first that Player $2$ picks a number above $x_1$. Then we have to distinguish two cases.

For small $x_1$, it will not pay for Player $3$ to use her first option. Then there is a boundary for $x_2$ at which Player $3$ switches form her second to third option. This is the optimal move for Player $2$, since playing to either side of it would just cede territory. The condition for Player $3$ to be indifferent between these two options is $1-x_2=(x_2-x_1)/2$ and thus $x_2=(x_1+2)/3$. At this point $x_2-x_1=(2-2x_1)/3$. If Player $3$ goes for her second option, that interval is split evenly between Players $1$ and $2$, so the payoffs are $((2x_1+1)/3,(1-x_1)/3+\frac\epsilon2,(1-x_1)/3-\frac\epsilon2)$; whereas if Player $3$ goes for her third option, that interval is split in proportions $\frac14:\frac14:\frac24$ (see above), so the payoffs are $((5x_1+1)/6,(1-x_1)/2,(1-x_1)/3)$. At the equilibrium point, the $\epsilon$ difference favours Player $3$'s third option, where she doesn't lose $\frac\epsilon2$, and since this is favourable to Player $2$ (who gets $(1-x_1)/2$ instead of $(1-x_1/3)$), Player $2$ can play exactly at the equilibrium point and doesn't have to add a $\delta$ of his own to induce Player $3$ to choose her third option.

For larger $x_1$, it will become profitable for $x_3$ to switch to her first option. The point of indifference for this switch is $(1-x_1)/3=x_1$, or $x_1=\frac14$. For $x_1\gt\frac14$, Player $2$ plays as closely as he can to Player $1$ while still forcing Player $3$ to use her first option. The point of indifference for this is $x_2=1-x_1$, but Player $2$ has to play at $x_2=1-x_1+\delta$ to make sure that Player $3$ uses her first and not her second option. The payoffs are then $((1-2x_1)/2+\frac\delta2+\frac\epsilon2,\frac12-\frac\delta2,x_1-\frac\epsilon2)$.

We've found that by picking a number above $x_1$, Player $2$ gets $\frac12-\frac\delta2$ if $x_1\gt\frac14$ and $(1-x_1)/2\ge\frac38$ if $x_1\le\frac14$. So it will never pay for Player $2$ to play below $x_1$, and we've thus exhausted all cases.

To summarize: If Player $1$ plays at $x_1\le\frac14$, then Player $2$ plays at $x_2=(x_1+2)/3$, Player $3$ uses her third option, and the payoffs are $((5x_1+1)/6,(1-x_1)/2,(1-x_1)/3)$. If Player 1 plays at $x_1\gt\frac14$, then Player $2$ plays at $x_2=1-x_1+\delta$, Player $3$ uses her first option, and the payoffs are $((1-2x_1)/2+\frac\delta2+\frac\epsilon2,\frac12-\frac\delta2,x_1-\frac\epsilon2)$.

In the first case, the payoff for Player $1$ increases with $x_1$, and in the second case it decreases with $x_1$, so the maximum is around $\frac14$. In the first case, this yields a payoff of $\frac38$ for Player $1$, whereas in the second case the payoff is not more than $\frac14$. Thus Player $1$ picks $\frac14$, Player $2$ picks $\frac34$, and Player $3$ uses her third option, with expected payoffs $(\frac38,\frac38,\frac14)$.

$\endgroup$
0
$\begingroup$

Let $x,y,z$ be the choices of players 1,2 and 3 respectively. Let $a$ represent the random number we pick.

Best response function of $z$ given some $x=0$ and given some $y$:

The probability that player 3 wins:

Case: $z>y$ $$\int_{z}^{1} da\ +\ \int_{\frac{z+y}{2}}^{z}da$$ $$=1-z+z-\frac{z+y}{2}=1-\frac{z}{2}+\frac{y}{2}$$ Maximizing this with respect to $z$, player 3 will want it to be as close to $y$ as possible while it is still greater than $y$.

Case: $z<y$ $$\int_{\frac{z}{2}}^{\frac{y+z}{2}}da$$ $$=\frac{y+z}{2}-\frac{z}{2}=\frac{y}{2}$$

So if $1-y>\frac{y}{2}$ or $y<\frac{2}{3}$, player 3 will choose to play $z>y$ (as close to $y$ as possible),

otherwise player 3 can pick any $z<y$

Best response function of $y$ given $x=0$ is:

The probability that player 2 wins:

Case: $y\leq\frac{2}{3}$ $$\int_{\frac{y}{2}}^{y}da=\frac{y}{2}$$

Case: $y>\frac{2}{3}$ $$\int_{\frac{y+z}{2}}^{1}da=1-\frac{y}{2}-\frac{z}{2}$$

So $y=\frac{2}{3}$

$\endgroup$
0
$\begingroup$

Intuitive explaination for part 2 (agreeing with the answer by @Aravind but providing more explainations):

After the first two players chose their positions, the optimal play for player 3 is fixed. The line is separated into 3 segments, each with a max expected reward for player 3 of $p_1 = \frac{x}{2}$, $p_2=\frac{y-x}{2}$, and $p_3=\frac{y}{2}$, assuming $0 \leq x \leq y \leq 1$ are the positions the first two people chose. And player 3 is going to choose $$max\{p_1, p_2, p_3\}$$

Without loss of generosity, assume player 1 is at $x$.

From the perspective of player 2: After choosing his position 2 has some original gain if 3 didn't exist. Now include 3 in the picture.

  • If 3 chooses $p_3$, 2 loses from his original profit all that 3 gains.
  • If 3 chooses $p_2$, 2 loses half of what 3 gains
  • If 3 chooses $p_1$, 2 loses nothing.

Since 3 is likely to be able to get some considerable (~1/3) gain, having 3 "take more from 2's bowl" is very unpreferable to 2. Therefore, in not too extreme situations, 2 optimizes for his own gain in the constraint that $$p_1 \geq p_2 \geq p_3$$

By symmetry between 1 and 2 at the instance we are looking at (when both have chosen positions and 3 hasn't), we know that 1 optimizes for his gain while hoping that $$p_3 \geq p_2 \geq p_1$$

This is similar to a minimax situation, and the optimal strategy for 1 would satisfy both inequalities, giving $$p_1 = p_2 = p_3$$ $$\frac{x}{2} = \frac{y-x}{2} = \frac{y}{2}$$

Solving it we get $x = 1/4$, $y = 3/4$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .