We consider a problem proposed by S. Alpern 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. 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 relocate 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.
