Robot Updated Swimming Trials
May 2022 : Puzzle
Back in October, we were tasked with the puzzle of finding the smallest number of robots we could invite to a Robot Swimming Trial in order to change the optimal strategy of participants away from discrete. Click here to see the original puzzle explanation and example; in the next paragraph we will go over a quick refresher on the setup.
The tournament directors choose a positive integer N, and then 3N robots are invited to compete in the trials, which are N races between all 3N robots. The robots commit to using a schedule of their identical fuel amounts to the N races, and on a given race whatever robot burns the most fuel wins (ties for most fuel spent on a given race are split uniformly randomly among the tying robots). All robots swim in all races according to their schedules, and then N distinct winners are determined, one from each race, by successively selecting the robot from the remaining races that spent the most fuel and finished ahead of all other robots that haven’t yet won a race. Robots all compete (i.e. choose their fuel allotment distributions to maximize the probability) to be selected for the finals by this method. The discrete strategy is the one in which a robot chooses a race uniformly randomly and assigns all of its fuel to that race, and zero fuel to the other races.
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 results1. 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.
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. ↩