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

## Dettaglio pubblicazione

2023, EC '23: Proceedings of the 24th ACM Conference on Economics and Computation, Pages 273-292

### Pandora's Problem with Combinatorial Cost (*04b Atto di convegno in volume*)

#### Berger Ben, Ezra Tomer, Feldman Michal, Fusco Federico

**ISBN:**9798400701047

**Gruppo di ricerca:**Algorithms and Data Science

**keywords**