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

Chapter 16
A Discrete Search-Ambush Game
with a Silent Predator
Robert Arculus
Abstract We investigate the problem faced by a searcher attempting to capture a
mobile hider hidden in one of K discrete locations. In each time period the searcher
may either inspect a location or ambush. The hider can attempt to move to a ran-
dom location at any time, but will be captured during the move if the searcher is
ambushing. This game was invented by Steve Alpern, and is an outgrowth of the
recent studies of Alpern et al. (J R Soc Interface 8, 2011), which assume a 'noisy
predator', where the prey always knows the fraction of the search area that has
been inspected. The distinguishing feature of the problem addressed here is that the
predator is 'silent', so that the prey can only surmise the extent of the current ex-
ploration. The prey, however, remains 'noisy', in that the predator is informed if a
successful move occurs. To make the game tractable via computation, the searcher
is constrained to inspect the entire space before some chosen number of periods
elapse. Here, we present general upper and lower bounds on the expected time until
capture, and state solutions to the game for some simple cases; among other results,
we observe that when the search space consists of two locations and the searcher
is unconstrained, the expected capture time is equal to the square of the golden
ratio. We also provide some conjectures concerning optimal behaviour and bounds
on the value of the game for general K with an unconstrained searcher. Our
numerical results are mentioned but not discussed in detail, though they have
potential to provide further insight into the structure of the game.