Research map / Learning theory and algorithms / Submodular and game algorithms
Pandora’s Problem with Deadlines
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Introduces Pandora's problem with per-box deadlines and time slots and gives an efficient threshold-based strategy achieving a constant (about 0.15) approximation to the optimal expected utility.
Problem
Optimal sequential search under costly inspection (Pandora's problem) when each box has a publicly known deadline after which it can no longer be chosen, or a set of allowed inspection time slots; Weitzman's greedy rule fails in this setting.
Approach
Restrict exploitation to always taking the last-seen reward so deadlines only constrain exploration order; show feasible inspection sets form a transversal matroid, use submodular maximization under a matroid plus adaptivity-gap and prophet-inequality arguments to pick a feasible set, its order, and a threshold.
Key results
- Efficient threshold strategy achieves a (e-1)/(4e-ε) ≈ 0.15 approximation to optimal expected utility for Pandora's problem with deadlines (Corollary 1).
- Same 0.15-approximation extends to the more general Pandora's problem with time slots (Theorem 1).
- Example shows the deadline-constrained optimum can be strictly smaller than the sequence-constrained and set-constrained relaxations (e.g., 10 vs 54/5 vs 55/5).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use an efficient threshold-based strategy with a feasible box ordering | Pandora’s Problem with Deadlines · Pandora’s Problem with Deadlines | approximation ratio: 0.15-approximation | Helped |
| Use an efficient threshold-based strategy with a feasible box ordering | Pandora’s Problem with Time Slots · Pandora’s Problem with Time Slots | approximation ratio: 0.15-approximation | Helped |
Surprising findings
- Weitzman's optimal greedy rule does not extend to deadlines, and deadlines can make the optimum strictly lower than relaxed versions of the problem.
Limitations
- Approximation factor of about 0.15 is a loose constant and is not claimed to be tight
- Requires an exp-max oracle, which is exact only for polynomially supported distributions and otherwise estimated via sampling
Experimental setup
Metrics: expected utility approximation ratio
Baselines: Weitzman's rule (not applicable) optimal strategy under deadlines (exact DP)
Builds on: Weitzman's Pandora's problem Esfandiari et al. 2019 online Pandora's box Singla 2018 price of information Vondrak 2008 continuous greedy Bradac, Singla, Zuzic 2019 adaptivity gap
Closest papers by meaning
- Contextual Pandora’s Box (AAAI 2024 · similarity 0.84)
- Pandora's AI Model Routing Box: Efficient Allocation with Costly Value Estimation (NeurIPS 2026 · similarity 0.83)
- Cost-aware Bayesian Optimization via the Pandora's Box Gittins Index (NeurIPS 2024 · similarity 0.82)
- Improved Regret and Contextual Linear Extension for Pandora's Box and Prophet Inequality (NeurIPS 2025 · similarity 0.79)
- Delay as Payoff in MAB (AAAI 2025 · similarity 0.79)
- Welfare, Improvability, and Variance: A Principal-Agent Approach to Optimal Benchmark Item Aggregation (NeurIPS 2026 · similarity 0.78)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.