Blindfolded pursuit with delays of your choice
Computer Science and Game Theory
Summary
The authors study a game where one player (the pursuer) tries to catch another player (the evader) moving invisibly on a network of points connected by lines. The pursuer can control how long it takes to move between points and choose where to check for the evader each step. They show that by carefully picking travel times, the pursuer can always catch the evader in a reasonable amount of time on any network, even though the evader tries to avoid detection. This is different from situations where travel times are fixed, where more pursuers are needed as the network grows. If the evader can start earlier without the pursuer knowing, the pursuer can still catch them but might take much longer.
Authors
Torben Schürenberg, Maximilian J. Stahlberg
Abstract
We study pursuit-evasion games on graphs with a single pursuer and an invisible evader. The pursuer may assign integer travel times to the edges of the graph and specify a finite sequence of vertices to query, one per time step. The evader then chooses a walk over the same time horizon, aiming to elude all queries. With unit travel times, the setting in which the evader must move at every time step is known as the hunter and rabbit game, while the variant in which the evader can wait at a vertex can be phrased as a firefighting game: the vertices of a burning graph must be extinguished, and any vertex left burning reignites its neighbors. For both settings, we show that the power to choose travel times allows a single pursuer to succeed in polynomial time on any graph. This contrasts with unweighted graphs, where the number of hunters or firefighters needed can grow linearly in the number of vertices. If the evader, in addition to waiting, may start at an earlier time unknown to the pursuer, we show that the pursuer still wins on any graph given exponential time.