Skip to Main content Skip to Navigation
Journal articles

Search for an immobile hider on a stochastic network

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.
Document type :
Journal articles
Complete list of metadata

https://hal.archives-ouvertes.fr/hal-03489798
Contributor : Accord Elsevier CCSD Connect in order to contact the contributor
Submitted on : Thursday, July 21, 2022 - 10:44:12 AM
Last modification on : Thursday, September 22, 2022 - 10:44:04 AM

File

S0377221719309518.pdf
Files produced by the author(s)

Licence


Distributed under a Creative Commons Attribution - NonCommercial 4.0 International License

Identifiers

Citation

Tristan Garrec, Marco Scarsini. Search for an immobile hider on a stochastic network. European Journal of Operational Research, Elsevier, 2020, 283 (2), pp.783 - 794. ⟨10.1016/j.ejor.2019.11.040⟩. ⟨hal-03489798⟩

Share

Metrics

Record views

13

Files downloads

0