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

Chapter 1
Search Games: A Review
Shmuel Gal
Abstract This review presents an update on the area of Search Games, highlight-
ing recent developments in the field, as well as presenting some new problems for
further research. The search space is either a graph, a bounded domain, a mixture
of the above, or an unbounded set. The search process is presented as a two-player
zero-sum game between the searcher and the hider. The searcher moves along a
continuous trajectory and the cost function is the time needed to find the hider. Our
review emphasises general results concerning minimax search trajectories and opti-
mal search strategies.
We present a review on mathematical modeling of hide and seek situations that
we all know from our childhood. These situations are common in military and anti-
terror activity, as well as many other areas. Isaacs [ 30 ] provided a mathematical
foundation to study of such situations in the last chapter of his topic, introducing the
concept of a continuous search game, which was further developed by Gal [ 24 ]. That
work, and the updated version by Alpern and Gal [ 4 ], has stimulated much research,
with applications to Computer Science, Economics and Biology. The present chap-
ter reviews different types of search games, putting an emphasis on recent results.
As such, it is an update of a previous survey article on search games that appeared
in the encyclopedia of Operations Research [ 26 ]. The present chapter also contains
some new observations on searching a graph using the Traveling Salesman Tour and
on searching mixed spaces which did not appear in print before, outlining possible
directions of future research.
We consider a zero-sum game played between a searcher and a hider in a search
space Q which is either a compact set in a Euclidean space or an unbounded con-
nected set, e.g., the real line. The searcher usually starts moving from a specified