Pandora’s Box Problem Over Time

The Pandora’s Box problem models the search for the best alternative when evaluation is costly. In its simplest variant, a decision maker is presented with n boxes, each associated with a cost of inspection and a distribution over the reward hidden within. The decision maker inspects a subset of these boxes one after the other, in a possibly adaptive ordering, and obtains as utility the difference between the largest reward uncovered and the sum of the inspection costs. While this version of the problem is well understood (Weitzman 1979), there is a flourishing recent literature on variants of the problem. In this paper, we introduce a general framework—the Pandora’s Box Over Time problem—that captures a wide range of variants where time plays a role, e.g., as it might constrain the schedules of exploration and influence both costs and rewards. In our framework, each box is characterized by time-dependent rewards and costs, and inspecting it might require a box-specific processing time. Once a box is inspected, its reward may deteriorate over time, possibly differently for each box. Our main result is an efficient 21.3-approximation to the optimal strategy, which generally is NP-hard to compute. We further obtain improved results for the natural special cases where boxes have no processing time or when costs and reward distributions are time-independent (but rewards may deteriorate after inspecting).