Optimal Random Bids

Question

This question comes from this website that I peruse often.

Two players go on a hot new game show called “Higher Number Wins.” The two go into separate booths, and each presses a button, and a random number between zero and one appears on a screen. (At this point, neither knows the other’s number, but they do know the numbers are chosen from a standard uniform distribution.) They can choose to keep that first number, or to press the button again to discard the first number and get a second random number, which they must keep. Then, they come out of their booths and see the final number for each player on the wall. The lavish grand prize — a case full of gold bullion — is awarded to the player who kept the higher number. Which number is the optimal cutoff for players to discard their first number and choose another? Put another way, within which range should they choose to keep the first number, and within which range should they reject it and try their luck with a second number?

This is either a very weird auction problem with symmetric players (I also assume the players are risk-neutral) or a very odd lotteries/game-theory game.

How would you approach this question mathematically speaking and what answer do you get for it? There's no prize for me getting the right answer to the site's riddle, I'm just curious. My intuition tells me that the optimal cutoff is 0.5, since you have a 50-50 chance of being higher or lower than your opponent's number, regardless of whether he/she repicks their random number or not, but I am not sure.

Answer 1

First I will just show that the 0.5 (or $\frac{1}{2}$) cut-off point does not work as a symmetric equilibrium, then you can decide for yourself if you want to think about the problem or read the complete answer.

Let us denote the cut-off points by $c_x,c_y$. Suppose both players use the strategy $c = \frac{1}{2}$. Let us denote the numbers of player $x$ and $y$ respectively by $x_1$ and $y_1$ and their potential second number by $x_2$ and $y_2$. Suppose $x_1 = \frac{2}{3}$. By keeping this the probability that player $x$ wins is $$ P\left(\frac{1}{2} \leq y_1 < \frac{2}{3} \right) + P\left(y_1 < \frac{1}{2}\right) \cdot P\left(y_2 < \frac{2}{3}\right) = \frac{1}{6} + \frac{1}{2} \cdot \frac{2}{3} = \frac{1}{2}. $$ This also means that $\frac{2}{3}$ is the median of this distribution.

Now suppose $x_1 = \frac{1}{2}$. By keeping this the probability that player $x$ wins is $$ P\left(y_1 < \frac{1}{2}\right) \cdot P\left(y_2 < \frac{1}{2}\right) = \frac{1}{2} \cdot \frac{1}{2} = \frac{1}{4} $$ But if he would discard $x_1 = \frac{1}{2}$ he has probability $$ P\left(y_1 < \frac{1}{2}\right) \cdot P\bigg(x_2 > y_2\bigg) + P\left(y_1 \geq \frac{1}{2}\right) \cdot P\bigg(x_2 > y_1\bigg) = \frac{3}{8} $$ of winning. $\frac{3}{8} > \frac{1}{4}$ so keeping $x_1 = \frac{1}{2}$ (and its environs) is not optimal therefore it cannot be an equilibrium move.

---

SPOILER ALERT

If player $y$ has a cut-off $c_y$ and player $x$ draws $x_1 = c_y$ and keeps it the probability that player $x$ wins is $$ P(y_1 < c_y) \cdot P(y_2 < c_y ) = c_y \cdot c_y = c_y^2. $$ If player $x$ where to discard $x_1$ the probability that he wins is \begin{eqnarray*} P(y_1 \geq c_y) \cdot P(x_2 > y_1) + P(y_1 < c_y) \cdot P(x_2 > y_2) & = & (1 - c_y) \cdot \left(1- \frac{1 + c_y}{2} \right) + c_y \cdot \frac{1}{2} \end{eqnarray*} Suppose there is a symmetric equilibrium, that is $c_x = c_y = c$.
(I don't think other equilibria exist but I didn't prove it.)
Since probability of winning is continuous in the value of $x_1$, the cut-off value $c$ is such that if $x_1 = c$ then the probability of winning is equal when $x_1$ is kept and when it is discarded. This means that \begin{eqnarray*} P(y_1 < c) \cdot P(y_2 < c) & = & P(y_1 \geq c) \cdot P(x_2 > y_1) + P(y_1 < c) \cdot P(x_2 > y_2) \\ \\ c \cdot c & = & (1 - c) \cdot \left(1 - \frac{1+c}{2}\right) + c \cdot \frac{1}{2} \\ \\ c^2 & = & \frac{1}{2} - c + \frac{c^2}{2} + \frac{c}{2} \\ \\ \frac{1}{2} \cdot c^2 + \frac{c}{2} - \frac{1}{2} & = & 0 \\ \\ c & = & \frac{\sqrt{5} - 1}{2}. \end{eqnarray*}

Answer 2

Suppose person 1 chooses a cutoff of $c_1$ and person 2 chooses a cutoff of $c_2$, with $c_2\ge c_1$. Let $p_1(x)$ be the probability that person 1's final number is no greater than $x$. $p_1(x)$ equals $c_1x$ if $x<c_1$ and $c_1x+x-c_1$ otherwise. Define $p_2(x)$ similarly. Now plot $p_2(x)$ against $p_1(x)$ on a parametric plot for $0\le x\le1$. The result is three line segments:

• One from $(0,0)$ to $(c_1^2,c_1c_2)$, corresponding to $0\le x\le c_1$;
• One from $(c_1^2,c_1c_2)$ to $(c_1c_2+c_2-c_1,c_2^2)$, corresponding to $c_1\le x\le c_2$;
• One from $(c_1c_2+c_2-c_1,c_2^2)$ to $(1,1)$, corresponding to $c_2\le x\le1$.

These three line segments divide the unit square into two parts. The area of the part under the graph is the probability that person 1 has the higher number. Some geometry shows that this area is $\frac{1}{2}+\frac{1}{2}(c_2-c_1)(c_1c_2+c_2-1)$. For there to be a stable equilibrium, both partial derivatives of this must be zero, i.e. $$1-c_2-2c_1c_2+c_2^2=0\\-1-c_1+2c_2-c_1^2+2c_1c_2=0$$

Adding the equations shows that $(c_2-c_1)(1+c_1+c_2)=0$, which is only possible if $c_1=c_2$. Substituting back into one of the equations, $1-c_1-c_1^2=0$, so the only stable equilibrium is at $c_1=c_2=\frac{\sqrt{5}-1}{2}$.