Rendezvous Problem - Search Theory: A Game Theoretic Perspective - page 161

Telephone Problem In each of two rooms, there are n telephones randomly
strewn about. They are connected in a pairwise fashion by n wires. At discrete
times t

players in each room pick up a phone and say “hello”.They
wish to minimize the time T when they first pick up paired phones and can
communicate. What common randomization procedure should they adopt for
choosing the order in which they pick up the phones?

= 0 , 1 , 2 ,...

The field was later popularised by Anderson and Weber in their seminal paper [ 7 ]
on discrete location rendezvous. The continuous formalisation of the problem was
later given by Alpern in [ 1 ]. Since then, the field grew substantially and attracted
interest of researchers from a number of fields including Mathematics, Opera-
tions Research and Computer Science. A comprehensive collection of rendezvous
problems including their rigorous classification can be found in the second part
(Rendezvous Theory) of the topic [ 4 ] from Alpern and Gal.
In general, Computer Science (CS) and Operations Research (OR) communi-
ties tend to study different models and aspects of the rendezvous problem. While
OR research focuses mainly on minimisation of the expected time to meet, and
sometimes maximisation of the probability of meeting within a given time, CS
community tends to study efficiency trade-offs based on the use of resources.
Despite differences, both communities expressed strong interest in rendezvous on a
(possibly infinite) line. A number of randomised as well as deterministic rendezvous
strategies have been proposed and analysed in this environment.
Alpern in [ 1 ] introduced the symmetric rendezvous search problem on the line
and proposed a strategy with the expected meeting time of 5 d ,where d is known
and it refers to the original distance between the agents. Alpern's idea was to it-
erate for as long as it is needed the following procedure. Pick a random direction
and move distance d in this direction and later distance 2 d in the opposite direc-
tion, all at speed one. In addition, Alpern and Gal in [ 3 ] gave the proof that all
symmetric strategies have expected time of rendezvous at least 3

. · .

25 d Also in

. ·

1995, Anderson and Essegaier in [ 6 ] improved the upper bound to 4 d using

a novel idea of mixed movements. Baston in [ 9 ] further improved the upper bound
to 4

5678

d by accumulating and using all information before rendezvous takes
place. More recently Uthaisombut in [ 30 ] presented tuned up mixed strategy im-
posing a better upper bound of 4

. 4182 ·

. 3931 · d . He also provided argument for the lower

bound 3 . 9546 · d . These two bounds were further improved by Han et al. in [ 20 ]to

4 d respectively. These two results required strong reference to

Markov chains, fractional quadratic programming and semidefinite programming.
The authors also conjectured that the rendezvous value is asymptotically equal to
4

. 2574 · d and 4 . 1520 ·

.
The case when the distance d is not known in advance have been discussed in [ 10 ]
where the competitive ratios (that compares efficiency of the proposed strategy to
the best possible solution) 17

. 25 · d

. 686 for the total distance traveled and 24 . 843 for the

total time are established.