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

Weitzman (1979) introduced the Pandora's 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. Doval (2018) studied a version of Pandora's problem that allows this, and showed that the index-based policy and various other simple policies are no longer optimal. Beyhaghi and Kleinberg (2019) gave the first non-trivial approximation algorithm for the problem, showing a simple policy with expected payoff at least a $(1 - \frac 1 e)$-fraction that of the optimal policy. 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 scheme that computes policies with an expected payoff at least $(0.8 - \epsilon)$-fraction of the optimal, for arbitrarily small $\epsilon > 0$.