A Classical Search Game in Discrete Locations

• 成果类型: Article
• 署名作者: Clarkson, Jake; Lin, Kyle Y.; Glazebrook, Kevin D.
• 署名单位: Lancaster University; United States Department of Defense; United States Navy; Naval Postgraduate School; Lancaster University
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.2022.1279
• 发表日期: 2023
• 页码: 687-707
• 关键词: intelligent evader

摘要

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, ..., 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.