Search Games with Multiple Hidden Objects
Search Games with Multiple Hidden Objects
复制标题
搜索具有多个隐藏物体的游戏
DOI：
10.1137/120893938
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
T. Lidbetter
中科院分区：
文献类型：
--
作者：
T. Lidbetter
我们考虑了一类零和搜索对策，其中搜索者试图最小化寻找被隐藏者隐藏的几个对象的预期时间。我们从分析一个游戏开始，在这个游戏中，搜索者希望找到隐藏在$n；k$盒子中的$k$球。搜索每个盒子都有一个已知的成本，搜索者试图在最坏的情况下将找到所有对象的总预期成本降至最低。我们证明了对于搜索者来说，从搜索$k$-子集$H$开始搜索概率为$\nu(H)$的盒子是最优的，这与盒子的搜索成本在$H$中的乘积成正比。然后，搜索者应该以随机顺序搜索剩余的$n-k$个盒子。最坏情况下的Hider分布是分布$\nu$。我们区分了聪明的搜索者和普通的搜索者，前者可以在搜索过程中改变自己的搜索计划，后者必须从一开始就制定自己的计划。我们表明，聪明的搜索者没有优势。然后，我们展示了如何用更一般的网络搜索对策来表示该对策，并给出了任意网络上对策值的上下界。对于$2$-弧连通网络(不能通过移除少于两条弧而断开的网络)，我们解决了智能搜索器的对策，并给出了正常搜索器的值的一个上界。如果网络是一个圆，则这个界限是紧的。
We consider a class of zero-sum search games in which a Searcher seeks to minimize the expected time to find several objects hidden by a Hider. We begin by analyzing a game in which the Searcher wishes to find $k$ balls hidden among $n>k$ boxes. There is a known cost of searching each box, and the Searcher seeks to minimize the total expected cost of finding all the objects in the worst case. We show that it is optimal for the Searcher to begin by searching a $k$-subset $H$ of boxes with probability $\nu(H)$, which is proportional to the product of the search costs of the boxes in $H$. The Searcher should then search the $n-k$ remaining boxes in a random order. A worst-case Hider distribution is the distribution $\nu$. We distinguish between the case of a smart Searcher who can change his search plan as he goes along and a normal Searcher who has to set out his plan from the beginning. We show that a smart Searcher has no advantage. We then show how the game can be formulated in terms of a more general network search game, and we give upper and lower bounds for the value of the game on an arbitrary network. For $2$-arc connected networks (networks that cannot be disconnected by the removal of fewer than two arcs), we solve the game for a smart Searcher and give an upper bound on the value for a normal Searcher. This bound is tight if the network is a circle.