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$
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$
  • $\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$ – Lev Soukhanov Oct 10 '19 at 5:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.