论文标题
具有移动目标的竞争搜索游戏
A competitive search game with a moving target
论文作者
论文摘要
我们介绍了一个离散的时间搜索游戏，其中两个玩家竞争首先找到一个对象。该物体根据有限的许多状态上的随时间变化的马尔可夫链移动。玩家知道马尔可夫链和对象的初始概率分布，但不观察对象的当前状态。球员轮流活跃。主动玩家选择一个状态，而另一个玩家观察到了这种选择。如果对象处于选定状态，则该玩家会获胜，并且游戏结束。否则，对象根据马尔可夫链移动，游戏将在下一个时期继续进行。 我们表明，该游戏允许一个值，对于任何错误的$ \ veps> 0 $，每个玩家都有一个纯净的（sub-game-perfect）$ \ veps $ - 最佳策略。有趣的是，0-最佳策略并不总是存在。 $ \ veps $ - 最佳策略在所有有限但足够长的视野上是$ 2 \ veps $ - 最佳的$ 2 \ veps $ - 在游戏折扣版本中的$ 2 \ veps $ - 优先级，只要折现因子接近1。此外，我们研究了有限截断策略的性能，这些策略易于计算和实施。我们特别注意重要的时间均匀案例，在此案例中得出了其他结果。
We introduce a discrete-time search game, in which two players compete to find an object first. The object moves according to a time-varying Markov chain on finitely many states. The players know the Markov chain and the initial probability distribution of the object, but do not observe the current state of the object. The players are active in turns. The active player chooses a state, and this choice is observed by the other player. If the object is in the chosen state, this player wins and the game ends. Otherwise, the object moves according to the Markov chain and the game continues at the next period. We show that this game admits a value, and for any error-term $\veps>0$, each player has a pure (subgame-perfect) $\veps$-optimal strategy. Interestingly, a 0-optimal strategy does not always exist. The $\veps$-optimal strategies are robust in the sense that they are $2\veps$-optimal on all finite but sufficiently long horizons, and also $2\veps$-optimal in the discounted version of the game provided that the discount factor is close to 1. We derive results on the analytic and structural properties of the value and the $\veps$-optimal strategies. Moreover, we examine the performance of the finite truncation strategies, which are easy to calculate and to implement. We devote special attention to the important time-homogeneous case, where additional results hold.
