TY - JOUR
AU - Berger, Ben
AU - Ezra, Tomer
AU - Feldman, Michal
AU - Fusco, Federico
PY - 2024/03/24
Y2 - 2024/09/07
TI - Pandora’s Problem with Deadlines
JF - Proceedings of the AAAI Conference on Artificial Intelligence
JA - AAAI
VL - 38
IS - 18
SE - AAAI Technical Track on Reasoning under Uncertainty
DO - 10.1609/aaai.v38i18.30015
UR - https://ojs.aaai.org/index.php/AAAI/article/view/30015
SP - 20337-20343
AB - Pandora’s problem is a fundamental model that studies optimal search under costly inspection. In the classic version, there are n boxes, each associated with a known cost and a known distribution over values. A strategy inspects the boxes sequentially and obtains a utility that equals the difference between the maximum value of an inspected box and the total inspection cost. Weitzman (1979) presented a surprisingly simple strategy that obtains the optimal expected utility.In this work we introduce a new variant of Pandora’s problem in which every box is also associated with a publicly known deadline, indicating the final round by which its value may be chosen. This model captures many real-life scenarios where alternatives admit deadlines, such as candidate interviews and college admissions. Our main result is an efficient threshold-based strategy that achieves a constant approximation relative to the performance of the optimal strategy for the deadlines setting.
ER -