A search game is a two-person

zero-sum game Zero-sum game is a mathematical representation in game theory and economic theory of a situation which involves two sides, where the result is an advantage for one side and an equivalent loss for the other. In other words, player one's gain is e ...

which takes place in a

set Set, The Set, SET or SETS may refer to: Science, technology, and mathematics Mathematics *Set (mathematics), a collection of elements *Category of sets, the category whose objects and morphisms are sets and total functions, respectively Electro ...

called the search space. The searcher can choose any continuous trajectory subject to a maximal velocity constraint. It is always 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 and at this very moment capture occurs. As mathematical models, search games can be applied to areas such as hide-and-seek games that children play or representations of some tactical military situations. The area of search games was introduced in the last chapter of Rufus Isaacs' classic book "Differential Games" and has been developed further by Shmuel GalS. Gal, ''Search Games'', Academic Press, New York (1980)S. Alpern and S. Gal,
The Theory of Search Games and Rendezvous
', Springer (2003). and

Steve Alpern Professor Steve Alpern is a professor of Operational Research at the University of Warwick, where he recently moved after working for many years at the London School of Economics. His early work was mainly in the area of dynamical systems and er ...

. The princess and monster game deals with a moving target.

Strategy

A natural strategy to search for a stationary target in a graph is to find a minimal closed curve L that covers all the arcs of the graph. (L is called a

Chinese postman In graph theory, a branch of mathematics and computer science, Guan's route problem, the Chinese postman problem, postman tour or route inspection problem is to find a shortest closed path or circuit that visits every edge of an (connected) undi ...

tour). Then, traverse L with probability 1/2 for each direction. This strategy seems to work well if the graph is Eulerian. In general, this random Chinese postman tour is indeed an optimal search strategy if and only if the graph consists of a set of Eulerian graphs connected in a tree-like structure. A misleadingly simple example of a graph not in this family consists of two nodes connected by three arcs. The random Chinese postman tour (equivalent to traversing the three arcs in a random order) is not optimal, and the optimal way to search these three arcs is complicated.

Unbounded domains

In general, the reasonable framework for searching an unbounded domain, as in the case of an

online algorithm In computer science, an online algorithm is one that can process its input piece-by-piece in a serial fashion, i.e., in the order that the input is fed to the algorithm, without having the entire input available from the start. In contrast, an o ...

, is to use a normalized cost function (called the competitive ratio in Computer Science literature). The

minimax Minimax (sometimes MinMax, MM or saddle point) is a decision rule used in artificial intelligence, decision theory, game theory, statistics, and philosophy for ''mini''mizing the possible loss for a worst case (''max''imum loss) scenario. When ...

trajectory for problems of these types is always a geometric sequence (or exponential function for continuous problems). This result yields an easy method to find the minimax trajectory by minimizing over a single parameter (the generator of this sequence) instead of searching over the whole trajectory space. This tool has been used for the

linear search problem In computational complexity theory, the linear search problem is an optimal search problem introduced by Richard E. Bellman and independently considered by Anatole Beck. The problem "An immobile hider is located on the real line according to a ...

, i.e., finding a target on the infinite line, which has attracted much attention over several decades and has been analyzed as a search game. It has also been used to find a minimax trajectory for searching a set of concurrent rays. Optimal searching in the plane is performed by using exponential spirals. Searching a set of concurrent rays was later re-discovered in Computer Science literature as the 'cow-path problem'.MY Kao, JH Reif and SR Tate
Searching in an unknown environment: an optimal randomized algorithm for the cow-path problem
SODA 1993.

References

{{DEFAULTSORT:Search Games Non-cooperative games Search algorithms