The symmetric rendezvous-evasion game

Abstract

E. J. Anderson and R. R. Weber, J. Appl. Probab., 28 (1990), pp. 839-851, considered the problem of two rendezvousers, R1,R2. randomly placed among n indistinguishable locations, who seek to meet in least expected time, using the same mixed strategy. We retain their dynamics but modify the rendezvousers' aim to meeting each other before either encounters an enemy searcher S. We solve this zero-sum game in minimal space (3 locations) and time (2 steps after placement), and find that optimal play requires that the rendezvous team use a mixture over behavioral strategies. While such complicated strategies are known to be necessary in principal for team games (the theory of Isbell and Alpern), we believe this is the first naturally occuring game where such a solution is derived. (An earlier paper by Lim solved a similar game in which R1 and R2 were allowed to use different strategies and joint randomization.).