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

point O called the origin but choosing the starting point arbitrarily is also consid-
ered. It is assumed that the searcher is free to choose any continuous trajectory
inside Q subject to a maximal velocity constraint which is normalized to 1. The

hider can be either stationary or mobile. It will always be assumed that neither the
searcher nor the hider has any knowledge about the movement of the other player
until their distance apart is less than or equal to the discovery radius r

,

and at this
moment capture occurs. The discovery radius r is assumed to be small with respect
to the dimension of Q

,

.

For one dimensional sets, r is assumed zero. A search tra-
jectory will be denoted by S and a hiding point or trajectory (depending whether
the hider is immobile or mobile) by H

. The cost function (payoff to the maximizing

hider) c is the time spent until the hider is found (the search time). A mixed

strategy s (resp. h ) of the searcher (resp. hider) is a probability measure on the set
of the searcher (resp. hider) pure strategies with expected payoff c

( S , H ) ,

( s , h ) . The exis-

tence of a value, v (minimax theorem) for such problems, and an optimal searcher

mixed strategy are established in [ 24 ]and[ 3 ]. An optimal hiding strategy need not
exist, only

,

-optimal strategies always exist. The existence theorem holds both for
immobile and mobile hider.

ε

1.1 Search Games for an Immobile Hider

In this section we consider games with an immobile hider, and the search space is
usually a network. In some sense, these are the simplest search games, but even
their solution can be very subtle and, as we shall see below, there still remain some
open problems to be solved. We assume that the search space Q is a finite connected
graph in which each arc has a given length. The sum of these lengths will be denoted
by

μ ,

which is called the total length of the graph. A pure strategy for the hider
is simply a (hiding) point H in Q

,

which can be a node or a point on one of the

= ( )

arcs . A pure strategy S for the searcher is a continuous trajectory in Q with

speed 1. The payoff c corresponding to pure strategies S and H is the search time
c

S t

( S , H )= min { t : S ( t )= H }.

1.1.1 The Searcher Starts at a Fixed Point

A natural way to search a graph is to use a Chinese postman tour (see [ 21 ]) i.e., a
closed trajectory that visits all the arcs of Q and has minimal length. Such a tour will
be denoted by S ∗ . Obviously, if Q is Eulerian, then S ∗ can be chosen as any Eulerian

In this case, if S ∗ (

tour with length is an Eulerian tour, then visiting

it with probability 1/2 in the forward direction and probability 1/2 in the backward
direction (using S ∗ ( μ −

μ . t ) , 0 ≤ t ≤ μ

t ) as the search trajectory) is an optimal search strategy.