A Discrete Search-Ambush Game with a Silent Predator - Search Theory: A Game Theoretic Perspective - page 238

16.1 Introduction and Terminology

Consider a zero-sum game played between a hider and a searcher on a search space
consisting of K discrete cells, with the searcher and hider minimising and maximis-
ing, respectively, the time elapsed until capture. In every unit of time the searcher
chooses either to inspect one of the cells, or to ambush in some central location.
Similarly, in each time unit the hider chooses either to remain motionless, or to at-
tempt to move from their current cell to a randomly selected cell (note this includes
the possibility that they may return to the cell they started the period in). If such a
move is attempted while the searcher is ambushing, then the hider is captured; oth-
erwise, the searcher loses all information gained so far regarding which cells do not
contain the hider.
We adopt the following terminology: a period is one discrete unit of time; a
round is a run of periods which ends when the hider is either caught or success-
fully randomises their position; a game consists of a sequence of rounds which ends
whenever there is a round in which the hider is caught. We include a second pa-
rameter, L , which is a limitation on the behaviour of the searcher, such that in any
round the searcher must commit to having searched all K cells by the time L periods
have elapsed. Thus while L limits the length of any round, any particular game can
potentially continue indefinitely. This parameter serves to make the game tractable
for computation purposes.
We assume that the searcher is silent , meaning the hider does not receive
additional information after the start of a round regarding the proportion of cells
that have been inspected. We further assume that the hider is noisy , in that, if cap-
ture does not occur in a period, the searcher is informed whether the hider moved or
remained motionless. The game can thus be modelled using a matrix representing a
simultaneous strategy commitment by both hider and searcher, where a hider strat-
egy involves picking a period in which to move, and a searcher strategy involves
picking K out of the first L periods in which to search. For a game to be non-trivial
and well-defined, we require L

> =

K the hider guarantees an infinite payoff
by moving in the first period of every round, and if L

K ;if L

<

K the searcher's constraint
cannot be satisfied. We refer to the game in general as the silent search-ambush
game .
We suppose that moving while search is taking place always allows the hider to
escape, even if the searcher is inspecting the cell that the hider was occupying at the
end of the previous period. Note also that when capture occurs, for the purposes of
measuring payoffs it is assumed to take place at the end of the relevant period.
As space available is abbreviated, some proofs will be omitted. Note also that
many of the results here were inspired by numerical solutions obtained computa-
tionally; we make occasional reference to these results, particularly when discussing
our conjecture in Sect. 16.7 , but they are not addressed in as much detail as they
might be.