  In delegation problems, a principal does not have the resources necessary to
complete a particular task, so they delegate the task to an untrusted agent
whose interests may differ from their own. Given any family of such problems
and space of mechanisms for the principal to choose from, the delegation gap is
the worst-case ratio of the principal's optimal utility when they delegate
versus their optimal utility when solving the problem on their own. In this
work, we consider the delegation gap of the generalized Pandora's box problem,
a search problem in which searching for solutions incurs known costs and
solutions are restricted by some downward-closed constraint. First, we show
that there is a special case when all random variables have binary support for
which there exist constant-factor delegation gaps for matroid constraints.
However, there is no constant-factor delegation gap for even simple non-binary
instances of the problem. Getting around this impossibility, we consider two
variants: the free-agent model, in which the agent doesn't pay the cost of
probing elements, and discounted-cost approximations, in which we discount all
costs and aim for a bicriteria approximation of the discount factor and
delegation gap. We show that there are constant-factor delegation gaps in the
free-agent model with discounted-cost approximations for certain downward
closed constraints and constant discount factors. However, constant delegation
gaps can not be achieved under either variant alone. Finally, we consider
another variant called the shared-cost model, in which the principal can choose
how costs will be shared between them and the agent before delegating the
search problem. We show that the shared-cost model exhibits a constant-factor
delegation gap for certain downward closed constraints.
