RENDEZVOUS SEARCH ON THE LINE WITH INDISTINGUISHABLE PLAYERS

Alpern introduced a problem in which two players are placed on the real line at a distance drawn from a bounded distribution F known to both. They can move at maximum velocity one and wish to meet as soon as possible. Neither knows the direction of the other, nor do they have a common notion of a positive direction on the line. It is required to find the symmetric rendezvous value R(s)(F), which is the minimum expected meeting time achievable by players using the same mixed strategy. This corresponds to the case where the players are indistinguishable; they both take directions from a controller who does not know their names. In this paper we give a mixed strategy which has an expected meeting time of 1.78D + mu/2, where D is the maximum of F and mu its mean. This leads to an upper bound R(s)(F) less than or equal to 1.78D + mu/2 on the symmetric rendezvous value, which is better than the upper bound R(s)(F) less than or equal to 2D + mu/2 obtained by Alpern.