Rendezvous Search on the Line with More Than Two Players
Wei Shi Lim, Steve Alpern, Anatole Beck · Operations Research · 1997
Suppose n blind, speed one, players are placed by a random permutation onto the integers 1 to n, and each is pointed randomly to the right or left. What is the least expected time required form m ≤ n of them to meet together at a single point? If they must all use the same strategy we call this time the symmetric rendezvous value R n,m s ; otherwise the asymmetric value R n,m a . We show that R 3,2 a = 47/48, and that R n,n s is asymptotic to n/2. These results respectively extend those for two players given by Alpern and Gal (Alpern, S., S. Gal. 1995. Rendezvous search on the line with distinguishable players. SIAM J. Control Optim. 33 1270–1276.) and Anderson and Essegaier (Anderson, E. J., S. Essegaier. 1995. Rendezvous search on the line with indistinguishable players. SIAM J. Control Optim. 33 1637–1642.).