Optimal pure strategies for a discrete search game
Optimal pure strategies for a discrete search game
复制标题
离散搜索博弈的最优纯策略
DOI：
10.1016/j.ejor.2023.08.041
复制
发表时间：
2024
影响因子：
6.4
通讯作者：
Lin, Kyle Y.
中科院分区：
文献类型：
--
作者：
Bui, Thuy;Lidbetter, Thomas;Lin, Kyle Y.
考虑一个隐藏者和搜索者之间的两人零和搜索博弈。隐藏者选择隐藏在n个离散位置（或“盒子”）中的一个，搜索者选择搜索序列，指定在这些盒子中查找的顺序，直到找到隐藏者。在框i处的搜索花费t i个时间单位，并且以概率q i独立地找到隐藏器（如果隐藏在那里），其中i= 1，.，n。搜索者希望最小化找到隐藏者所需的预期总时间，而隐藏者希望最大化它。文献中表明，搜索者具有最优搜索策略，该策略以适当的概率混合多达n个不同的搜索序列。本文研究了搜索器的最优纯策略的存在性-一个确定性的搜索序列，实现最优的预期总搜索时间，无论隐藏在哪里。我们确定了几种情况下，搜索者有一个最佳的纯策略，和几种情况下，这种最佳的纯策略不存在。最优纯搜索策略具有重要的实用价值，因为搜索者不需要随机化他们的行动，并且如果从最优混合策略中选择的搜索序列结果不好，将避免第二次猜测自己。
Consider a two-person zero-sum search game between a Hider and a Searcher. The Hider chooses to hide in one of n discrete locations (or “boxes”) and the Searcher chooses a search sequence specifying which order to look in these boxes until finding the Hider. A search at box i takes t i time units and finds the Hider—if hidden there—independently with probability q i, for i= 1,…, n. The Searcher wants to minimize the expected total time needed to find the Hider, while the Hider wants to maximize it. It is shown in the literature that the Searcher has an optimal search strategy that mixes up to n distinct search sequences with appropriate probabilities. This paper investigates the existence of optimal pure strategies for the Searcher—a single deterministic search sequence that achieves the optimal expected total search time regardless of where the Hider hides. We identify several cases in which the Searcher has an optimal pure strategy, and several cases in which such optimal pure strategy does not exist. An optimal pure search strategy has significant practical value because the Searcher does not need to randomize their actions and will avoid second guessing themselves if the chosen search sequence from an optimal mixed strategy does not turn out well.