The Pandora's Box problem, originally posed by Weitzman in 1979, models selection from a set of random-valued alternatives-the "boxes"-when evaluation is costly. Weitzman showed that the Pandora's Box problem admits a simple threshold-based solution that considers the options in decreasing order of reservation value, a proxy for the actual value of the boxes in the exploration process. We study for the first time this problem when the order in which the boxes are opened is constrained, forcing the solution to account for both the depth of search, as opening a box gives access to more boxes, and the breadth, as there are many directions to explore. Despite these difficulties, we show that greedy optimal strategies exist and can be efficiently computed for tree-like order constraints. We also prove that finding optimal adaptive search strategies is NP-hard to approximate (up to a certain constant) when certain matroid constraints are applied to further restrict the set of boxes that may be opened or when the order constraints are given as reachability constraints on a directed acyclic graph. We complement this hardness result by giving efficient approximation algorithms, exploiting a low adaptivity gap for a carefully relaxed version of the problem.

Pandora's Box Problem with Order Constraints / Boodaghians, S; Fusco, F; Lazos, Filippos; Leonardi, S. - In: MATHEMATICS OF OPERATIONS RESEARCH. - ISSN 0364-765X. - 48:1(2023), pp. 498-519. [10.1287/moor.2022.1271]

Pandora's Box Problem with Order Constraints

Boodaghians, S;Fusco, F;Lazos, Filippos;Leonardi, S
2023

Abstract

The Pandora's Box problem, originally posed by Weitzman in 1979, models selection from a set of random-valued alternatives-the "boxes"-when evaluation is costly. Weitzman showed that the Pandora's Box problem admits a simple threshold-based solution that considers the options in decreasing order of reservation value, a proxy for the actual value of the boxes in the exploration process. We study for the first time this problem when the order in which the boxes are opened is constrained, forcing the solution to account for both the depth of search, as opening a box gives access to more boxes, and the breadth, as there are many directions to explore. Despite these difficulties, we show that greedy optimal strategies exist and can be efficiently computed for tree-like order constraints. We also prove that finding optimal adaptive search strategies is NP-hard to approximate (up to a certain constant) when certain matroid constraints are applied to further restrict the set of boxes that may be opened or when the order constraints are given as reachability constraints on a directed acyclic graph. We complement this hardness result by giving efficient approximation algorithms, exploiting a low adaptivity gap for a carefully relaxed version of the problem.
2023
Pandora's Box problem; Gittins' index; optimal exploration; stopping theory
01 Pubblicazione su rivista::01a Articolo in rivista
Pandora's Box Problem with Order Constraints / Boodaghians, S; Fusco, F; Lazos, Filippos; Leonardi, S. - In: MATHEMATICS OF OPERATIONS RESEARCH. - ISSN 0364-765X. - 48:1(2023), pp. 498-519. [10.1287/moor.2022.1271]
File allegati a questo prodotto
Non ci sono file associati a questo prodotto.

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/1684341
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 1
  • ???jsp.display-item.citation.isi??? 0
social impact