Search Games: A Review - Search Theory: A Game Theoretic Perspective - page 6

1.1.3 The Hider Hides in a Node

Traditionally, the hider was allowed to hide anywhere in a graph, either in a node
or somewhere in an arc. The case in which the hider can hide in the nodes only, has
just recently been considered. In Chap. 3 of the topic, Zoroa et al. develop a theory
for such games, if the graph is an integer lattice. In general, it is natural to use the
Traveling Salesman Problem (TSP) Tour , i.e., the trajectory that starts at O , visits
all the nodes, and returns to O in minimal time. Finding the TSP tour is NP hard, in

contrast to the Chinese Postman tour which can be solved in O N 3 .

Definition 1. We say that the searcher uses the Random Traveling Salesman Strat-
egy (RTSP), if he equiprobably uses either the TSP tour or the 'reverse' tour. RTSP
guarantees an expected search time of at most half the tour length.

It is natural to ask if the RTSP strategy is optimal. It turns out that sometimes
it is, for example if the nodes are on a circle or for a tree. However, RTSP is not
always optimal, for if it would be, then it would also be optimal if the hider can
hide anywhere in the network. This is not the case. The optimal searcher strategy
for the three-arcs graph is much more complicated than RTSP. So if there are n

1
equally spaced nodes along each of the arcs of the three-arcs graph, then RTSP is not
optimal. One can show that RTSP need not even be optimal for an Eulerian graph,
e.g., by adding one more unit arc between O and A to the three-arcs graph.

Proposition 1. There exists no topological characterization for graphs that have the
property that RTSP is optimal.

Proof. Consider the three-arc graph G consisting of three unit arcs b 1 , b 2 , b 3 joining

O and A with nodes along each arc, that are equally spaced along b 1 and

b 2 , but they are not necessarily equally spaced along b 3 .Ifthe n nodes along b 3 are
also equally spaced, then we already argued that RTSP is not optimal. However,
if the n nodes along b 3 are all very close to A

( n 1 )

,

then these nodes reduce more or
less to one and the resulting graph is more or less a circle, in which case RTSP is
optimal. Indeed, RTSP is optimal: go to A randomly along b 1 or b 2 - search the
nodes along b 3 -returnto A andthengobackto O via the unvisited arc. Thus, the
same topological structure can have both RTSP optimal and non-optimal.

Note. Similar examples exist with node degrees ≥ 3 rather than 2 .

The RTSP strategy with arbitrary start is the analogous strategy to the Simple
network search. It is based on a minimal trajectory, not necessarily closed ,that
visits all the nodes and use it with probability 1/2 for each direction. The RTSP
leads to expected capture time equal to the half length of the minimal trajectory. It
is sometimes an optimal search strategy but for an arbitrary start there does not
exist a topological characterization for the optimality of the RTSP strategy .A
proof for that can be based on a discrete version of Fig. 1.2 , following the same line
of argument as in [ 5 ].