A Classical Search Game in Discrete Locations

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 ${\alpha }_i$ for $i=1,\dots ,n$. The hider aims to maximize the expected time until detection, whereas 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 that can be constructed with up to n simple search sequences.

Funding: This work was supported by the Engineering and Physical Sciences Research Council [Grant EP/L015692/1] STOR-i Centre for Doctoral Training.