Pandora Box Problem with Nonobligatory Inspection: Hardness and Improved Approximation Algorithms

Hu Fu, Jiawei Li, Daogao LiuarXiv 2022 · arXiv · OpenReview

Abstract

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 - \epsilon)$-fraction of the optimal, for arbitrarily small $\epsilon > 0$. On the side, we show the decision version of the problem to be in NP.

Introduction

In the classic Pandora’s Box Problem, an agent must decide the order in which to open boxes containing random rewards, paying a search cost for each inspection. Weitzman’s 1979 solution provided an elegant "index-based" strategy: assign every box a score, open them in descending order, and stop when a revealed value exceeds the scores of all remaining boxes.

However, real-world scenarios often allow for Non-obligatory Inspection (PNOI), where an agent can select an option without paying to see its contents (e.g., choosing a school or a wireless channel "blind"). This flexibility breaks the optimality of simple index policies. While previous research provided an 80% approximation, this paper settles the problem's complexity and provides a near-optimal approximation scheme.

Hardness and the Structure of Optimal Policies

The authors prove that PNOI is NP-hard by reducing the classical Partition Problem to a specific instance of PNOI. The reduction demonstrates that finding the optimal order to probe boxes is equivalent to determining if a set of integers can be split into two equal-sum subsets.

Figure 1: Visualization of the box sequence construction used to prove NP-hardness, showing the strategic ordering of boxes based on their indices (\tau).

As illustrated in Figure 1, the optimal policy follows a specific structure. It involves a sequence of boxes divided into those probed before ($T_{Bef}$) and after ($T_{Aft}$) a specific box $B_{n+1}$ with the lowest index. The agent acts as a hybrid: they start with a specific sequence (the "non-obligatory" part) but are ready to pivot to a standard index-based search the moment they find a "good enough" value. This "leap of faith" adds a layer of adaptivity that makes the problem computationally difficult.

Approximation via PTAS

To address the NP-hardness, the authors developed a Polynomial-Time Approximation Scheme (PTAS) that achieves a $(1 - \epsilon)$ approximation for any $\epsilon > 0$. This is a significant improvement over the previous 0.8-approximation.

The PTAS relies on a novel discretization method within a Stochastic Sequential Decision Process (SSDP) framework. Standard rounding fails for "large" values in this problem; the authors' method rounds revealed large values upward but treats un-opened boxes differently to maintain a tight error margin. They observed that once a very large value is found, the additional gain from further searching behaves like a well-behaved additive function, making it easier to approximate.

Key Insights

  • The Non-Exposed Property: The authors utilize this concept from search theory to derive a mathematical expression for the difference between a "normal" policy and the classic index policy, serving as the bridge for their hardness reduction.
  • Strategic Switching: Optimal agents are shown to follow a specific pattern: committing to a subset of boxes in a specific order until a threshold is met, then either taking a box blindly or reverting to Weitzman’s index-based search.
  • Complexity Class: Beyond hardness, the authors proved the decision version of the problem is in NP, meaning a given policy's performance can be verified efficiently.

Limitations and Future Work

The primary limitation of the PTAS is its computational cost. While polynomial in the number of boxes ($n$), the running time has an exponential dependence on $1/\epsilon$ (specifically $n^{2^{O(\epsilon^{-3})}}$). This makes it a theoretical tool rather than a practical one for high-precision real-time systems.

Future research may explore the existence of a Fully Polynomial-Time Approximation Scheme (FPTAS), where complexity grows more slowly relative to precision requirements. Additionally, the hardness gaps identified here may exist in other online decision problems, such as bipartite matching with search frictions.

Summary updated

Abstract

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 - \epsilon)$-fraction of the optimal, for arbitrarily small $\epsilon > 0$. On the side, we show the decision version of the problem to be in NP.
BibTeX
@misc{fu2022pandora,
  author = {Hu Fu and Jiawei Li and Daogao Liu},
  title = {{Pandora Box Problem with Nonobligatory Inspection: Hardness and Improved Approximation Algorithms}},
  year = {2022},
  eprint = {2207.09545},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2207.09545},
}
Figure