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.