arXiv:2509.05956 · v5

Pandora's Knapsack via Simple Policies

首次提交 2025-09-07 15:44

版本更新 2026-11-10 21:46

雷达观测 2026-11-11 13:08

摘要

We introduce Pandora's Knapsack: a hybrid of the classic stochastic knapsack [Dean, Goemans, and Vondr'ak, 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. A motivating application from contract design is knapsack contracts, where a principal sequentially delegates jobs with stochastic processing times to agents before a deadline, and must pay each agent to incentivize effort, even if the job ends up not completing in time. 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, compared to the classic stochastic knapsack and Pandora's box, policies in our model must be significantly more complex along both axes to be approximately optimal. Conversely, we show that with full distributional information and by 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 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.