# Pursuit-Evasion type game on graph (“Flyswatter game”)

An instance of the "flyswatter game" is defined by a graph $G$ and positive integer $k$. There are two players, A (the 'fly') and B (the 'swatter'). Essentially, the fly moves around $G$ and the swatter tries to guess where the fly will be $k$ steps in the future.

Formally, the game is played in two stages:

(1) Player A chooses an infinite walk $w_1, w_2, \dots$ on $G$ (but player B doesn't see it).

(2) Player B goes through the walk one step at a time. At step $t$ (having already observed $w_1, w_2, \dots, w_t$) he gets to either go to step $t+1$ (revealing $w_{t+1}$) or he can 'swat' by picking a vertex $v$ (which ends the game -- so he can only do it once). Player B is allowed to observe as many steps of the walk as he wants before swatting.

Player B wins if and only if $w_{t+k} = v$, where $t$ is the step where he decided to swat $v$ (i.e. the fly gets hit).

Even simple examples (e.g. $G$ is a 3-cycle, $k = 2$) give interesting behavior. I'd be surprised if nobody has ever studied this game, but I can't find it anywhere. Has anyone seen this before?

EDIT: As per Kaveh's suggestion (on the CSTheory copy -- now deleted), here's a bit of background about this.

I'm interested in this question as a simplification of a continuous problem about finding a maximally unpredictable random process for generating a path on the real line (for a particular measure of unpredictability). Thus, one thing I'd like to know in particular is an optimal strategy for the fly on the integer line (which can be simulated by using a cycle of size $2k + 1$ instead).

What I've proven:

Let $p_A(G, k)$ be the probability of winning for player A. Then (for any $G$) $k_1 < k_2$ implies that $p_A(G, k_1) \leq p_A(G, k_2)$ (player A prefers larger $k$).

If $G$ has $n$ vertices, $p_A(G, k) \leq \frac{n-1}{n}$ (this is trivial, as player B can simply guess a random vertex).

What I strongly suspect to be true (not yet proven):

There is always an optimal strategy for player A which generates the walk using an order-$k$ Markov chain.

If $k = 1$, the optimal strategy for player A is to find the subgraph $G^*$ of $G$ which has largest minimum degree (there is a poly-time algorithm to find this), and then do a random walk on $G^*$.

An interesting case: $C_3$ with $k = 2$.

The best strategy I've found so far for A to generate his walk is:

1. begin at any vertex; at first move, move CW or CCW with probability $1/2$ each.

2. for all subsequent moves, with probability $\frac{\sqrt{5} - 1}{2}$ repeat the previous move (CW or CCW); otherwise switch.

This gives player B a winning probability of $1 - \frac{\sqrt{5} - 1}{2} \approx 0.382$ (the probability for A to be back where he started after 2 moves, or to have moved twice in the same direction as his previous move).

• Note that it's not obvious that these games have well-defined values. $\;$ – user5810 Nov 10 '15 at 19:49
• The game is interesting, but not so much at $k=2$ if $G$ is a cycle: the value in that case is $1$ if $G$ is a 2-cycle (of course), $\frac12$ if $G$ is a 4-cycle, and $\frac13$ otherwise. The first non-trivial case I come across for $k=2$ is when $G$ is a line of six vertices and the starting vertex is one of the middle two. – Mark Fischler Nov 11 '15 at 0:01
• @ Mark: I'd be curious to see the $\frac{1}{3}$ strategy for player A (the best I've found so far produces a probability of winning for player B of $1 - \frac{\sqrt{5} - 1}{2}$). I'd be surprised if there was a way to generate a random walk on $K_3$ (for instance) such that the marginal distribution over the 3 vertices at a 2-move horizon is always $\frac{1}{3}$ for each. – minderbinder8 Nov 11 '15 at 1:33
• @DavidSpeyer : $\;\;\;$ Your calculation only works when the swatter has no information about $q_n$, but in your strategy, $q_{n-1}$ gives the swatter information about $q_n$. $\:$ Furthermore, I found a strategy for the swatter that wins with probability greater than 1/3 on all cycles. $\;\;\;\;\;\;\;\;$ – user5810 Nov 11 '15 at 18:02
• minderbinder and @RickyDemmer are right; there appears to be no solution that achieves a value of 1/3 on a cyclic graph, because there likely is no Markov process that moves to each of the three possible 2-step vertices with probability 1/3 at every step. BTW mindbender, I think this problem is more appropriate here than in the CS stack exchange, so I would vote for putting it on hold there instead of here. – Mark Fischler Nov 11 '15 at 22:30

When the graph is just the integer lattice ${\bf Z}$, this problem was proposed by Isaacs, and solved independently by Dubins [1] and Karlin [2].

