Pandora's Box Problem with Order Constraints

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.