Pandora’s Problem with Combinatorial Cost

Pandora’s problem is a fundamental model in economics that studies optimal search strategies under costly inspection. In this paper, we initiate the study of Pandora’s problem with combinatorial costs, capturing applications where search cost is nonadditive. Weitzman’s celebrated algorithm (1979) demonstrates that for additive costs, the optimal search strategy is nonadaptive and computationally feasible. We inquire to which extent this structural and computational simplicity extends beyond additive costs. Our main result is that the class of submodular cost functions admits an optimal strategy that follows a fixed order, thus preserving the structural simplicity of additive costs. In contrast, for the more general class of subadditive (or even fractionally subadditive) cost functions, the optimal strategy may inevitably determine the search order adaptively. On the computational side, obtaining any approximation to the optimal utility requires superpolynomially many queries to the cost function, even for a strict subclass of submodular cost functions. Funding: B. Berger and M. Feldman are partially supported by the HORIZON EUROPE European Research Council [Grant 866132] and the United States-Israel Binational Science Foundation [Grant 2020788]. T. Ezra is supported by the Harvard University Center of Mathematical Sciences and Applications. F. Fusco is partially supported by the National Recovery and Resilience Plan (PNRR) by Ministero dell’Università e della Ricerca [Project IR0000013-SoBigData.it] and the Future Artificial Intelligence Research project funded by the NextGenerationEU program within the National Recovery and Resilience Plan Extended Partnership for Artificial Intelligence (PNRR-PE-AI) scheme [Grant M4C2, investment 1.3, line on Artificial Intelligence]. Additionally, this work was supported by Ministero dell’Università e della Ricerca [Grant ALGADIMAR], the Israel Science Foundation [Grant 317/17], the Amazon Research Award, and the HORIZON EUROPE European Research Council [Grant 788893].