A rendezvous-evasion game on discrete locations with joint randomization

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 Probability 28, pp. 839-851). A1, 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 S wins under optimal play. We assume that R1 and R2 can jointly randomize their strategies. When n equals 3, the value of the game is 47/76 ≈ 0.61842. We also prove that the value of the game is bounded above by 1 - e-1 (≈0.632121) asymptotically. If, in addition, the players share a common notion of a directed cycle containing all the n locations (while still able to move between any two locations), the value of the game is ((1 -2/n)n-1 + 1)/2. Finally, we prove that with this extra information, R can secure a strictly lower value for all n.