3
$\begingroup$

First of all, I want to state that I'm not an expert in the game theory and searching the references for the game I just made up. Solving this game by itself seems like a decent project for strong highschool / undergrad students and I would like to suggest it to some people, but I'm not sure whether anything is known about it already and need to familiarize with the topic.

The game is a zero-sum probabilistic game with two players: runner and catcher.

Runner moves in some space, say a line or a plane with limited speed $v$ and arbitrary direction.

Catcher knows the exact position of a runner. Once catcher can declare some circle of radius $R$, and after the time $t$ passes, if the runner is in the circle, the catcher wins. Otherwise, runner wins.

Runner doesn't know the declaration moment.

We also state that if for $T >> t$ catcher does not declare anything, runner wins automatically (but I think that runner's behavior should actually have some limit for $T \rightarrow \infty$).


I've tried to tackle the problem for the following discrete model: the time is discrete, runner moves 1 step left or right each turn, catcher declares 1 possible position, $t = 2$ turns. Then, there is a strategy for a runner which allows to escape with probability $\frac{\sqrt{5} - 1}{2} \approx 0.62$ independent on a catcher behavior. I believe it is optimal but didn't prove it fully. Note that escape with probability $> \frac{2}{3} \approx 0.66$ is not possible due to the following catcher strategy: choose $3$ possible positions of a runner on a second turn with equal probability.

Note also that the symmetric random walk allows the escape with probability $\frac{1}{2}$ which is much worse.


Does anybody know something about this game or any possible references?

$\endgroup$

1 Answer 1

7
$\begingroup$

The discrete approximation problem you mention was proposed by Isaacs, and solved independently by Dubins [1] and Karlin [2]. These papers show that the runner has a unique optimal strategy which depends on the previous move only and yields escape probability $p=\frac{\sqrt{5} - 1}{2}$. Conversely, for every $\epsilon>0$, the catcher has a strategy that succeeds with probability at least $1-p-\epsilon=(3-\sqrt{5})/2 -\epsilon$. However, the catcher does not have an optimal strategy. A generalization is described in [3]. This problem is related to Pursuit-Evasion type game on graph ("Flyswatter game") Isaacs' original motivation involved continuum games of the type you describe, which are considered in the theory of differential games.

[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

$\endgroup$
1
  • $\begingroup$ Thank you for a detailed answer. I supposed differential games were ought to somehow meet this problem but hadn't find it by myself. $\endgroup$ Oct 10, 2019 at 5:14

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .