Ten Open Problems in Rendezvous Search - Search Theory: A Game Theoretic Perspective - page 217

10. When to give up: rendezvous with failure. As stated in the Introduction,
what distinguishes rendezvous search from Schelling's coordination prob-
lems is that the search continues until coordination (meeting) is achieved.
However it is common that when two people agree to meet in a large area,
one or more may eventually give up, assuming the other didn't come to the
area. Similarly, searches for missing people are eventually terminated.

There are two ways we could incorporate giving up the search: we could keep
the classical formulations but change the cost function; or we could put in new
ingredients to the problem. For the former, we could postulate a cost function
c where c is an increasing convex function of search time T and C

is a cost of failure that is incurred if the search is terminated at a time T with-
out meeting (in this case f

( T )+ f · C ,

0). Or we could have a value of
meeting which decays exponentially, while the cost is still the search time T

= 1; otherwise f =

.
The later version involves changing the ground rules of the rendezvous problem
itself. We could have a given probability that each player simply does not turn
up to the game. Or this could be implicit: for example the initial distribution of
the players could be uniform on the union of disjoint complete graphs of size 8
and 2 Presumably one would start off in the hope that the other is in the same

component and play optimally within your component. At some point (earlier
if you are in the small component), you have a sufficiently low updated prob-
ability that rendezvous is possible, and you would stop. If the players stop at
different times it is not clear how to allocate costs to search times.

.

14.3 Further Comments

For more results in the field of the operations research aspects of rendezvous, see
the monograph of the author and S. Gal [ 12 ] and the survey of the author [ 5 ]. For a
broader approach to search games and search problems, see the monograph of Stone
[ 33 ] and the survey of Benkoski, Monticino and Weisinger [ 18 ].

References

1. Alpern, S. Hide an seek games. Seminar, Institut fur Hohere Studien, Vienna, 26 July 1976.

2. Alpern, S. The rendezvous search problem. LSE CDAM Research Report 1993 53, London

School of Economics.

3. Alpern, S. The rendezvous search problem. SIAM J. Control & Optimization 1995;

33 :673-683.

4. Alpern, S. Asymmetric rendezvous search on the circle. Dynamics and Control 2000;

10 :33-45