Robot Weightlifting Competition - Optimize chance of winning

Question

This is a puzzle posted by JaneStreet

They just released a solution to the puzzle today!

I disagree with their solution, but it's probably because I don't understand it. The issue is the way they calculate the probability of Robot 1 winning which is the best way to start. I'll also discuss how I got my solution in case I'm right (what a thrill that would be!).

Problem

The Robot Weightlifting World Championship’s final round is about to begin! Three robots, seeded 1, 2, and 3, remain in contention. They take turns from the 3rd seed to the 1st seed publicly declaring exactly how much weight (any nonnegative real number) they will attempt to lift, and no robot can choose exactly the same amount as a previous robot. Once the three weights have been announced, the robots attempt their lifts, and the robot that successfully lifts the most weight is the winner. If all robots fail, they just repeat the same lift amounts until at least one succeeds.

Assume the following:

1. all the robots have the same probability p(w) of successfully lifting a given weight w;

2. p(w) is exactly known by all competitors, continuous, strictly decreasing as the w increases, p(0) = 1, and p(w) -> 0 as w -> infinity; and

3. all competitors want to maximize their chance of winning the RWWC.

If w is the amount of weight the 3rd seed should request, find p(w). Give your answer to an accuracy of six decimal places.

Setup

We only need to consider the probability of lifting a weight successfully. I'm going to represent this with $R_3$ for the probability ($p(w)$) of Robot 3 successfully lifting a weight; similarly I'll use $R_2$ for Robot 2 and $R_1$ for Robot 1.

Order matters here. If $R_3$ and $R_2$ choose the same weight (and successfully lift it), $R_2$ will win because they will presumably choose an infinitesimal amount heavier than $R_3$.

When discussing the strategy for $R_1$, $R_{min}$ is $min(R_2, R_3)$ and $R_{max}$ is $max(R_2, R_3)$

My solution

I think the correct answer is $R_3$ should be 1/2, then $R_2$ is 1/3 and $R_1$ is 1.

My approach was to start with $R_1$ since it should be easy to determine their probability of winning. I made a lookup table (see below photo).

These three calculations for probability of losing is where my answer diverges from the solution

The way I determined this lookup table is by picking the optimum value among three cases:

1. Undershoot the lowest value (between $R_2$ and $R_3$): $$R_{min}$$
2. Undershoot the max value (between $R_2$ and $R_3$): $$R_{max}*(1-R_{min})$$
3. Overshoot both and choose 1.0: $$(1-R_2)*(1-R_3)$$

Based on these parameters we can make a map of $R_1$ for each value of $R_2$ and $R_3$ (see picture below).

Robot 2 will know what Robot 1 will choose and will optimize their choice for Robot 1's choice. Robot 3 knows this and will have a picture of Robot 2's chance of winning in mind.

Robot 3 knows that Robot 2 will optimize for themself. So Robot 3 looks at all the optimum choices for Robot 2 and sees which one has the best outcome for themself (Robot 3). In other words, Robot 3 picks the column knowing that and Robot 2 picks the row and optimizes for it.

Graphs for visualization

Black is 0 and white is 1.

Puzzle Solution

The puzzle solution takes the same approach except the way the probability of Robot 1 winning is calculated which affects the optimum choice.

Their description [transposed with my notation] is:

1. lift an arbitrarily small amount more than the Robot 3, to have ($R_3$-$\epsilon$) chance of success,
2. lift an arbitrarily small amount more than the Robot 2, to have ($R_2$-$\epsilon$) chance of success,
3. lift zero weight with success probability 1.

They have [transposed with my notation]:

$$\frac{R_3}{1-(1-R_3)^2(1-R_2)}$$ $$\frac{(1-R_3)R_2}{1-(1-R_3)(1-R_2)^2}$$ $$(1-R_3)(1-R_2)$$

Where $\epsilon \to 0$

Question

Everything makes sense except the denominators; where do they get those denominators?

Answer 1

I think you are are just missing the fact that the competition might take several rounds until some robot succeeds.

Under the first strategy, Robot 1 wins in $r$ rounds if all three robots fail in all previous rounds and Robot 1 succeeds in round $r$. This happens with probability $$(1-R_3)^{r-1} (1-R_2)^{r-1} (1-R_1)^{r-1} R_1 = [(1-R_3)(1-R_2)(1-R_1)]^{r-1} R_1,$$ so summing the infinite geometric series over all rounds yields overall win probability \begin{align} \sum_{r=1}^\infty [(1-R_3)(1-R_2)(1-R_1)]^{r-1} R_1 &= \frac{R_1}{1-(1-R_3) (1-R_2)(1-R_1)} \\ &\to \frac{R_3}{1-(1-R_3)^2 (1-R_2)}. \end{align}

Under the second strategy, Robot 1 wins in $r$ rounds if all three robots fail in all previous rounds, Robot 3 fails in round $r$, and Robot 1 succeeds in round $r$. This happens with probability $$[(1-R_3) (1-R_2)(1-R_1)]^{r-1} (1-R_3)R_1,$$ so summing the infinite geometric series over all rounds yields overall win probability \begin{align} \sum_{r=1}^\infty [(1-R_3)(1-R_2)(1-R_1)]^{r-1} (1-R_3)R_1 &= \frac{(1-R_3)R_1}{1-(1-R_3)(1-R_2)(1-R_1)} \\ &\to \frac{(1-R_3)R_2}{1-(1-R_3) (1-R_2)^2}. \end{align}

Under the third strategy, Robot 1 wins if Robots 2 and 3 fail in round $1$. This happens with probability $$(1-R_3) (1-R_2).$$

---

Alternatively, you can avoid the infinite series by using recursion. Let $W$ be the probability that Robot 1 wins. Then by conditioning on three mutually disjoint cases for the current round (Robot 1 succeeds, Robot 1 fails and Robot 2 or 3 succeeds, or all three robots fail), we have under the first strategy that $$W = R_1\cdot 1 + [1-(1-R_3)(1-R_2)](1-R_1)\cdot 0 + (1-R_3)(1-R_2)(1-R_1) W,$$ which implies that $$W = \frac{R_1}{1-(1-R_3)(1-R_2)(1-R_1)} \to \frac{R_3}{1-(1-R_3)^2(1-R_2)}.$$

Under the second strategy, we similarly obtain $$W = (1-R_3)R_1\cdot 1 + (1-R_3)(1-R_2)(1-R_1) W,$$ which implies that $$W = \frac{(1-R_3)R_1}{1-(1-R_3)(1-R_2)(1-R_1)} \to \frac{(1-R_3)R_2}{1-(1-R_3)(1-R_2)^2}.$$

---

Here is a rough description of the thought process I used for the infinite series approach. I don't know how many rounds it will take until some robot succeeds, but I know how to calculate the probability that Robot 1 wins in exactly $r$ rounds, by considering $r-1$ failures and then $1$ success. The argument is similar to computing the probability mass function of a geometric random variable. Then I can use the law of total probability to add up the probabilities of these disjoint events that yield a Robot 1 win.

For the recursive approach, the main idea is to notice that if some robot succeeds in round 1, you are done, and otherwise you are back where you started for the next round. It is another application of the law of total probability.