This week’s Fiddler is based on “Showcase Showdown” on the game show “The Price is Right”.
Suppose we have some number of players. Player A is the first to spin a giant wheel, which spits out a real number chosen randomly and uniformly between 0 and 1. All spins are independent of each other. After spinning, A can either stick with the number they just got or spin the wheel one more time. If they spin again, their assigned number is the sum of the two spins, as long as that sum is less than or equal to 1. If the sum exceeds 1, A is immediately declared a loser.
After A is done spinning (whether once or twice), B steps up to the wheel. Like A, they can choose to spin once or twice. If they spin twice and the sum exceeds 1, they are similarly declared the loser. This continues until all players are done. Whoever has the greater value (that does not exceed 1) is declared the winner.
Assuming all players play the game optimally, what are player A’s chances of winning?
My solution:
[Show Solution]
We’ll assume there are $n$ players in total. Define the following:
\[
W_k(y) = \left\{ \begin{aligned}
&\text{Probability that the $k^\text{th}$}\\
&\text{player from the end will win}\\
&\text{assuming the highest number}\\
&\text{obtained so far is $y$.}
\end{aligned}
\right\}
\]In other words, $W_1$ is the probability the last player wins, $W_2$ is the probability the second-last player wins, etc. This is the quantity we need to solve for. It will also be helpful to define the probability that the last $k$ players all lose:
\[
L_k(y) = \left\{ \begin{aligned}
&\text{Probability that the last $k$}\\
&\text{players will be declared}\\
&\text{losers assuming the highest}\\
&\text{number obtained so far is $y$.}
\end{aligned}
\right\}
\]Let’s work our way backwards, starting from the last player. Suppose the number to beat is $y$. Since there is only one player left, $W_1(y) + L_1(y) = 1$. Let’s say they obtain $x$ on their first spin. Clearly, if $x > y$, they will stop (and win the game). Otherwise, they will try their chances with a second spin. Say they obtain $z$. They will win if they obtain a sum $x+z$ that is larger than $y$ but not larger than $1$. Therefore,
\begin{align*}
W_1(y) &= \int_y^1\,\mathrm{d}x + \int_0^y \int_{y-x}^{1-x}\, \mathrm{d}z\, \mathrm{d}x = 1-y^2
\end{align*}Consequently, $L_1(y)=y^2$. This makes sense. If $y$ (the number to beat) approaches $1$, then the probability of winning approaches zero because it becomes increasingly difficult to beat it.
Now consider the case with $k$ players remaining. Again, the number to beat is $y$. We will assume a threshold strategy: the player will spin a second time if their first spin is less than $a$, where $a$ is the threshold value. Clearly, if their first spin is less than $y$, they must spin again, otherwise they are guaranteed to lose. So $y < a < 1$. There are several cases to consider. Suppose the first spin is $x$ and the second spin, if needed, is $z$.
- If $y < a < x$, then $W_k(y) = L_{k-1}(x)$.
- If $y < x < a$, then if $x+z > 1$, we lose. Else, $W_k(y) = L_{k-1}(x+z)$.
- If $x < y < a$, then if $x+z > 1$ or $x+z < y$, we lose. Otherwise, $W_k(y) = L_{k-1}(x+z)$.
Expressing as integrals, the probability of winning with threshold $a$ is:
\begin{align*}
W_k(y,a) &=
\int_a^1 L_{k-1}(x)\,\mathrm{d}x
+ \int_y^a \int_{0}^{1-x} L_{k-1}(x+z)\,\mathrm{d}z\, \mathrm{d}x
+ \int_0^y \int_{y-x}^{1-x} L_{k-1}(x+z)\,\mathrm{d}z\, \mathrm{d}x\\
&= \int_a^1 L_{k-1}(x)\,\mathrm{d}x
+ \int_y^a \int_{x}^{1} L_{k-1}(v)\,\mathrm{d}v\, \mathrm{d}x
+ \int_0^y \int_{y}^{1} L_{k-1}(v)\,\mathrm{d}v\, \mathrm{d}x\\
&= \int_a^1 L_{k-1}(x)\,\mathrm{d}x
+ \int_y^a \int_{x}^{1} L_{k-1}(v)\,\mathrm{d}v\, \mathrm{d}x
+ y \int_{y}^{1} L_{k-1}(v)\,\mathrm{d}v
\end{align*}This player will pick $a \in [y,1]$ to maximize this probability of winning. In other words:
\[
W_k(y) = \underset{a \in [y,1]}{\text{maximize}}\; W_k(y,a)
\]The maximum will occur when the derivative with respect to $a$ is zero, or at $a=y$. Therefore, we have:
\[
a_k^\star(y) = \begin{cases}
\text{soln. of }L_{k-1}(a) = \int_{a}^1 L_{k-1}(v)\,\mathrm{d}v & \text{if it satisfies }a > y \\
y & \text{otherwise}
\end{cases}
\]Next, we can recursively compute $L_k$. In order for all players to lose, the current player must lose, and so must all others. This happens when the first spin is below the threshold, the second spin doesn’t beat $y$, and all subsequent players lose. In other words,
\begin{align*}
L_k(y) &= \int_y^{a_k^\star(y)}
\int_{1-x}^1 L_{k-1}(y)\,\mathrm{d}z\,\mathrm{d}x
+
\int_0^{y}\left(
\int_0^{y-x} L_{k-1}(y)\,\mathrm{d}z +
\int_{1-x}^1 L_{k-1}(y)\,\mathrm{d}z\right)\mathrm{d}x \\
&= \left( \int_y^{a_k^\star(y)}
\int_{1-x}^1 \mathrm{d}z\,\mathrm{d}x
+
\int_0^{y}\left(
\int_0^{y-x} \mathrm{d}z +
\int_{1-x}^1 \mathrm{d}z\right)\mathrm{d}x\right)L_{k-1}(y) \\
&= \left( \int_y^{a_k^\star(y)}
x\,\mathrm{d}x
+
\int_0^{y} y\, \mathrm{d}x\right)L_{k-1}(y) \\
&= \tfrac{1}{2}\left(a_k^\star(y)^2 + y^2\right) L_{k-1}(y)
\end{align*}The reason this can simplify so much is that the integrands are evaluated at $y$ because when the present player loses, the “best spin” does not change for subsequent players!
Two players
Applying the recursive formulas above, we find:
\begin{align*}
W_1(y) &= 1-y^2 \\
L_1(y) &= y^2 \\
W_2(y,a) &= \tfrac{1}{12}\left(4+4 a-4 a^3-a^4-3 y^4\right)
\end{align*}Things are starting to get messy… It turns out the optimal $a$ is given by:
\[
a_2^\star(y) = \max\left\{y, 2 \cos \left(\tfrac{2 \pi }{9}\right)-1\right\} \approx \max\{y,0.532089\}
\]Finding $W_2(y)$ is even messier, but thankfully, in this case, we can just let $y=0$ because the second last player is also the first player! This gives us a probability of winning of approximately:
\[
W_2(0) = \tfrac{1}{12} \left(9+4 \sin (\tfrac{\pi }{18})+2 \cos (\tfrac{\pi }{9})-8 \cos (\tfrac{2 \pi }{9})\right) \approx 0.453802
\]So the probability that the first (of two) players wins is about 45.38%. Here is a plot of $W_2(0,a)$ that shows how the probability of the first player winning varies as a function of their threshold. The function is maximized at $a^\star_2(0)$
Three players
Continuing our computations, we have:
\begin{align*}
a_2^\star(y) &\approx \max\{y,0.532089\} \\
L_2(y) &= \tfrac{1}{2}\left( y^2 + a_2^\star(y)^2 \right)y^2 \\
%W_3(y,a) &= -\tfrac{1}{24}\left(a^4+4 a^3-4 a+3 y^4-4\right) a_2^\star(y)^2\\
%&\hspace{3cm}-\tfrac{1}{60}\left(a^6+6 a^5-6 a+5 y^6-6\right)
W_3(y,a) &= \text{(messy)}
\end{align*} At this point, I abandoned any hope of analytic solutions… Optimizing numerically, I obtained:
\begin{align*}
a_3^\star(y) &\approx \max\{y,0.648655\} \\
W_3(0) &\approx 0.305227
\end{align*}So the probability that the first (of three) players wins is about 30.52%.
Similar to the previous section, here is a plot of $W_3(0,a)$ that shows how the probability of the first player winning varies as a function of their threshold. It’s a lot harder to win when there are three players!
More players
In principle, we can keep turning the crank and generating solutions for more players. The nice thing about this problem is that the optimal strategy for a given player does not depend on the total number of players; it only depends on how many players there are after the current player.
Here is a table of the thresholds I was able to calculate:
$k$ | $a_k^\star(y)$ (threshold) | $W_k(0)$ prob of win |
---|---|---|
$1$ | $\max\{y,0\}$ | $1.000000$ |
$2$ | $\max\{y,0.532089\}$ | $0.453802$ |
$3$ | $\max\{y,0.648655\}$ | $0.305227$ |
$4$ | $\max\{y,0.711449\}$ | $0.231060$ |
$5$ | $\max\{y,0.752249\}$ | $0.186229$ |
Here is how you read the table: Suppose you are the $k^\text{th}$ player from the end, say $k=3$. When your turn comes, let $y$ be the largest value obtained by any player before you. Pick whichever is largest, $y$ or $0.648655$, this becomes your threshold. Take your first spin. If you obtain something larger than the threshold, you’re currently winning, so pass your turn. Otherwise, spin again and hope for the best. The last column shows the probability of this player winning assuming they go first.
As $k$ gets larger, so does the threshold; the more players will spin after you, the more aggressive you have to be with your thresholding strategy. Also, notice that the probability of winning when you go first is a little less than $1/k$; the first player is always at a disadvantage, so we can expect their probability of winning to be below average.