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 many real-life scenarios where search cost is non-additive. Weitzman's celebrated algorithm [1979] establishes the remarkable result that, for additive costs, the optimal search strategy is non-adaptive and computationally feasible. We inquire to which extent this structural and computational simplicity extends beyond additive cost functions. Our main result is that the class of submodular cost functions admits an optimal strategy that follows a fixed, non-adaptive order, thus preserving the structural simplicity of additive cost functions. In contrast, for the more general class of subadditive (or even XOS) cost functions, the optimal strategy may already need to determine the search order adaptively. On the computational side, obtaining any approximation to the optimal utility requires super polynomially many queries to the cost function, even for a strict subclass of submodular cost functions.
翻译:潘多拉的问题是一个经济学的基本模型,它研究的是成本昂贵的最佳搜索战略。在本文中,我们开始研究潘多拉的组合成本问题,捕捉了许多搜索成本非附加成本的真实生活情景。威茨曼的著名算法[1979年]确定了一个显著的结果,即对于添加成本而言,最佳搜索战略是非适应性的,计算也是可行的。我们调查这种结构和计算简单性在多大程度上超越了添加成本功能。我们的主要结果是,子模块成本功能类别采纳了一种遵循固定、非适应性排序的最佳战略,从而保持了添加成本功能的结构简单性。相比之下,对于更普通的子添加(甚至XOS)成本功能,最佳战略可能已经需要以适应性的方式决定搜索顺序。在计算方面,任何对最佳用途的近似都要求对成本功能进行超多边质质质质质,即使是严格的子模块子模块的子模块成本功能也是如此。</s>