Computing Optimal Strategies for a Search Game in Discrete Locations

Jake Clarkson () and Kyle Y. Lin ()
Additional contact information
Jake Clarkson: Centre Inria d’Université Côte d’Azur, 06902 Sophia Antipolis, France
Kyle Y. Lin: Operations Research Department, Naval Postgraduate School, Monterey, California 93943

INFORMS Journal on Computing, 2025, vol. 37, issue 3, 666-683

Abstract: Consider a two-person zero-sum search game between a hider and a searcher. The hider hides among n discrete locations, and the searcher successively visits individual locations until finding the hider. Known to both players, a search at location i takes t i time units and detects the hider—if hidden there—independently with probability α i , for i = 1 , … , n . The hider aims to maximize the expected time until detection, whereas the searcher aims to minimize it. We present an algorithm to compute an optimal strategy for each player. We demonstrate the algorithm’s efficiency in a numerical study, in which we also study the characteristics of the optimal hiding strategy.

Keywords: search games; Gittins index; semifinite games; search and surveillance (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/ijoc.2023.0155 (application/pdf)

Related works:
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:inm:orijoc:v:37:y:2025:i:3:p:666-683

Access Statistics for this article

More articles in INFORMS Journal on Computing from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().