Network Search Games With Immobile Hider, Without a Designated Searcher Starting Point Centre for Discrete and Applicable Mathematics
Steve Alpern, V. J. Baston, Gal Shmuel · 2006
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 payo ¤ to the maximizing Hider is the time T = T (S; H) = min ft: S (t) = Hg required for the Searcher to …nd 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 …xed-start games (G; x): Our results may be more easily interpreted as determining the best worstcase method of searching a network from an arbitrary starting point.