Home > Research > Publications & Outputs > A Classical Search Game In Discrete Locations

Electronic data

  • SearchGame_resub_2_to_KG

    Accepted author manuscript, 476 KB, PDF document

    Available under license: CC BY-NC: Creative Commons Attribution-NonCommercial 4.0 International License

View graph of relations

A Classical Search Game In Discrete Locations

Research output: Contribution to Journal/MagazineJournal articlepeer-review

E-pub ahead of print
<mark>Journal publication date</mark>1/07/2022
<mark>Journal</mark>Mathematics of Operations Research
Number of pages40
Publication StatusE-pub ahead of print
Early online date1/07/22
<mark>Original language</mark>English


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 ti 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, while the searcher aims to minimize it. We prove the existence of an optimal strategy for each player. In particular, any optimal mixed hiding strategy hides in each location with a nonzero probability, and there exists an optimal mixed search strategy which can be constructed with up to n simple search sequences.