Source

I got this problem from Rustan Leino, who got it from Johannes Kinder, who said he heard it from his brother. Rustan reformulated the setting.

I solved it and wrote up my solution.

Problem

A particular basketball shootout game consists of a number of duels. In each duel, one player is the challenger. The challenger chooses another player to challenge, and then gets one chance to shoot the hoop. If the player makes the shot, the playing being challenged is out. If the player does not make the shot, or if the player chooses to skip their turn, then the game continues with the next duel. A player wins when only that player remains.

One day, this game is played by three players: A, B, and C. Their skill levels vary considerably: player A makes every shot, player B has a 50% chance of making a shot, and player C has a 30% chance of making a shot. Because of the difference in skill levels, they decide to let C begin, then B, then A, and so on (skipping any player who is out of the game) until there is a winner. If everyone plays to win, what strategy should each player follow? In this scenario, what probability does each player have of winning?

Solution
Reveal

Player C should skip their turn, then player B should challenge A. If player B doesn't make the shot, then player A should challenge player B and thereby knock them out. Either way, there should then be two players left, and each should challenge the other at every opportunity.

The probabilities of players A, B, and C winning are, respectively, 35%, $\sim$27%, and $\sim$38%. (The exact probabilities are 7/20, 7/26, and 99/260.)

When there are only two players left, it's clear they should challenge each other at every opportunity, since they only give up a chance at winning by skipping. Once there are two players left, if the first player to challenge has probability $p_1$ of making each shot and the second player to challenge has probability $p_2$ of making each shot, then the probability of the first player winning is $p_1 + (1-p_1)(1-p_2)p_1 + (1-p_1)(1-p_2)(1-p_1)(1-p_2)p_1 + \cdots = \frac{p_1}{1 - (1-p_1)(1-p_2)} = \frac{p_1}{p_1 + p_2 - p_1p_2}.$

When player B challenges player A, they make their shot with probability $0.5.$ In this scenario, we have $p_1 = 0.3$ and $p_2 = 0.5,$ so player C wins with probability $0.3/(0.3 + 0.5 - 0.3 \cdot 0.5) = 6/13$ and player B wins with probability $1 - 6/13 = 7/13.$ In the alternate scenario where player B doesn't make their first shot, A knocks player B out of the game. Then, player C gets one shot to win, winning with probability $0.3$ and losing with probability $0.7.$

So, in aggregate, the probabilities of winning are as follows. Player A wins with probability $(0.5)(0.7) = 0.35.$ Player B wins with probability $(0.5)(7/13) = 7/26.$ Player C wins with probability $(0.5)(6/13) + (0.5)(0.3) = 3/13 + 3/20 = 99/260.$

The reason they follow this strategy is that any other strategy by a player gives them a lower probability of winning, as we'll now discuss.

If player B misses their first shot, player A could choose to skip their turn. However, this can't be the right strategy because if player A continually skips their turn in this scenario then player B will eventually succeed at knocking player A out.

If player B misses their first shot, player A could choose to challenge player C. However, if so, player B will challenge player A and win with probability $0.5.$ This gives player A a chance of winning of only $0.5,$ instead of the $0.7$ chance they have if they challenge player B. So, player A won't choose this option.

We see now that if player B misses their first shot, player A won't choose to skip their turn or challenge player C. So, we see why player A chooses to challenge player B in this scenario.

At player B's first opportunity, they could choose to challenge player C. However, if they do so and win, then player A will knock them out and they'll have no chance of winning. So, player B won't choose this option.

At player B's first opportunity, they could choose to skip their turn. However, if so, player A will knock player B out just as they would have if player B had missed their shot. So, player B won't choose this option as it reduces their probability of winning to zero.

Since player B won't choose to challenge player C or skip their turn at their first opportunity, we see why they challenge player A then.

At player C's first opportunity, they could challenge player A. But, if they win, player B and player C start alternating turns starting with player B. Thus, player B has probability of winning of $(0.5)/(0.5 + 0.3 - 0.5 \cdot 0.3) = 10/13$ and player C has a probability of winning of just $1 - 10/13 = 3/13.$ This is lower than player C's probability of winning calculated above, so they won't choose this option.

At player C's first opportunity, they could challenge player B. But, if they win, player A will immediately knock player C out and player C will have no chance of winning. So, player C won't choose this option.

Since player C won't choose to challenge player A or player B at their first opportunity, we see why they skip their turn. We've now worked our way back to the beginning of the game, so we see why the players follow the strategy outlined above.