Pandora's Problem with Combinatorial Cost
成果类型：
Article; Early Access
署名作者：
Berger, Ben; Ezra, Tomer; Feldman, Michal; Fusco, Federico
署名单位：
Harvard University; Tel Aviv University; Sapienza University Rome
刊物名称：
MATHEMATICS OF OPERATIONS RESEARCH
ISSN/ISSBN：
0364-765X
DOI：
10.1287/moor.2023.0248
发表日期：
2024
关键词：
摘要：
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.