Sequential Search with Acquisition Uncertainty

We study a variation of the classical Pandora's problem in which a decision-maker (DM) sequentially explores alternatives from a given set and learns their values while trying to acquire the best alternative. The variations in the model we study are (i) alternatives randomly become unavailable during exploration and (ii) the DM's ability to acquire a remaining alternative is uncertain and depends on a chosen offer price. Such acquisition uncertainties arise in many applications, including housing search, hiring problems, and e-commerce, but greatly complicate the search problem in that optimal policies retain all previously explored alternative values as part of the problem state, as opposed to only the highest explored value as in Pandora's rule. Our central insight is that despite the complexity that these acquisition uncertainties create, simple greedy policies based on static sequencing and a single threshold value enjoy strong performance guarantees. We develop such a class of policies and show how to compute them using a greedy algorithm whose worst-case run-time scales linearly (up to logarithmic factors) in the number of alternative types. We show that our policies (a) are asymptotically optimal in high multiplicity regimes with many alternatives and (b) obtain at least 1-1/e ≈ 63.2% of the optimal value under a broad set of conditions. Extensive numerical examples support this theory: we illustrate our policies on a variation of Pandora's problem with disappearing alternatives and housing search on models calibrated on data from the online brokerage Redfin. In these examples, our policies significantly outperform policies based on Pandora's rule