Network search games with immobile hider,without a designated searcher starting point |
| |
Authors: | Steve Alpern Vic Baston Shmuel Gal |
| |
Institution: | (1) Department of Mathematics, London School of Economics, Houghton Street, London, WC2A 2AE, UK;(2) Department of Mathematics, University of Southampton, Southampton, UK;(3) Department of Statistics, University of Haifa, Haifa, Israel |
| |
Abstract: | In the (zero-sum) search game Γ(G, x) proposed by Isaacs, the Hider picks a point H in the network G and the Searcher picks a unit speed path S(t) in G with S(0) = x. The payoff to the maximizing Hider is the time T = T(S, H) = min{t : S(t) = H} required for the Searcher to find the Hider. An extensive theory of such games has been developed in the literature. This
paper considers the related games Γ(G), where the requirement S(0) = x is dropped, and the Searcher is allowed to choose his starting point. This game has been solved by Dagan and Gal for the
important case where G is a tree, and by Alpern for trees with Eulerian networks attached. Here, we extend those results to a wider class of networks,
employing theory initiated by Reijnierse and Potters and completed by Gal, for the fixed-start games Γ(G, x). Our results may be more easily interpreted as determining the best worst-case method of searching a network from an arbitrary
starting point. |
| |
Keywords: | Search game Network Zero-sum Chinese postman Eulerian |
本文献已被 SpringerLink 等数据库收录! |
|