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.

Delegation covers a broad class of problems in which a principal doesn't have the resources or expertise necessary to complete a task by themselves, so they delegate the task to an agent whose interests may not be aligned with their own. Stochastic probing describes problems in which we are tasked with maximizing expected utility by "probing" known distributions for acceptable solutions subject to certain constraints. In this work, we combine the concepts of delegation and stochastic probing into a single mechanism design framework which we term delegated stochastic probing. We study how much a principal loses by delegating a stochastic probing problem, compared to their utility in the non-delegated solution. Our model and results are heavily inspired by the work of Kleinberg and Kleinberg in "Delegated Search Approximates Efficient Search." Building on their work, we show that there exists a connection between delegated stochastic probing and generalized prophet inequalities, which provides us with constant-factor deterministic mechanisms for a large class of delegated stochastic probing problems. We also explore randomized mechanisms in a simple delegated probing setting, and show that they outperform deterministic mechanisms in some instances but not in the worst case.