A Classical Search Game in Discrete Locations
研究一个两人零和搜索博弈，藏匿者藏在n个离散位置中，搜索者依次访问位置，每次搜索耗时且可能检测失败，证明了双方最优策略的存在性。
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 [Formula: see text] for [Formula: see text]. 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.