Part I

This was originally asked by Jane Street as one of their monthly puzzles1 back in October of 20212. I will paste their description of the problem:

In the Robot Swimming Trials, 3N identical robots compete for N equivalent spots in the finals by swimming N races. Each robot precommits to spending a certain amount of its fuel in each race. After all the races are run, the spots in the finals are given to the winners of the races, moving from the fastest winner to the slowest. (Once a robot wins a race, it is ineligible to win another race.) A robot’s speed is strictly increasing in the amount of fuel it spends, and ties are broken by randomly choosing the winner among the robots that have spent the same amount of fuel.

Mathematically speaking, the 3N robots each submit a strategy, which is an N-tuple of nonnegative real number “bids” summing to 1, representing the fuel burned in each of the N races. The winners of the races are then determined from the highest bid (across all races and all robots) on down, with ties broken randomly. Once a robot wins a race their other bids are deleted, so we are guaranteed to get N distinct qualifiers for the finals.

For example, suppose N=3 and the 3N=9 robots submit their strategies as

Robot Race 1 Race 2 Race 3

Automatonya 0.6 0.1 0.3

Botty 0.6 0.3 0.1

Chroma 0 1 0

Data 0.3 0.5 0.2

Electro 0.2 0.8 0

Fernandroid 0.4 0.5 0.1

Gregulator 0.5 0.5 0

Hannanobot 0 0.9 0.1

IO 0.2 0.7 0.1

The second race gets resolved first because Chroma’s bid of 1 is the highest overall, and Chroma is declared the winner of that time trial. Next, the first race is resolved because 0.6 is the highest remaining bid (we ignore the 0.9, 0.8, and 0.7 in the second race because it already has a winner). We flip a fair coin to determine who is the winner between Automatonya and Botty; say that Automatonya gets lucky and is declared the winner. Then the third race is decided, and Data is declared the winner, because 0.2 is the highest bid among robots that have not yet won (Automatonya’s 0.3 is ignored).

Over the storied history of the RST, the metagame settled into what was widely believed to be the Nash equilibrium: each robot uniformly randomly selects a race and devotes all of their fuel to it. Let’s call this the discrete strategy. However, rumors are circulating that this conventional wisdom is not entirely accurate: for a large enough N, the discrete strategy is not the Nash equilibrium. You’ve been tasked to find two pieces of information:

What is the smallest N for which the trial does not have the discrete strategy as the Nash equilibrium?

For this N, if the other 3N-1 robots naively play the discrete strategy and your robot plays optimally (exploiting this knowledge of your opponents’ strategies), with what probability p will you make the finals (rounded to 6 significant digits)?

Part I Solution

If every other of the 3N-1 robots is playing discrete and we play with some amount less than discrete spread throughout the races, then our only chance of winning would be when not a single robot randomly selects one (or more) of the races to allot their fuel to. We therefor will evenly spread out our fuel among all races. (Technically it wouldn’t matter if we don’t evenly spread out our fuel among all races so long as some non zero amount is allotted to every race given that every other player is definitely playing the discrete strategy.)

For a given set of N races, we will calculate the probability that 3N-1 players have left one or more races ‘open’.

The probability that there are exactly k open races is given by (read more about Sterling numbers of the second kind3):

Therefore the probability that there is one or more open races is given by:

In a Nash Equilibrium in an a perfectly symmetric game, every player should have an equal probability of winning. Given that there are 3N players and N players move on, then every player should have the same 1/3 probability of moving on. We therefor are seeking the smallest value of N such that our probability is strictly greater than 1/3.

The smallest N for which this is true was found to be 8 with a probability of winning being approximately 33.4578%.

Part II

Jane Street released a second part to this puzzle in May of 20224.

We found (spoiler alert!) that inviting 24 robots to compete in 8 trial races (i.e. N=8) created a tournament in which the discrete strategy was no longer optimal. The tournament organizers adopted this tournament size, and viewers were rewarded with a richer set of strategies and more diverse race results (1). As expected, the competitors switched from everyone always using the discrete strategy to more subtle and continuous allotments of fuel. The metagame evolved and eventually settled into a Nash equilibrium in which a given competitor chooses the discrete strategy with a certain probability p, and otherwise elects for an allotment that distributes nonzero fuel to at least two races.

Find p, the probability a robot using the Nash equilibrium strategy when competing at a Robot Updated Swimming Trial with N=8 devotes all of its fuel to a single race, to 6 significant digits.

1. Also, many fewer extremely slow races in which all robots devoted zero fuel, and whichever robot’s random motion took it across the finish line first was declared the winner.

Part II Solution

Given that the optimal strategy has been let out, players will start to use it, but remember that that strategy was only an optimal pure strategy given that every other player was guaranteed to play the discrete strategy. We now need to find the optimal mixed strategy to use the discrete strategy such that we are indifferent (probability of winning is 1/3) regardless of which strategy we chose to use to arrive at the new Nash Equilibrium.

For a given mixed probability d of playing the discrete strategy and 1-d probability of playing the non discrete strategy, we will find our probability of winning when we play the non discrete strategy and find when this is equal to 1/3 indicating that we are at the Nash Equilibrium.

The probability that there are exactly n others using the non discrete strategy is given with a binomial distribution. If we are the only one using the non discrete strategy, then we are guaranteed to advance if there is one or more open races. With at least one more person playing the non discrete then we are only guaranteed if there are at least as many open races as people playing the non discrete strategy. If fewer races are open then the number of people playing then everyone playing the non discrete has equal probability of being selected at each.

We aim to sum over all possible combinations of players choosing discrete or non-discrete strategies, given that we are fixed on playing non-discrete. This sum is weighted by the probability of each combination occurring under a given mixed strategy and the probability of winning in one or more of the ‘open’ races in that scenario.

Solving for a d when this is equal to 1/3:

We therefor randomly play the discrete strategy with probability ~99.9560% in this new Nash Equilibrium.