Pandora's Box Problem with Order Constraints
28 Ottobre 2020 alle 14:30
Piattaforma Zoom: link: https://zoom.us/j/97138136702
Speaker: Federico Fusco
Referente: Nicolò Cesa-Bianchi
The Pandora's Box Problem, originally formalized by Weitzman in 1979, models selection from a set of random, alternative options, when evaluation is costly. This includes, for example, the problem of hiring a skilled worker, where only one hire can be made, but the evaluation of each candidate is an expensive procedure. Weitzman showed that the Pandora's Box Problem admits an elegant, simple solution, where the options are considered in decreasing order of reservation value, i.e., the value that reduces to zero the expected marginal gain for opening the box. We study for the first time this problem when order - or precedence - constraints are imposed between the boxes. We show that, despite the difficulty of defining reservation values for the boxes which take into account both in-depth and in-breath exploration of the various options, greedy optimal strategies exist and can be efficiently computed for tree-like order constraints. We also prove that finding approximately optimal adaptive search strategies is NP-hard when certain matroid constraints are used to further restrict the set of boxes which may be opened, or when the order constraints are given as reachability constraints on a DAG. We complement the above result by giving approximate adaptive search strategies based on a connection between optimal adaptive strategies and non-adaptive strategies with bounded adaptivity gap for a carefully relaxed version of the problem.
Joint work with: Shant Boodaghians, Philip Lazos, Stefano Leonardi. Appeared in the Proceedings of the 21st ACM Conference on Economics and Computation (EC '20).
Federico Fusco is a PhD student in Data Science at Sapienza Università di Roma. His research interests are Algorithmic Game Theory, Mechanism Design, Combinatorial and Stochastic Optimization.