Simple strategy achieves half the best possible value for deadline search
A $1/2$-Approximation for Pandora's Problem with Deadlines
Computer Science and Game Theory
Summary
Pandora's problem is about deciding which boxes to open when each box costs something and has a deadline before it must be opened or picked. The authors study this problem with deadlines and show that a simple rule, called a threshold strategy, gets at least half of the best possible expected benefit. This improves on the previous best known strategy, which only guaranteed about 16% of the optimal value. Their work helps understand how to make good decisions when searching through options under time limits.
What this means in practice
- •For supply chain planners: Schedule inspections or checks of inventory items with deadlines and costs to maximize operational efficiency using the improved threshold strategy.
- •For cloud resource schedulers: Allocate or release cloud resources with known deadlines and costs more effectively by applying the threshold-based approach to maximize expected utility.
Authors
Shenyu Qin, Chihao Zhang, Yuhao Zhang, Zixuan Zhu
Abstract
Pandora's problem is a fundamental model of sequential search in which opening each box incurs a cost. We study the variant with deadlines, where each box has a publicly known deadline for both opening and selection. We prove that a simple threshold strategy achieves a $1/2$-approximation to the optimal expected utility, improving the previous guarantee of $(e-1)/(4e)\approx0.158$ due to Berger et al. (AAAI 2024).