Search Games: A Review - Search Theory: A Game Theoretic Perspective - page 13

radius D around O , walk towards 1 o'clock for 3 D units then, turn on the tangent
that strikes the circle at 2 o'clock. Follow the circle to 9 o' clock and continue on a
tangent for length D (until reaching the tangent to the circle at 12 o'clock). At that
time all the tangents of the circle with radius D have been visited. The length of this
minmax trajectory is about 6

. 4 D . However, this trajectory is not effective unless D

is known exactly.
An online framework for the general problem is presented in [ 24 ]. The goal is to
minimax the ratio between the distance travelled until reaching the shore (assumed
a straight line) and the unknown distance, D

,

to the shore. It has been suggested that
the solution could be an exponential spiral but the problem seems difficult and is
still open.

Acknowledgements The author would like to thank the Lorentz Center, the organizing committee
of the workshop on Search and Rendezvous, and especially Robbert Fokkink and Steve Alpern for
their help and support. The author is also obliged to Robbert Fokkink for his useful remarks which
led to a significantly improved version.

References

1. Alpern, S. (1974). The search game with mobile hider on the circle. Pp. 181-200 in Roxin,
EO, Liu, PT and Sternberg, RL, eds. Differential Games and Control Theory. Dekker, New
Yo r k .
2. Alpern, S. (2008). Hide-and-seek games on a tree to which Eulerian networks are attached.
Networks 52(3):109-178.
3. Alpern, S. and Gal, S. (1988). A mixed strategy minimax theorem without compactness. SIAM
J. Control Optim. 26:1357-1361.
4. Alpern, S. and Gal, S. (2003). The theory of search games and rendezvous . Springer.
5. Alpern, S., Baston, V, and Gal, S. (2008). Network search games with immobile hider, without
a designated searcher starting point. International Journal of Game Theory 37:281-302.
6. Alpern, S., Fokkink, R., Lindelauf, R. and Olsder, GJ. (2008). The Princess and Monster game
on an interval. SIAM Journal on Control and Optimization. (47):1178-1190.
7. Anderson, EJ. and Aramendia, MA. (1990). The search game on a network with immobile
hider. Networks. 20(7):817-844.
8. Baeza-Yates, R. A., Culberson, J. C. and Rawlins, G. J. E. (1993). Searching in the plane. Inf.
Comput. 106(2):234-252.
9. Bellman, R. (1956). Minimization problem. Bull. Am. Math. Soc. 62:270.
10. Bellman, R. (1963). An optimal search problem. SIAM Rev. 5:274.
11. Beck, A. (1964). On the linear search Problem. Israel J. Mathematics. 2:221-228.
12. Beck, A. (1965). More on the linear search problem. Israel J. Mathematics. 3:61-70.
13. Beck, A. and Beck, M. (1986). The linear search problem rides again. Israel J. Mathematics.
53(3):365-372.
14. Beck, A. and Newman, DJ. (1970). Yet More on the linear search problem. Israel J. Mathe-
matics. 8:419-429.
15. Borodin A. and El-Yaniv, R. (1998). Online Computation and Competitive Analysis. Cam-
bridge University Press.

16. Bruce, TF. and Robertson, JB. (1988). A survey of the linear-search problem. Math. Sci. 13:

75-89.

17. Chrobak M. and Kenyon-Mathieu, C. (2006). Competitiveness via doubling. SIGACT News.

37(4):115-126.