Search for an immobile hider on a stochastic network
From MaRDI portal
Publication:2286995
DOI10.1016/J.EJOR.2019.11.040zbMATH Open1431.91062arXiv1904.12852OpenAlexW2991159027WikidataQ126663049 ScholiaQ126663049MaRDI QIDQ2286995FDOQ2286995
Marco Scarsini, Tristan Garrec
Publication date: 23 January 2020
Published in: European Journal of Operational Research (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/1904.12852
Random graphs (graph-theoretic aspects) (05C80) Search theory (90B40) 2-person games (91A05) Stochastic games, stochastic differential games (91A15) Games involving graphs (91A43) Positional games (pursuit and evasion, etc.) (91A24)
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Random graphs and complex networks. Volume 1
- Percolation
- Percolation
- The theory of search games and rendezvous.
- Cops and robbers in a random graph
- Find-and-fetch search on a tree
- Search Games with Mobile and Immobile Hider
- Paths in graphs
- A first course on zero-sum repeated games
- Search games
- A Multistage Search Game
- Search for an immobile entity on a network
- Network search games with immobile hider, without a designated searcher starting point
- Mining Coal or Finding Terrorists: The Expanding Search Paradigm
- Optimal Trade-Off Between Speed and Acuity When Searching for a Small Object
- Discrete Search with Directional Information
- On the Optimality of the Exponential Functions for Some Minimax Problems
- Yet more on the linear search problem
- The search game on a network with immobile hider
- Network search games, with arbitrary searcher starting point
- A search game on a cyclic graph
- On the optimality of a simple strategy for searching graphs
- Approximate solutions for expanding search games on general networks
- Search games with immobile hider
- Search Games on Trees with Asymmetric Travel Times
- A search game on the union of graphs with immobile hider
- A HIDE AND SEEK GAME WITH TRAVELING COST
- A SEARCH GAME WITH TRAVELING COST
- Complexity of searching an immobile hider in a graph
- Search for an immobile hider in a known subset of a network
- A general search game
- Searching symmetric networks with Utilitarian-Postman paths
- Hide-and-seek games on a tree to which Eulerian networks are attached
- A Discrete Search Game
- Hide-and-Seek Games on a Network, Using Combinatorial Search Paths
- Searching a Variable Speed Network
- Search-hide games on trees
- A hide–search game
- Optimum Evasion Versus Systematic Search
- Search games: literature and survey
- On a Discrete Search Problem on Three Arcs
- Searching a Tree with Permanently Noisy Advice
- The search for an intelligent evader concealed in one of an arbitrary number of regions
- The search for an intelligent evader: Strategies for searcher and evader in the two-region problem
- The gold-mine game
- Percolation games, probabilistic cellular automata, and the hard-core model
- Maker–Breaker percolation games I: crossing grids
Cited In (12)
- Possibility degree-based interval-valued \(q\)-rung orthopair fuzzy graphs
- A game of hide and seek in networks
- Planning a multi-sensors search for a moving target considering traveling costs
- A Linear Programming Approach to the Search Game on a Network with Mobile Hider
- Network search games with immobile hider, without a designated searcher starting point
- Search for an immobile entity on a network
- Search for a moving target in a competitive environment
- Complexity of searching an immobile hider in a graph
- A competitive search game with a moving target
- Multiple searchers searching for a randomly distributed immobile target on a unit network
- A differentiable path-following method to compute subgame perfect equilibria in stationary strategies in robust stochastic games and its applications
- Multi-objective search game: long-term vs short-term
This page was built for publication: Search for an immobile hider on a stochastic network
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2286995)
