Search for an Immobile Hider on a Stochastic Network
Preprint
Abstract
Harry hides on an edge of a graph and does not move from there. Sally, starting from a known origin, tries to find him as soon as she can. Harry's goal is to be found as late as possible. At any given time, each edge of the graph is either active or inactive, independently of the other edges, with a known probability of being active. This situation can be modeled as a zero-sum two-person stochastic game. We show that the game has a value and we provide upper and lower bounds for this value. Finally, by generalizing optimal strategies of the deterministic case, we provide more refined results for trees and Eulerian graphs.Keywords
All Related Versions
This publication has 39 references indexed in Scilit:
- Searching symmetric networks with Utilitarian‐Postman pathsNetworks, 2009
- Hide‐and‐seek games on a tree to which Eulerian networks are attachedNetworks, 2008
- Network search games, with arbitrary searcher starting pointNetworks, 2008
- A search game on a cyclic graphNaval Research Logistics (NRL), 2004
- A search game on the union of graphs with immobile hiderNaval Research Logistics (NRL), 1995
- Search games with immobile hiderInternational Journal of Game Theory, 1993
- The search game on a network with immobile hiderNetworks, 1990
- The gold-mine gameJournal of Optimization Theory and Applications, 1990
- The search for an intelligent evader concealed in one of an arbitrary number of regionsNaval Research Logistics Quarterly, 1979
- The search for an intelligent evader: Strategies for searcher and evader in the two‐region problemNaval Research Logistics Quarterly, 1978