A RENDEZVOUS-EVASION GAME ON DISCRETE LOCATIONS WITH JOINT RANDOMIZATION

We consider a problem proposed by S. Alpern (European Journal of Opera tional Research (1997)) of how two players can optimally rendezvous wh ile at the same time evading an enemy searcher. This problem can be mo delled as a two-person, zero-sum game between the rendezvous team R (w ith agents R-1, R-2) and the searcher S. This paper gives the first so lution to such a rendezvous-evasion game by considering a version that is discrete in time and space, as in the pure rendezvous problem of A nderson and Weber (Journal of Applied Probability 28, pp. 839-851). R- 1, R-2 and S start at different locations among the n identical locati ons where there is no common labelling and at each integer time they m ay rellocate to any one of the n locations. When some location is occu pied 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 w ins under optimal play. We assume that R, and R, can jointly randomize their strategies. When n equals 3, the value of the game is 47/76 app roximate to 0.61842. We also prove that the value of the game is bound ed above by 1 - e(-1) (approximate to 0.632121) asymptotically. If, in addition, the players share a common notion of a directed cycle conta ining all the n locations (while still able to move between any two lo cations), 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.