Bike Tour

You are the coach for Team Riddler at the Tour de FiveThirtyEight, where there are 20 teams (including yours). Your objective is to win the Team Time Trial race, which has the following rules:

• Each team rides as a group throughout the course at some fixed pace, specified by that team’s coach. Teams that can’t maintain their pace are said to have “cracked,” and don’t finish the course.
• The team that finishes the course with the fastest pace is declared the winner.
• Teams ride the course one at a time. After each team completes its attempt, the next team quickly consults with its coach (who assigns a pace) and then begins its ride. Coaches are aware of the results of all previous teams when choosing their own team’s pace.
• Assume that all teams are of equal ability: At any given pace, they have the exact same probability of cracking, and the faster the pace, the greater the probability of cracking. Teams’ chances of cracking are independent, and each team’s coach knows exactly what a team’s chances of cracking are for each pace.

Team Riddler is the first team to attempt the course. To maximize your chances of winning, what’s the probability that your team will finish the course? What’s the probability you’ll ultimately win?

Extra Credit: If Team Riddler is the last team to attempt the course (rather than the first), what are its chances of victory?

(fivethirtyeight)

Solution

If the first team’s coach chooses a pace with cracking probability $p$ (I will assume that there is a pace for every probability, and that in a tie the last finisher wins; this simplifies the math without sacrificing anything of interest about the problem), then in the worst-case scenario for that team, all of the other coaches will also choose $p$, yielding the highest possible probability of the first team losing. In that scenario, the first team has a winning probability of $(1-p)p^{19}$. This is maximized when $p$ is $19/20$, with a winning probability of only about $.0189$.

But how do we know that the other coaches will in fact choose $19/20$? Start with the last coach: they will certainly choose whatever the leading pace is at that point, because it’s the pace at which their team is most likely to win. The second-to-last coach, knowing this, would prefer to choose a probability $q$ that maximizes their winning probability $(1-q)q$. The value of $q$ that maximizes this is $1/2$, so this coach will select $1/2$, or, if the currently leading probability $p$ is greater than that, they will choose $p$ itself (the value of $(1-q)q$ monotonically decreases for $q$ greater than $1/2$). Knowing this, the third-to-last coach, for similar reasons, would prefer to choose $2/3$, which maximizes $(1-q)q^2$, but will choose the then-leading pace if it’s greater than that. And so on. So if the first coach chooses a cracking probability of $19/20$ and finishes, all of the remaining coaches will choose the same.

The Extra Credit asks for the last team’s winning probability. For generality, let’s ask for the winning probability for the $t$-from-last team (the last team counts as $0$ from last). The then-leading pace will be determined by the team, if any, that is first to finish. If it’s the first team, the pace will be $19/20$; if the second, $18/19$. And so on. If it’s the last team, the pace will be $0$ (which sounds weird, but since we’re labeling paces with their associated cracking probabilities, it just means no chance of cracking, not an actual velocity of $0$).

The probability that the $t$-from-last team wins is the sum, over the possible first-to-finish teams $i$, which can range from $t$ to $19$, of the probability that team $t$ wins and team $i$ sets the pace. The probability that $t$ wins and $i$ sets the pace is the product of three probabilities: the probability that all teams prior to $i$ fail to finish (this is the product of their ideal cracking probabilities $j/(j+1)$), the probability that teams $i$ and $t$ don’t crack at $i$’s ideal cracking probability ($(1- i/(i+1))^2$, or just $1-i/(i+1)$ if $i$ is $t$ itself), and the probability that no later team, from $t-1$ down to $0$, finishes at team $i$’s pace ($(i/(i+1))^t$).

So the overall probability that team $t$ will win is:

(My LaTeX not being up to the challenge, I’ve ignored in this formula that we don’t square the first term when $i=t$; I made the correct adjustment in performing the calculation.)

Here are the results:

So unfair!