  A set of n boxes, located on the vertices of a hypergraph G, contain known
but different rewards. A Searcher opens all the boxes in some hyperedge of G
with the objective of collecting the maximum possible total reward. Some of the
boxes, however, are booby trapped. If the Searcher opens a booby trapped box,
the search ends and she loses all her collected rewards. We assume the number k
of booby traps is known, and we model the problem as a zero-sum game between
the maximizing Searcher and a minimizing Hider, where the Hider chooses k boxes
to booby trap and the Searcher opens all the boxes in some hyperedge. The
payoff is the total reward collected by the Searcher. This model could reflect
a military operation in which a drone gathers intelligence from guarded
locations, and a booby trapped box being opened corresponds to the drone being
destroyed or incapacitated. It could also model a machine scheduling problem,
in which rewards are obtained from successfully processing jobs but the machine
may crash. We solve the game when G is a 1-uniform hypergraph (the hyperedges
are all singletons), so the Searcher can open just 1 box. When G is the
complete hypergraph (containing all possible hyperedges), we solve the game in
a few cases: (1) same reward in each box, (2) k=1, and (3) n=4 and k=2. The
solutions to these few cases indicate that a general simple, closed form
solution to the game appears unlikely.
