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

This game was solved by Gal [ 23 ], under the condition that the search space Q
is convex. Actually a much weaker condition is needed (see [ 24 ], p. 39). The value,
v ∼ 2 r , is the area of the

room (twice the value obtained for an immobile hider). Gal's optimal strategy for
the princess is to stay at random locations in Q and make the changes of location
not too often but also not too rarely, (for details see [ 23 ]or[ 24 ]). His proposed
optimal search strategy is based on subdividing Q into many narrow rectangles
searching a random rectangle in a specific random fashion for some time and then
moving to another random rectangle, etc. Note that this type of strategy would not
be efficient if the rules of the game were changed in such a way that the hider knows
the position of the searcher from time to time. A search strategy that is robust to
this type of knowledge has been presented by Lalley and Robbins [ 35 ]. It is based
on going in a straight line and, upon reaching the boundary, choosing a random
direction going back into the region, etc. It should be noted, though, that Lalley
and Robbins' strategy would be ineffective for non-convex regions but Gal's search
strategy is also effective for non-convex regions and can also be adapted to more
general problems, e.g., a non-constant capture radius, multi-dimensional regions,
more general cost functions and search game with several searchers. Several other
extensions have been presented by Garnaev (e.g. [ 29 ]).

, of the princess and monster game satisfies v where μ

1.2.2 Mobile Hider on a Network

The princess and monster game on an arbitrary network remains far from solved.
The only case that has been settled is the game on a circle, which was originally
suggested in the 1960s by Isaacs [ 30 ] as a stepping stone for the game in the region
described above. This problem was independently solved by Alpern [ 1 ] and Zelikin
[ 45 ]. (See also Wilson [ 44 ].) Their optimal search strategy is now a well known
strategy which has been named by Alpern ' coin half tour' . It says simply flip a
symmetric coin every half tour of the circle and go clockwise or anti-clockwise.
This strategy has also been used for rendezvous problems and in computer science.

The search game on the unit interval with an arbitrary start, which may look
like a rather trivial problem, is surprisingly difficult. At first sight it may look like
there is a simple optimal strategy: pick a random end of the interval and go, as
fast as possible, to the other end. However, the hider's best response to this is to
start very near to a random end, and move to the other end with unit speed. This
leads to an expected search time of 0 75. Surprisingly, the searcher can do better,

using a more complex mixed strategy, and the value of the game is about 0

.

7. This
unexpected behavior, and an approximate solution of the game on the interval has
been presented by Alpern et al. [ 6 ]. The search game with an mobile hider on other
networks remains open. More information on these games, as well as an addendum
to the computations from [ 6 ] can be found in Chap. 4 .

.