Graph pursuit games

Chasing Pokémon around a map is equivalent to one of the graph pursuit games mathematicians have studied since the 1970s. This game is played on an \(n\)-vertex graph \(G\) with (one or more) pursuers attempting to catch an evasive target. The pursuers and target occupy vertices in the graph and move along the edges; the game ends if and when any pursuer lands on the same vertex as the target.

The so-called “cops-and-robbers” game is a fascinating and accessible research with a deep open problem and enough prior work to fill a book. It’s known, for example, the exact conditions under which a lone pursuer can back the target into a corner and when the target can evade capture indefinitely.

Professor Elm ponders some results and conjectures about graph pursuit games.

Unfortunately for us, the Pokémon region of Johto does not form a “cop-win graph” — in theory, the roaming Pokémon could give us the run-around forever. Luckily, this isn’t the case in practice, as the legendary beasts don’t use a perfect evasive strategy.1 Instead, they appear to take a random walk independent of the player’s movements, and we can use techniques from probability theory and other branches of math to analyze the expected capture time under a given strategy.

The first place to start is the “greedy” strategy I originally tried as a kid: every time Raikou moves, check the map, and move to any route that gets me closer to them. After Raikou makes its random move, the distance between us could be unchanged (with Raikou’s move offsetting mine), or it could go down by one, or it could go down by two in the lucky \( \frac{1}{\Delta} \) chance that Raikou moves towards me. If I start at a distance of \(\ell\) steps away from Raikou and get lucky \(\frac{\ell}{2} \) times, I’ll have caught up — so using a negative binomial distribution bound,

$$ E[\text{capture time}] ≤ \frac{\Delta \ell}{2}$$

In the grand scheme of things, this isn’t too bad — especially if Δ is low. But it still takes a frustratingly large time for a 12-year-old, and in general it’s possible to do better.

Recently, Peter Winkler and Natasha Komarov found a strategy for general graphs which gives a better bound on the expected capture time. Somewhat counterintuitively, it involves aiming for where the robber was — rather than their current location — until the cop is very close to catching them. The Komarov-Winkler strategy has an expected capture time of \(n + o(n)\). This is essentially best possible on certain graphs, and beats the above \( \frac{\Delta \ell}{2} \) for large graphs with vertices of large degree.

For graphs without high-degree vertices — like the Pokémon world map — it is possible that a simpler solution could beat the Komarov-Winkler strategy. The problem is: simpler strategies may not be simpler to analyse. In her PhD thesis, Komarov wondered whether a greedy algorithm with random tiebreakers could guarantee \( n + o(n) \) expected capture time. It is an open question to find a general bound for the “randomly greedy” strategy’s expected performance that would prove her right.

  1. Fair enough; I’m sure they have better things to do than devoting their movements to avoiding a little kid. ↩︎