Centre for Discrete and Applicable Mathematics |
|
CDAM Research Report, LSE-CDAM-2006-03March 2006 |
Network Search Games With Immobile Hider, Without a Designated Searcher Starting Point
Steve Alpern, Vic Baston and Shmuel Gal
In the (zero-sum) search game Z(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 Z(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 Z(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.
A PDF file (163 kB) with the full contents of this report can be downloaded by clicking here.
Alternatively, if you would like to get a free hard copy of this report, please send the number of this report, LSE-CDAM-2006-03, together with your name and postal address to:
CDAM Research Reports Series Centre for Discrete and Applicable Mathematics London School of Economics Houghton Street London WC2A 2AE, U.K. |
||
Phone: +44(0)-20-7955 7494. Fax: +44(0)-20-7955 6877. Email: info@maths.lse.ac.uk |
Introduction to the CDAM Research Report Series. | ||
CDAM Homepage. |