A competitive search game with a moving target

Benoit Duvocelle, János Flesch, Mathias Staudigl and Dries Vermeulen

European Journal of Operational Research, 2022, vol. 303, issue 2, 945-957

Abstract: We introduce a discrete-time search game, in which two players compete to find an invisible object first. The object moves according to a time-varying Markov chain on finitely many states. The players are active in turns. At each period, the active player chooses a state. If the object is there then he finds the object and wins. Otherwise the object moves and the game enters the next period. We show that this game admits a value, and for any error-term ε>0, each player has a pure (subgame-perfect) ε-optimal strategy. Interestingly, a 0-optimal strategy does not always exist. We derive results on the analytic and structural properties of the value and the ε-optimal strategies. We devote special attention to the important time-homogeneous case, where we show that (subgame-perfect) optimal strategies exist if the Markov chain is irreducible and aperiodic.

Keywords: Game Theory; Search game; Two-player zero-sum game; Optimal strategies; Discrete time-varying Markov process (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221722001801
Full text for ScienceDirect subscribers only

Related works:
Working Paper: A competitive search game with a moving target (2020)
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:303:y:2022:i:2:p:945-957

DOI: 10.1016/j.ejor.2022.03.004

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().