  Many practical search problems concern the search for multiple hidden objects
or agents, such as earthquake survivors. In such problems, knowing only the
list of possible locations, the Searcher needs to find all the hidden objects
by visiting these locations one by one. To study this problem, we formulate new
game-theoretic models of discrete search between a Hider and a Searcher. The
Hider hides $k$ balls in $n$ boxes, and the Searcher opens the boxes one by one
with the aim of finding all the balls. Every time the Searcher opens a box she
must pay its search cost, and she either finds one of the balls it contains or
learns that it is empty. If the Hider is an adversary, an appropriate payoff
function may be the expected total search cost paid to find all the balls,
while if the Hider is Nature, a more appropriate payoff function may be the
difference between the total amount paid and the amount the Searcher would have
to pay if she knew the locations of the balls a priori (the regret). We give a
full solution to the regret version of this game, and a partial solution to the
search cost version. We also consider variations on these games for which the
Hider can hide at most one ball in each box. The search cost version of this
game has already been solved in previous work, and we give a partial solution
in the regret version.
