Approximating Pandora's Knapsack via Simple Policies

Abstract

We introduce Pandora's Knapsack: a hybrid between the classic stochastic knapsack problem [Dean et al., 2008] and Pandora's box [Weitzman, 1979]. As in stochastic knapsack, items have sizes drawn from known distributions, and items that fit within a knapsack contribute to the total value. As in Pandora, every item $i$ comes in a box that costs $c_i$ to open. What distinguishes our problem is that the size is revealed only after opening the box and paying the cost. We study the power of simple decision-making policies to approximate Pandora's Knapsack, along two complexity axes: (i)~knowledge of size distributions, and (ii)~adaptivity. We show that adding costs to stochastic knapsack completely changes the algorithmic landscape, and policies must now be complex along both axes to be approximately-optimal. We complement these impossibilities by showing that with full distributional information and slightly more adaptivity---allowing adaptive skipping of items---a constant approximation can be recovered. Our analysis reveals an economic quantity, namely ROI (return-on-investment, defined as the jobs' minimum utility over cost), which smoothly characterizes the performance of simple policies. Across a hierarchy of increasingly adaptive policies, we establish near-tight adaptivity gaps all governed by ROI. To demonstrate the importance of the ROI parameter in characterizing simple policies, we revisit Pandora's Box, and show that return-on-investment exactly captures the adaptivity gap in this classic problem as well. As a corollary, we get that simple policies are approximately-optimal provided the ROI is sufficiently large.