Local Hedging Algorithm for PNOI
Our reading group covered this paper today: Local hedging approximately solves Pandora’s box problems with nonobligatory inspection Ziv Scully and Laura Doval (2025) | Link: https://arxiv.org/pdf/2410.19011 Abstract: We consider search problems with nonobligatory inspection and single-item or combinatorial selection. A decision maker is presented with a number of items, each of which contains an unknown price, and can pay an inspection cost to observe the item’s price before selecting it. Under single-item selection, the decision maker must select one item; under combinatorial selection, the decision maker must select a set of items that satisfies certain constraints. In our nonobligatory inspection setting, the decision maker can select items without first inspecting them. It is well-known that search with nonobligatory inspection is harder than the well-studied obligatory inspection case, for which the optimal policy for single-item selection (Weitzman, 1979) and approximation algorithms for combinatorial selection (Singla, 2018) are known. ...

