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?

(Fiddler on the Proof)

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 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:$

\[\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 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 $z$ energy 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$ enters with energy $g.$ Team $\alpha$ emerges 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 cases where the remaining energy is less than or equal to $c$ and take the derivative

\[\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 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 simply 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. However, since the PDF is simply the derivative of the CDF we just found, and evaluating the CDF at $0$ yields $0,$ this integral evaluates exactly to 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 our 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$

(* 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: