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

of any dimension, a hider picks a hiding point (that is a point in ). The searcher

then picks some sort of unit speed trajectory in the region. The payoff (or search
time) is the time taken until the searcher's trajectory meets the hider. There is an
assumption that the searcher is able to find a tour of the region that is not wasteful,
so that it does not 'double back' on itself. The solution of the game Isaacs gives is
simple: the searcher picks one such tour S , then follows it with probability one half
and follows the reverse tour with probability one half. Supposing

R

R

has measure μ ,

R

if S finds a point in at time t , the reverse of S will find the same point at time

μ −

t . Hence the expected time T to find any given point is given by

T = 1 / 2 t + 1 / 2 ( μ − t )= μ / 2

The value of the game is therefore at most μ / 2. The hider can ensure the payoff

is no more than μ / 2 by hiding uniformly in R , so that the probability he hides

in any subset of is proportional to its measure. By using this strategy, the hider

ensures that the probability the searcher finds him before time t is no more than t

R

/ μ

for 0 ≤ t ≤ μ , so the probability the search time is t or more is at least 1 − t / μ .

Hence the expected time T satisfies

∞

T = Pr ( search time is ≥ t ) dt

0

μ
0 (

≥ 1 − t / μ ) dt

= μ / 2 .

The value of the game is therefore at least μ / 2, and combining the bounds we

have

Theorem 1 (Isaacs). The value of the simple search game is μ / 2 .

These strategies given by Isaacs are important and direct a lot of the later research
on search games.

2.3 Search Games on Networks

A more precise formulation of Isaac's game is given by Gal [ 10 ]and[ 11 ]. Gal
focuses on the game played on a network Q , which is any connected finite set of
arcs of measure

with a distinguished starting point O , called the root. The hider
picks a point H in Q and the searcher picks a unit speed path S starting from O .
The payoff (or search time) is the time taken for the path to reach H .Thisgameis
mentioned in Sect. 1.1.1 of Chap. 1 .
In [ 10 ], Gal uses Isaacs hider strategy to give a lower bound for the value V of
the game: by hiding uniformly in the network the hider can ensure that the search
time always at least

μ

μ / 2. We call this strategy u . However, the assumption made