To paraphrase Math reviews, [1] and [2] deal with the following game: At each unit of time, the Evader may move either one unit of distance to the left or one to the right. The Pursuer, knowing the past moves of the Evader, has one move—he predicts two units of time in advance the position of the Evader. The payoff to the Pursuer is 1 if he predicts correctly; otherwise it is zero. Then [1], [2] show that this game has the value $(3-\sqrt{5})/2$ and that the Evader has a unique optimal strategy which depends on the previous move only. However, the Pursuer does not have an optimal strategy.

Of course the value on ${\bf Z}$ is an upper bound for the value the game on any cycle. Extensions to some other graphs are in Ferguson [3].

An asymptotic version of the problem is considered in [4]. In that paper, given $\alpha\in (1/2,1)$, a nearest-neighbor process $\{S_n\}$ on the integers that is less predictable than simple random walk is constructed, in the sense that given the process until time $n$, the conditional probability that $S_{n+k}=x$ is uniformly bounded above by $Ck^{-\alpha}$ for some constant $C<\infty$. Such a process does not exist for $\alpha=1$; the exact predictability profiles possible were determined in [5] and [6].

[1] Dubins, L. E. A discrete evasion game. Contributions to the theory of games, Vol. 3, pp. 231–255; Ann. of Math. Studies, No. 39, Princeton Univ. Press, Princeton, N.J., 1957.

[2] Karlin, Samuel An infinite move game with a lag. Contributions to the theory of games, vol. 3, pp. 257–272. Annals of Mathematics Studies, no. 39. Princeton University Press, Princeton, N. J., 1957 \newline

[3] Ferguson, Thomas S. On discrete evasion games with a two-move information lag. 1967 Proc. Fifth Berkeley Sympos. Math. Statist. and Probability (Berkeley, Calif., 1965/66), Vol. I: Statistics pp. 453–462 Univ. California Press, Berkeley, Calif. \newline

[4] Benjamini, Itai ; Pemantle, Robin ; Peres, Yuval. Unpredictable paths and percolation.
Ann. Probab. 26 (1998), no. 3, 1198–1211.

[5] Häggström, Olle; Mossel, Elchanan Nearest-neighbor walks with low predictability profile and percolation in 2+ϵ dimensions. Ann. Probab. 26 (1998), no. 3, 1212–1231.

[6] Hoffman, Christopher Unpredictable nearest neighbor processes. Ann. Probab. 26 (1998), no. 4, 1781–1787.

• Awesome, thanks! Admittedly, I'd started to get my hopes up that this was really a novel problem -- it's funny to see that it was known since the '50s! To follow up: do you know of any work on this problem in a continuous setting, e.g. that the evader is moving on $\mathbb{R}$ (with top speed 1) and the pursuer wins if his guess is off by a distance of at most 1? – minderbinder8 Nov 30 '15 at 13:14
• Such continuous problems are studied in "Differential games", a topic first developed by Isaacs, who wrote a book on it. The problem above was invented by Isaacs as an approximation to the continuous case, but I have not searched for explicit analysis of the continuous problem. – Yuval Peres Dec 2 '15 at 18:41

Strategy to have more than a 1/3 chance of hitting the fly:

The origin is the vertex the fly starts on. ​ For 1-cycles and 2-cycles,
the swatter wins with certainty by immediately swatting the origin.
For larger cycles, the following strategy gives the swatter at least a 5/14 chance of winning:

Note that cycles with more than 2 vertices, one can make sense of "continue in the same direction".
With probability

2/14 ​ ​ ​ ​ immediately swat the origin
3/14 ​ ​ ​ ​ at t=1, swat its current location
3/14 ​ ​ ​ ​ at t=1, swat 2 further in the direction it moved

​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ at t=2,
​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ if it backtracked then choose [the origin or the vertex
6/14 ​ ​ ​ ​ 2 further in the direction it just moved] with equal probability
​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ else choose [one of the three vertices it can be at in 2 more moves] with equal probability
​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ swat the chosen vertex

.

I found that by manually carrying out quantifier elimination in the ordered group Q.
If I managed it correctly, then for cycles with more than 4 vertices (i.e., "large" cycles, since k=2),
the strategy I gave will be the swatter's unique best for when the swatter can't wait till after t=2.
(Presumably, a more patient swatter could do better than that.)

• Great, thanks. I like the idea of an "impatient swatter" (I guess it's a very natural thing to assume) who must swat by some given time $T$. Defining $p_B(G, k, T)$ as the probability of the impatient swatter winning and $p_B(G, k, \infty)$ as the probability of the original swatter winning, it should be the case that $\lim_{T \to \infty} p_B(G, k, T) = p_B(G, k, \infty)$, right? – minderbinder8 Nov 12 '15 at 16:12
• Yes, that ought to be true. ​ ​ ​ Another modifications one could make is considering the discounted version, in which [a real number r such that ​ 0 < r < 1 ] ​ is given and if the swatter hits the fly at time t then the swatter scores $r^{\hspace{.02 in}t}$ else the swatter scores 0. ​ ​ ​ ​ ​ ​ ​ ​ ​ – user5810 Nov 12 '15 at 17:02