Question
Congratulations to Fiddler Nation for making it to the semifinals of the World Cup! All four teams that made it this far are equally matched in that they each possess the same total amount of “energy.” In advance of each semifinal game, teams must independently decide how much of their energy to allocate to the match; all remaining energy goes toward the finals. The team that spends more energy in any given game will win. The semifinals and finals occur so close in time that teams can’t recuperate any of their energy in between.
You’ve heard that the managers for the other three teams are abysmal and have no idea how to allocate their teams’ energy. Each of the other managers will independently pick a random percentage between $0$ and $100$ and allocate that portion of their team’s energy to the semifinal game; the rest of that team’s energy will go toward the final.
Since you’re the cleverest manager of the bunch, you can choose an optimal strategy that will maximize Fiddler Nation’s probability of winning the World Cup. What is this optimal probability?
Extra Credit
As it turns out, I spoke too soon. Fiddler Nation has made it to the quarterfinals of the World Cup rather than the semifinals. My mistake. As before, teams must allocate the same total amount of energy across up to three matches.
The managers for the other seven teams remain abysmal. Each manager will independently pick a random percentage between $0$ and $100$ and allocate that amount of their team’s energy to the quarterfinal. If they win, they will allocate a random amount of their remaining energy to the semifinal. And if they win that, the rest of their team’s energy will go toward the final.
Fiddler Nation’s strategy must be drawn up in advance, with no specific knowledge of the other teams’ strategies beyond what I have already shared.
That said, as the cleverest manager of the bunch you can once again choose an optimal strategy that will maximize Fiddler Nation’s probability of winning the World Cup. What is this optimal probability?
Solution
The smart manager’s team wins if it wins in all three rounds, so our approach will be to find those three probabilities in terms of $x$ and $y,$ multiply them, and find a point where the derivatives with respect to both variables is zero.
The first round
In the first round, we play a chosen amount $x$ and our opponent is a random number between $0$ and $1.$ The probability that they lose to us is just $x.$
The second round
In the second round, we play a chosen amount $y$ against the winner of another first round match. We should expect this number to bias toward small numbers and away from large numbers, since they’ve already spent some energy winning the first round.
We can find this probability using the connection between CDFs and PDFs
\[P(\text{first round winner has }z\text{ left}) = \frac{\text{d}}{\text{d}z} P(\text{first round winner has }\leq z\text{ left}).\]The first round winner has $z$ or less left when one minus the max of the first round energies was less than $z.$ In other words, neither of the first round competitors picked a random number between $z$ and $1:$
\[\begin{align} P(1-\max \{r_1, r_2\} \leq z) &= P(1-z\leq\max\{r_1,r_2\}) \\ &= 1-(1-z)^2. \end{align}\]Taking the derivative of the CDF with respect to $z$ we get
\[\begin{align} P(z\text{ remaining for second round}) &= \frac{\text{d}}{\text{d}z} \left[1-(1-z)^2\right] \\ &= 2(1-z). \end{align}\]If the smart manager’s second round opponent has energy $z$ left going into the second round, they will again play a random amount of what they have left. So they will play $zr,$ where $r$ is another random unit number, and the smart manager wins when $y \gt zr.$
\[P(y \gt zr) = \begin{cases} 1 & \text{if } z < y \\ \frac{y}{z} & \text{if } z \ge y \end{cases}\]And the probability the smart manager wins the second round is
\[\begin{align} P(\text{win second round}) &= \int_0^1 \text{d}z\, P(y \gt zr) P(z) \\ &= \int_0^y \text{d}z\, 2(1-z) + \int_y^1 \text{d}z\, \frac{y}{z}2(1-z) \\ &= y^2 - 2y\log y \end{align}\]The third round
In the third round, there is no choice left since the smart manager’s remaining energy is set by $1-x-y.$ If the winner of the opposite bracket has remaining energy $c$ then the smart manager wins when $1-x-y \gt c$ and the probability that they win the round is
\[P(\text{win third round}) = \int_0^1 \text{d}c\, P(1-x-y \gt c)P(c).\]To find $P(c)$ let’s assume that the opposing bracket has $4$ players $\alpha, \beta, \gamma,$ and $\delta$ and that $\alpha$ and $\gamma$ face off in the quarterfinal match, with $\alpha$ winning. Team $\alpha$ exits the first round with energy $a$ and team $\gamma$ exits with energy $g.$ Team $\alpha$ goes into the final round with remaining energy $c$ if the amount they spent in the second round is $a^\prime = a-c,$ and they spent more than team $\gamma$: $a^\prime \gt g^\prime.$ We need to average the probability of this outcome over all possible values of $a, g, a^\prime,$ and $g^\prime.$
Again, it is easier to use the CDF/PDF connection than to find the PDF directly, so we will account for all possible cases where the remaining energy is less than or equal to $c$ and take the derivative. Team $\alpha$ can use any amount of energy from $0$ up to $a-c$ (cutting off at zero if $a - c \lt 0$) and team $\gamma$ can use any amount from $0$ up to $a^\prime$ (the amount played by $\alpha$) unless $a^\prime$ exceeds $g.$ We account for all possible values of $f$ and $g$. Finally, we multiply by $2$ to account for the arbitrary choice of $\alpha$ as the winner:
\[\begin{align} &P(\text{opposing bracket winner's remaining energy} \leq c) = \\ &\quad\quad 2\int_0^1\text{d}a \int_0^1 \text{d}g\, P(a)P(g) \frac{1}{a}\int_0^{\max(a-c,0)} \text{d}a^\prime\, \frac{1}{g} \int_0^{\min(a^\prime, g)}\text{d}g^\prime. \end{align}\]The distributions for $a$ and $g$ are just what we found in the second round, $P(a) = 2(1-a)$ and $P(g)=2(1-g).$
Evaluating the integral results in the magnificent expression for the CDF of the opponent’s remaining energy:
\[\begin{aligned} &P(\text{opposing bracket winner's remaining energy} \leq c) = \\ &\quad \frac{1}{3} \Bigg( 8c^3 \text{arctanh}(1-2c) + 2(3c^2 - 6c + 1)\ln(1-c) \\ &\quad\quad + c\Big(c^3 + 2c(\pi^2 - 10) + 6c(1 - 2\ln c)\ln c + 22\Big) - 12c^2 \Re\left(\text{Li}_2\left(\frac{1}{c}\right)\right) \Bigg) \end{aligned}\]Now, we have to evaluate the probability to win the third round. The smart manager wins when $1-x-y > c,$ so we integrate the PDF over the winning range. Because the PDF is the derivative of the CDF we just found, and evaluating the CDF at $0$ yields $0,$ this integral is simply the CDF evaluated at $1-x-y:$
\[\begin{align} P(\text{win round three}) &= \int_0^1\text{d}c\, P(1-x-y>c)P(c) \\ &= \int_0^{1-x-y}\text{d}c\, P(c) \\ &= \int_0^{1-x-y}\text{d}c\, \frac{\text{d}}{\text{d}c} P(\text{opponent energy} \leq c) \\ &= P(\text{opponent energy} \leq 1-x-y) \end{align}\]Plugging $c = 1-x-y$ into the CDF yields the win probability for round three:
\[\begin{aligned} &P(\text{win round three}) = \\ &\quad \frac{1}{3} \Bigg( 8(1-x-y)^3 \text{arctanh}(2x+2y-1) + 2\big(3(1-x-y)^2 - 6(1-x-y) + 1\big)\ln(x+y) \\ &\quad\quad + (1-x-y)\Big((1-x-y)^3 + 2(1-x-y)(\pi^2 - 10) \\ &\quad\quad\quad + 6(1-x-y)\big(1 - 2\ln(1-x-y)\big)\ln(1-x-y) + 22\Big) \\ &\quad\quad - 12(1-x-y)^2 \Re\left(\text{Li}_2\left(\frac{1}{1-x-y}\right)\right) \Bigg) \end{aligned}\]Overall Win Probability
The probability to win the tournament is the product of the probabilities to win each round:
\[P(\text{win overall}) = P(\text{win round one}) \cdot P(\text{win round two}) \cdot P(\text{win round three})\]This gives us a surface in the space of strategies $(x,y).$ We can find its maximum by finding the point where the partial derivatives in each direction are both equal to zero.
Doing that, we get
\[(x^\text{opt}, y^\text{opt}, 1-x^\text{opt}-y^\text{opt}) \approx \left(0.5196555337, 0.2296375664, 0.2507068997\right),\]which gets a maximum win probability of $P(\text{win overall}) \approx 0.2816222513\dots$
Counterintuitively, we should hold on to more energy for the final round than for the second to last round even though the opponent has less energy than they had in the second round. This is because in the last round they spend everything they have left, no matter what. We have to hedge to account for the fact that they’ll be going for broke.
(* CDF of c *)
CDFc = FullSimplify[
ComplexExpand[Re[
2 * Integrate[
2 (1 - a) * 2 (1 - g) * (1/a) * (1/g)
, {a, 0, 1}
, {g, 0, 1}
, {ap, Max[a - c, 0], a}
, {gp, 0, Min[ap, g]}
, Assumptions -> {0 < c < 1}
]
]],
Assumptions -> {0 < c < 1}
];
(* round by round probabilities *)
pWinFirstRound = x;
pWinSecondRound = y * (y - 2 * Log[y]);
pWinThirdRound = FullSimplify[
(CDFc /. {c -> 1 - x - y}) - Limit[CDFc, c -> 0]
];
(* overall win probability *)
pWinOverall = FullSimplify[pWinFirstRound * pWinSecondRound * pWinThirdRound];
(* optimize *)
NMaximize[{
pWinOverall,
1/1000 < x < 1,
1/1000 < y < 1,
1/1000 < x + y < 1
}, {x, y}, WorkingPrecision -> 15]
Win probability surface
Below we have the overall win probability surface $P(\text{Win Overall})$ as a function of the energies $x$ and $y$. The region where $x + y \geq 1$ gives probability zero since no energy is left for the final round: