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

that is topologically homeomorphic to the three arc network depicted in Fig. 1.1 .
A weakly cyclic network is depicted on the left hand side of Fig. 1.2 ; the cycles are
indicated by the dotted lines.
Reijnierse and Potters give an algorithm to calculate the optimal hider distribu-
tion, in which the hider hides with some probability on leaf nodes and with some
probability hides uniformly on the cycles. Alpern and Gal [ 4 ] later give an alterna-
tive version of the algorithm, in which every cycle in the network is replaced with a
leaf arc of half the length of the cycle, and the EBD distribution is calculated on the
new network. The network depicted on the right hand side of Fig. 1.2 is the modi-
fication of the weakly cycle network on the left. The hider probability that should
be assigned to a cycle in the original network is then the probability assigned to the
end of the associated leaf arc in the new network (Fig. 2.2 ).

Fig. 2.2 A weakly cyclic network and its modifications

Reijnierse [ 16 ] later showed that the equivalent result holds if we replace 'weakly
cyclic' with 'weakly Eulerian'. A network is weakly Eulerian if it can be obtained
from a tree by replacing some nodes with Eulerian networks. Gal [ 12 ] found a sim-
ple proof of this result, showing not only that the value V of the game is ¯

2for
weakly Eulerian networks, but, as mentioned in Chap. 1 , these are the only networks
for which this is the value, and the RCPT is optimal. In summary,

μ /

Theorem 3 (Gal). The value of the search game with an immobile hider played on
anetworkQis ¯ μ / 2 if and only if Q is weakly Eulerian.

Notice that the class of weakly Eulerian networks includes both trees and Eule-
rian networks, so Theorem 3 generalizes Theorem 2 .

2.5 Search Games Without a Fixed Searcher Starting Point

In a recent paper [ 9 ] Dagan and Gal define a new Search Game model on a net-
work Q in which the assumption that the searcher has a fixed starting point O is
dropped, and the searcher can begin his search from any point on Q . This model has
already been discussed in Sect. 1.1.2 in Chap. 1 , where it was noted that provided the
searcher has some Eulerian path (one which visits every point of the network exactly