# Optimal Random Bids

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.

• I don't think risk neutrality has anything to do with this, players simply try to maximize their probability of winning. Payoffs are binary, there are no safe average outcomes. – Giskard Mar 5 '16 at 19:29
• @denesp You could be risk averse in the sense that if you were to draw say 0.46, you might not want to redraw even though you have a better chance of getting a better number than a worse one. – Kitsune Cavalry Mar 5 '16 at 19:56
• @KitsuneCavalry I see what you're saying, but that would be some "behavioral" notion of risk aversion, as it's defined over an interim step rather than over the final outcomes. – Shane Mar 5 '16 at 20:08
• @Shane Sure, I hear ya. And I'm not too worried about it anyway. – Kitsune Cavalry Mar 5 '16 at 20:14

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.

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*}$$

• Someone did a similar derivation as you, and did this Wolfram calculation to double check it: tinyurl.com/j9xey5t So I'm going to ahead and say this looks right. Now if you solve the general form of this game, I'll give you best answer :P Kidding~ (Though it would be interesting to see how the game changes with more chances to reroll.) Does your edited cutoff mean both players have 50% of winning, or do you still think there is a mistake in your answer? – Kitsune Cavalry Mar 6 '16 at 1:07
• @KitsuneCavalry I think accepting it was a little premature but fortunately the calculation is correct and my reasoning about the 50% was wrong. The cut-off is so high that drawing it is 'lucky' and thereby you have a better than 50% chance of winning if you draw it. Before the draw you have exactly 50%. – Giskard Mar 6 '16 at 9:18
• If it counts for anything, the site that gave the question gave the answer. You got it on the money. Feel like a winner today. You earned it B) – Kitsune Cavalry Mar 28 '16 at 2:33

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}$.

• This is a great answer but why do you call the equilibrium a stable equilibrium? – Giskard Mar 6 '16 at 21:26
• @denesp I guess that's redundant. – f'' Mar 6 '16 at 23:22