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

general, be formulated as an infinite-dimensional linear program. This formulation
with an algorithm for obtaining its (approximate) solution is presented by Anderson
and Aramendia [ 7 ].

1.1.2 The Searcher Starts at an Arbitrary Point

If we allow the searcher to start at any point in the network Q , then the natural
search trajectory to use is the Chinese postman path S which visits all the points of
Q and has minimum length but is not necessarily closed. The searcher can use the
following natural strategy:
Simple Strategy: Choose the starting point randomly, starting equiprobably at
either end of S , going to the other end along S .

For example, for a tree the Chinese postman path traverses the arcs of its diameter
once, and all other arcs twice. The simple strategy for a tree (see [ 18 ]) means picking
randomly an end of the diameter and using that Chinese postman path to traverse the
tree. Sometimes Simple is optimal. For example, if S is an Eulerian path then Simple
is optimal. Such an example is the three arcs graph, which is very difficult for the
fixed start, but very easy for the arbitrary start search game. In addition, Simple is
optimal for any tree, [ 18 ], and also for any tree with one or several Eulerian graphs
attached, [ 2 ]. However, Alpern, Baston, and Gal [ 5 ] have shown that it is impossible
to topologically characterize the graphs, for which Simple is optimal. Their result is
based on the graph in Fig. 1.2 .

Fig. 1.2 A graph for which simple is optimal only if the base is wide

D all have unit length, but the arcs DE and DF have
length r .If r is large, then it is easy to see that the optimal search strategy is to ran-
domly pick an end of the long interval and to traverse the network using the Chinese
postman path, so that Simple is the optimal search strategy. However, if r is small
then it can be shown that Simple is not optimal. Since the two networks are topo-
logically equivalent it follows that topological characterization for the optimality of
Simple is impossible. This is quite surprising because it contradicts the result for the
fixed start search games.

The arcs between A , B , C ,