Rendezvous search on the line with more than two players

Abstract

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 for 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 Rn,m s; otherwise the asymmetric value Rn,m a. We show that R3,2 a = 47/48, and that Rn,ns, is asymptotic to n/2. These results respectively extend those for two players given by Alpern and Gal (1995) and Anderson and Essegaier (1995). © 1997 INFORMS.