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

Pandora's Problem with Combinatorial Cost / Berger, Ben; Ezra, Tomer; Feldman, Michal; Fusco, Federico. - (2023), pp. 273-292. (Intervento presentato al convegno ACM Conference on Economics and Computation tenutosi a Londra) [10.1145/3580507.3597699].

Pandora's Problem with Combinatorial Cost

Tomer Ezra
;
Michal Feldman
;
Federico Fusco
2023

Abstract

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
2023
ACM Conference on Economics and Computation
pandora’s problem; pandora’s box problem
04 Pubblicazione in atti di convegno::04b Atto di convegno in volume
Pandora's Problem with Combinatorial Cost / Berger, Ben; Ezra, Tomer; Feldman, Michal; Fusco, Federico. - (2023), pp. 273-292. (Intervento presentato al convegno ACM Conference on Economics and Computation tenutosi a Londra) [10.1145/3580507.3597699].
File allegati a questo prodotto
File Dimensione Formato  
Berger_Pandora's_2023.pdf

solo gestori archivio

Tipologia: Versione editoriale (versione pubblicata con il layout dell'editore)
Licenza: Tutti i diritti riservati (All rights reserved)
Dimensione 682.31 kB
Formato Adobe PDF
682.31 kB Adobe PDF   Contatta l'autore
Berger_preprint_Pandora's_2023.pdf

accesso aperto

Note: https://doi.org/10.1145/3580507.3597699
Tipologia: Documento in Pre-print (manoscritto inviato all'editore, precedente alla peer review)
Licenza: Tutti i diritti riservati (All rights reserved)
Dimensione 463.69 kB
Formato Adobe PDF
463.69 kB Adobe PDF

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11573/1684836
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 1
  • ???jsp.display-item.citation.isi??? ND
social impact