Rendezvous Search on the Line with More Than Two Players

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.).