Delegation with Costly Inspection

We study the problem of delegated choice with inspection cost (DCIC), which is a variant of the delegated choice problem by Kleinberg and Kleinberg (EC'18) as well as an extension of the Pandora's box problem with nonobligatory inspection (PNOI) by Doval (JET'18). In our model, an agent may strategically misreport the proposed element's utility, unlike the standard delegated choice problem which assumes that the agent truthfully reports the utility for the proposed alternative. Thus, the principal needs to inspect the proposed element possibly along with other alternatives to maximize its own utility, given an exogenous cost of inspecting each element. Further, the delegation itself incurs a fixed cost, thus the principal can decide whether to delegate or not and inspect by herself.We show that DCIC indeed is a generalization of PNOI where the side information from a strategic agent is available at certain cost, implying its NP-hardness by Fu, Li, and Liu (STOC'23). In fact, we observe that DCIC becomes significantly more challenging than PNOI and the delegated choice problem in several aspects. First, neither of (i) running PNOI policy without delegation nor (ii) running a simple delegation mechanism can achieve a constant approximation to the optimal mechanism for DCIC, implying that we need to use both the delegation and inspection for efficient mechanisms. Furthermore, the standard approaches to PNOI (or Pandora's box problem) for upper bounding the optimal policy in a structured way to obtain algorithms do not easily extend to DCIC.Nevertheless, we provide constant approximate mechanisms for DCIC problem. En route to this result, we first consider a costless delegation setting in which the cost of delegation is free. We prove that the maximal mechanism over the pure delegation with a single inspection and an PNOI policy without delegation achieves a 3-approximation for DCIC with costless delegation, which is further proven to be tight. These results hold even when the cost comes from an arbitrary monotone set function, and can be improved to a 2-approximation if the cost of inspection is the same for every element. We extend these techniques by presenting a constant factor approximate mechanism for the general setting for rich class of instances.