Abstract
In the (zero-sum) search game Γ(G, x) proposed by Isaacs, the Hider picks a point H in the network G and the Searcher picks a unit speed path S(t) in G with S(0) = x. The payoff to the maximizing Hider is the time T = T(S, H) = min{t : S(t) = H} required for the Searcher to find the Hider. An extensive theory of such games has been developed in the literature. This paper considers the related games Γ(G), where the requirement S(0) = x is dropped, and the Searcher is allowed to choose his starting point. This game has been solved by Dagan and Gal for the important case where G is a tree, and by Alpern for trees with Eulerian networks attached. Here, we extend those results to a wider class of networks, employing theory initiated by Reijnierse and Potters and completed by Gal, for the fixed-start games Γ(G, x). Our results may be more easily interpreted as determining the best worst-case method of searching a network from an arbitrary starting point.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Alpern S (1974) The search game with mobile hider on the circle. In: Roxin EO, Liu PT, Sternberg RL(eds) Differential games and control theory. M. Dekker, New York, pp 181–200
Alpern S (2008) Hide-and-seek games on a tree to which Eulerian networks are attached. Networks (in press)
Alpern S, Asic M (1985) The search value of a network. Networks 15(2): 229–238
Alpern S, Gal S (2003) The theory of search games and rendezvous. Kluwer International Series in Operations Research and Management Sciences. Kluwer, Boston, p 319
Alpern S, Howard JV (2000) Alternating search at two locations. Dyn Control 10: 319–339
Anderson EJ, Aramendia MA (1990) The search game on a network with immobile hider. Networks 20(7): 817–844
Beck A, Newman DJ (1970) Yet more on the linear search problem. Nav Res Logist 8: 419–429
Dagan A (2005) Strategies for searching graphs with an arbitrary starting point, MSc Thesis, University of Haifa
Dagan A, Gal S (2008) Network search games with arbitrary searcher starting point. Networks (in press)
Demaine E, Fekete S, Gal S (2006) Online searching with turn cost. Theor Comput Sci 361: 342–355
Dvir D, Handler GY (2004) The absolute center of a network. Networks 43(2): 109–118
Edmonds J, Johnson EL (1973) Matching Euler tours and the Chinese postman problem. Math Program 5: 88–124
Eiselt HA, Gendreau M, Laporte G (1995) Arc routing problems I. The Chinese postman problem. Oper Res 43: 231–242
Gal S (1980) Search games. Academic Press, New York
Gal S (2000) On the optimality of a simple strategy for searching graphs. Int J Game Theory 29: 533–542
Garnaev AY (2000) Search games and other applications of game theory. Springer, Berlin
Hakimi S (1964) Optimal locations of switching centers and medians of a graph. Oper Res 12: 450–459
Hassin R, Tamir A (1995) On the minimum diameter spanning tree problem. Inf Process Lett 53: 109–111
Isaacs R (1965) Differential games. Wiley, New York
Kikuta K (1995) A search game with traveling cost on a tree. J Oper Res Soc Jpn 38(1): 70–88
Megiddo N, Tamir A (1983) New results on the complexity of p-center problems. SIAM J Comput 12(4): 751–758
Pavlovic L (1995) A search game on the union of graphs with immobile hider. Nav Res Logist 42(8): 1177–1189
Reijnierse JH, Potters JAM (1993) Search games with immobile hider. Int J Game Theory 21: 385–394
Ruckle WH (1983) Geometric games and their applications. Pitman, Boston
von Stengel B, Werchner R (1997) Complexity of searching an immobile hider in a graph. Discrete Appl Math 78: 235–249
Zeliken MI (1972) On a differential game with incomplete information. Sov Math Dokl 13: 228–231
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Alpern, S., Baston, V. & Gal, S. Network search games with immobile hider, without a designated searcher starting point. Int J Game Theory 37, 281–302 (2008). https://doi.org/10.1007/s00182-008-0116-7
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00182-008-0116-7