Search games with multiple hidden objects

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.