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 his 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 his 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 him 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, he makes his 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 his 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 him a lower probability of winning, as we'll now discuss.

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

If player B misses his 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 he has if he challenges player B. So, player A won't choose this option.

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

At player B's first opportunity, he could choose to challenge player C. However, if he does so and wins, then player A will knock him out and player B will have no chance of winning. So, player B won't choose this option.

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

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

At player C's first opportunity, he could challenge player A. But, if he wins, 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 he won't choose this option.

At player C's first opportunity, he could challenge player B. But, if he wins, 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 his first opportunity, we see why he skips his 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.