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).



Pursuit-Evasion type game on graph ("Flyswatter game")
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.


