# Pandora Box Problem with Nonobligatory Inspection: Hardness and Approximation Scheme

arXiv: https://arxiv.org/abs/2207.09545 · HTML: https://mlsanity.com/paper/2207.09545/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 19 Jul 2022.

## Built on by (most cited first, 5 of 5)

- [The Gittins Index: A Design Principle for Decision-Making Under Uncertainty](https://mlsanity.com/paper/2506.10872/) (2025)
- [Improved Regret and Contextual Linear Extension for Pandora's Box and Prophet Inequality](https://mlsanity.com/paper/2505.18828/) (2025)
- [Teaching Transformers to Solve Combinatorial Problems through Efficient Trial & Error](https://mlsanity.com/paper/2509.22023/) (2025)
- [Pandora's AI Model Routing Box: Efficient Allocation with Costly Value Estimation](https://mlsanity.com/paper/2608.20316/) (2026)
- [T-TAMER: Provably Taming Trade-offs in ML Serving](https://mlsanity.com/paper/2509.22992/) (2025)

## Abstract (arXiv)

Weitzman (1979) introduced the Pandora Box problem as a model for sequential search with inspection costs, and gave an elegant index-based policy that attains provably optimal expected payoff. In various scenarios, the searching agent may select an option without making a costly inspection. The variant of the Pandora box problem with non-obligatory inspection has attracted interest from both economics and algorithms researchers. Various simple algorithms have proved suboptimal, with the best known 0.8-approximation algorithm due to Guha et al. (2008). No hardness result for the problem was known. In this work, we show that it is NP-hard to compute an optimal policy for Pandora's problem with nonobligatory inspection. We also give a polynomial-time approximation scheme (PTAS) that computes policies with an expected payoff at least (1 - ε)-fraction of the optimal, for arbitrarily small ε > 0. On the side, we show the decision version of the problem to be in NP.