Search Games for an Immobile Hider - Search Theory: A Game Theoretic Perspective - page 21

once), Isaac's result holds and the value of the game is 2. The searcher can simply

choose the Eulerian path with probability 1/2 and its reverse with probability 1/2;
the hider can hide uniformly on the network. The networks that have an Eulerian
path include the 3 arc network in Fig. 1.1 , whose solution in Gal's classic model
was so elusive. For the arbitrary start model, the value of this game is

μ /

2.
Just as we define Chinese Postman Tours, we can define a Chinese Postman Path
of a network Q as a minimal time path that visits all the points of Q . We can then
define ˜

μ / 2 = 3 /

as the length of a Chinese Postman Path, and we obtain a result analgous
to ( 2.1 ) for the value V of the Search Game played on networks with an arbitrary
starting point:

μ

μ / 2 ≤ V ≤ μ / ˜ 2 . (2.2)

The arbitrary start model was further studied in [ 3 ] in which the authors call a
network simply searchable if the upper bound on V in ( 2.2 ) is tight. They give suffi-
cient conditions for a network to be simply searchable, and in particular they show
that trees are simply searchable and that the hider should use the EBD distribution,
with respect to a root located at the center of the tree: that is the point c whose great-
est distance from any other point in the tree is minimal. For example, in Fig. 2.1 the
center c is located halfway between nodes O and D . If we add a node at c ,thenat
this point there are two branches of lengths 7/2 and 11/2, which the hider chooses
with probabilities proportional to 7 and 11, respectively. Hence the hider chooses
the node C with probability 7/18 and nodes A and B with total probability 11/18.

2.6 Other Search Game Models

Recently some alternative models of search games on networks have been proposed.
In the models we have discussed so far the searcher's strategy space is a set of unit
speed paths. However we might consider associated games in which the searcher
has a different strategy set.
In [ 2 ] Alpern defines a new model called find-and-fetch in which he considers a
searcher who not only wishes to find a hider but also wishes to return to the root O .
This models common problems such as search-and-rescue and foraging problems
in which an animal must find food and then return to its lair. As in Gal's model, the
searcher follows a unit speed path from O , but then upon reaching the hider takes
the shortest path back to O at speed

. The payoff is the total time to find the hider
and return to O . In the case of a bird being weighed down by food he is taking back
to his nest we might have

ρ

1 might be more appropriate for the
case of someone searching for a contact lens, in which the return speed would be
quicker.
Alpern finds that if Q is a tree, the optimal strategy for the hider is still the EBD
distribution in this game. However, the RCPT is no longer optimal for the searcher.
Instead, he randomizes between all possible depth-first searches using a type of
strategy called a branching strategy. Upon reaching a node for the first time the
searcher chooses which outward branch to take according to a certain probability.
Alpern proves the following.

ρ < 1, whilst ρ >