Network Search from a Game Theoretic Perspective

Date

Nov 23, 2015

Time

1:30 PM - 2:30 PM

Speaker

Steve Alpern

Affiliation

U. of Warwick

Language

en

Main Topic

Physik

Other Topics

Physik

Host

Advanced Study Group Klages

Description

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.

Last modified: Nov 23, 2015, 8:42:42 AM