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.

Search for an immobile hider on a stochastic network / Garrec, Tristan; Scarsini, Marco. - In: EUROPEAN JOURNAL OF OPERATIONAL RESEARCH. - ISSN 0377-2217. - 283:2(2020), pp. 783-794. [10.1016/j.ejor.2019.11.040]

Search for an immobile hider on a stochastic network

Scarsini, Marco
2020

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.
2020
Game theory, Hide-search game, Zero-sum two-person game, Random graph
Search for an immobile hider on a stochastic network / Garrec, Tristan; Scarsini, Marco. - In: EUROPEAN JOURNAL OF OPERATIONAL RESEARCH. - ISSN 0377-2217. - 283:2(2020), pp. 783-794. [10.1016/j.ejor.2019.11.040]
File in questo prodotto:
File Dimensione Formato  
EJOR2020TG.pdf

Solo gestori archivio

Tipologia: Versione dell'editore
Licenza: Tutti i diritti riservati
Dimensione 932.49 kB
Formato Adobe PDF
932.49 kB Adobe PDF   Visualizza/Apri
Pubblicazioni consigliate

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11385/190962
Citazioni
  • Scopus 7
  • ???jsp.display-item.citation.isi??? 7
social impact