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:

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

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

always$\frac{1}{3}$ for each. $\endgroup$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. $\endgroup$2more comments