Article contents
A rendezvous-evasion game on discrete locations with joint randomization
Published online by Cambridge University Press: 01 July 2016
Abstract
We consider a problem proposed by S. Alpern (European Journal of Operational Research (1997)) of how two players can optimally rendezvous while at the same time evading an enemy searcher. This problem can be modelled as a two-person, zero-sum game between the rendezvous team R (with agents R1, R2) and the searcher S. This paper gives the first solution to such a rendezvous-evasion game by considering a version that is discrete in time and space, as in the pure rendezvous problem of Anderson and Weber (Journal of Applied Probability28, pp. 839–851). R1,R2 and S start at different locations among the n identical locations where there is no common labelling and at each integer time they may rellocate to any one of the n locations. When some location is occupied by more than one player, the game ends. If S is at this location, S (maximizer) wins and the payoff is 1; otherwise R(minimizer) wins and the payoff is 0. The value of the game is the probability that Swins under optimal play. We assume that R1 and R2 can jointly randomize their strategies. When n equals 3, the value of the game is . We also prove that the value of the game is bounded above by asymptotically. If, in addition, the players share a common notion of a directed cycle containing all the nlocations (while still able to move between any two locations), the value of the game is ((1 – 2/n)n–1 + l)/2. Finally, we prove that with this extra information, R can secure a strictly lower value for all n.
Keywords
MSC classification
- Type
- General Applied Probability
- Information
- Copyright
- Copyright © Probability Trust 1997
References
- 18
- Cited by