Steve Alpern
U. of Warwick
Network Search from a Game Theoretic Perspective
A searcher wishes to find an unknown point H (hidden object or prey) on a
given metric network Q. The searcher typically starts from a known point O and
moves at unit speed on Q until the first time T that he reaches H. The
approach studied here, formulated by Isaacs [1] is to view this problem as a
zero-sum game with the capture time T as payoff. The hider (who chooses H) is
the maximizer, and the searcher (who chooses a search path S(t) ) is the
minimizer. The approach is equivalent to viewing the searcher’s problem as a
game against nature, but it also gives any real hider advice as to the optimal
distribution of choosing H. The "classical theory" begins in 1979 with the
work of Gal [2] for trees Q, and culminates with Gal’s extension of the tree
theory to weakly Eulerian networks in 2000 [3]. In between, many other
researchers contributed to the theory. Here, we review the classical theory
and present extensions in various directions that enlarge the applicability
and theory of such search games.
[1] R. Isaacs. Differential Games. John Wiley & Sons, New York, 1965.
[2] S. Gal. Search games with mobile and immobile
hider. SIAM Journal on Control and Optimization 17:99-122, 1979.
[3] S. Gal. On the optimality of a simple strategy for searching
graphs. International Journal of Game Theory 29:533-542, 2000.