Local Hedging Approximately Solves Pandora's Box Problems with Optional Inspection

Local Hedging Approximately Solves Pandora's Box Problems with Optional Inspection (via Zoom)

Abstract: We consider Pandora's box search problems with optional 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 buy one item; under combinatorial selection, the decision maker must buy a set of items that satisfies certain constraints. In our optional inspection setting, the decision maker can buy items without first inspecting them. It is well known that search with optional inspection is harder than the well-studied mandatory inspection case, for which the optimal policy for single-item selection and approximation algorithms for combinatorial selection are known. 

We introduce a technique, called local hedging, for constructing policies with good approximation ratios in the optional inspection setting. Local hedging takes policies for the mandatory inspection setting and turns them into policies for the optional inspection setting. The cost of local hedging is an extra factor in the approximation ratio, which is instance-dependent but always at most 4/3. We thus obtain the first approximation algorithms for a variety of combinatorial selection problems in the optional-inspection setting, including matroid basis, matching, and facility location.
Joint work with Laura Doval (Columbia Business School).

Bio: Ziv Scully is an assistant professor at Cornell ORIE (Operations Research and Information Engineering). He obtained his BS from MIT in 2016 and completed his PhD in Computer Science at CMU in 2022. Between graduating from CMU and starting at Cornell, Ziv spent a year as a postdoc at the UC Berkeley Simons Institute, Harvard SEAS, and MIT CSAIL.
Broadly, Ziv researches the theory of decision making under uncertainty, including stochastic control, resource allocation, and performance evaluation. A particular emphasis of his work is scheduling and load balancing in queueing systems. Ziv’s work has been recognized by awards from INFORMS, ACM SIGMETRICS, and IFIP PERFORMANCE, including the 2022 SIGMETRICS Doctoral Dissertation Award.