# pandoras_problem_with_deadlines__e2f8563e.pdf

Pandora s Problem with Deadlines

Ben Berger1, Tomer Ezra2, Michal Feldman3,4, Federico Fusco5

1 Offchain Labs, Inc. 2 Simons Laufer Mathematical Sciences Institute 3Tel Aviv University 4 Microsoft ILDC 5Department of Computer, Control and Management Engineering Antonio Ruberti , Sapienza University of Rome

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 thresholdbased strategy that achieves a constant approximation relative to the performance of the optimal strategy for the deadlines setting.

Introduction Pandora s problem, introduced in a seminal paper by Weitzman (1979), models the search for a good alternative among different options, under costly evaluation. An instance of the problem consists of n boxes, each hiding some reward drawn from a known and independent distribution. Each box also comes with a known evaluation cost. In the original variant, the decision maker opens the boxes sequentially in any desired order (which may be adaptive), until she decides to halt. The goal is to maximize the obtained utility, which is the maximum observed value across all opened boxes, minus the sum of their costs. This captures many real-life scenarios such as interviewing job candidates and choosing colleges, where the decision-maker has to balance between the need to explore many options in order to guarantee a good result, and to minimize the total exploration cost. Remarkably, Weitzman provided a simple and efficient strategy which obtains the optimal expected utility. The original model described above assumes that all rewards are available throughout the entire procedure. However, this may not necessarily be the case in practice, as some alternatives might become unavailable at some point in time. For instance, job candidates might eventually defer to other

Copyright 2024, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved.

employment opportunities if the recruiter took too long to offer them the job. Motivated by such applications, in this work we introduce a variant of Pandora s problem where each box, in addition to its cost and value distribution, is also associated with a known deadline, after which it is no longer available. This constraint complicates the problem significantly, as it limits the exploration orders that can be chosen by the decision maker. Furthermore, it may introduce interference between boxes that are otherwise compatible. For instance, suppose there are two favorable candidates that an employer would have liked to interview one after the other, but both of them are available only in the very next time slot. Weitzman s solution would not work in this case, as the employer must choose only one of them to interview.

Our results. While Weitzman s algorithm is not applicable in our model, we devise a simple strategy that attains a constant approximation to the optimal utility attainable by any algorithm. Result 1 (see Corollary 1). There is an efficient algorithm that achieves a 0.15-approximation to the optimal expected utility in Pandora s Problem with Deadlines. We further show how to generalize this result to the more restricted time slots setting where in addition to the exploitation deadline, each box is also associated with the set of time slots in which it is allowed to be inspected. Result 2 (see Theorem 1). There is an efficient algorithm that achieves a 0.15-approximation to the optimal expected utility in Pandora s Problem with Time Slots. Our results add to a large body of work that studies Pandora s problem under different restrictions on exploration and exploitation (see Related Work).

Technical Challenges and Techniques. Solving Pandora s problem entails finding a balance in the well known exploration-exploitation dilemma: inspecting new boxes is costly, but may offer the opportunity to collect better reward. The presence of deadlines and time slots imposes extra constraints on the order in which boxes can be opened, as well as on the reward collection process. For instance, continuing the exploration process may impede the decision maker to collect some very good observed reward whose deadline is close. To address the last challenge, we focus on strategies

The Thirty-Eighth AAAI Conference on Artiﬁcial Intelligence (AAAI-24)

that always take the reward that was seen last. This allows us to treat the deadlines only as a constraint to the order of exploration, and not on the exploitation. Then, we make the crucial observation that the family of sets of boxes for which there exists a feasible exploration order forms a transversal matroid. This allows us to exploit adaptivity gap results for submodular maximization (Bradac, Singla, and Zuzic 2019), and find a feasible subset of the boxes S that admits the following property: there exists a strategy that commits in advance to opening only boxes in S without sacrificing more than a constant fraction of the optimal utility. Furthermore, S admits a threshold such that for any ordering of it, selecting the first box that exceeds this threshold attains a constant approximation to the optimal utility. Finally, we compute this threshold (using techniques from Esfandiari et al. 2019) and the feasible ordering which exists by definition, and this defines our strategy.

Related Work. The two works closest to ours are Singla (2018) and Esfandiari et al. (2019). Singla (2018) considers a variant of Pandora s problem that constrains the set of boxes that can be opened and selected, and offers constant factor approximation algorithms for many natural classes of downward closed constraints. Note that these constraints apply only to the set of boxes that can be opened, and not the order in which they can be opened. Esfandiari et al. (2019) study an online version of Pandora s problem where the boxes have to be considered online, one after the other in some predetermined order. Once a box arrives, the decision maker chooses whether to open it (and possibly halt and take its realized reward), or discard it forever. Their model is strictly subsumed by ours, as it coincides with the special case of disjoint time slots but does not capture (natural) situations where the decision maker has some freedom in choosing the order of exploration (still respecting deadline constraints). Weitzman s seminal paper has given rise to many natural variants of Pandora s Problem that have been investigated over the years: non-obligatory inspection (Doval 2018; Beyhaghi and Kleinberg 2019; Beyhaghi and Cai 2023; Fu, Li, and Liu 2023), precedence constraints (Boodaghians et al. 2023), commitment constraints (Fu, Li, and Xu 2018; Segev and Singla 2021), interdependent valuations (Chawla et al. 2020, 2023), and combinatorial costs (Berger et al. 2023). Finally, Pandora s problem has also been studied from the learning perspective, both in the sample complexity framework (Guo et al. 2021), and in online learning (Gergatsouli and Tzamos 2022; Gatmiry et al. 2022).

Model and Preliminaries In Pandora s problem there are n boxes, each containing a hidden random variable Vi which is drawn from a distribution Xi. These distributions are independent, nonnegative and publicly known. Each box is also associated with a known cost ci R 0. The reservation value of a box i, denoted ri, is the number that satisfies the equation E [(Vi ri)+] = ci, where the expectation is with respect to the variables Vi, which are drawn from Xi, and we use the notation ( )+ to denote max( , 0). The notion of reserva-

tion value is the crucial ingredient for Weitzman s rule: the simple greedy strategy that is optimal for the original version of Pandora s problem (Weitzman 1979). The rule works as follows: it opens boxes in decreasing order of reservation value, and stops when the reservation value of the next box is smaller than the largest reward experienced so far (or there is no other box left).

Pandora s Problem with Deadlines. We introduce a variant of Pandora s problem where each box i is also associated with a known deadline di N, indicating the final time point by which it can be chosen. Formally, an instance to the problem is denoted by I = (Xi, ci, di)i [n]*, including all available information, namely, the box distributions, costs and deadlines. A strategy π for I opens the boxes in a sequential manner, revealing the hidden values inside. At each round t (starting from the first round t = 1), the strategy may choose to open any unopened box i, or otherwise the strategy may choose to halt. We say that a box is expired at a given round t if its deadline has passed before that round, i.e., di < t. Otherwise, we say that the box is active. The utility attained is the expected difference between the largest observed value of a box that is active at the last round of the process i.e., upon halting (or 0 if no such box exists), and the sum of the costs of all opened boxes. The strategy may be adaptive, i.e., the decisions at each round may depend on the values observed along the procedure. Note that the classic Pandora s problem introduced by Weitzman (i.e., without deadlines) is a special case of our setting where di = n for every box i, but that the greedy solution based on reservation value does not work, as it does not capture the central notion of deadlines. Given a strategy π for I, we introduce the following notation:

S(π) denotes the (random) ordered tuple of boxes opened by π. V (π) denotes the maximum value of an active box observed by π: V (π) = max i S(π), |S(π)| di

We also refer to this value as the reward obtained by π.

u(π) = E [V (π)] E h P i S(π) ci i denotes the expected utility (i.e., value minus cost) achieved by π.

Note that the quantities defined above depend on both the given instance and the strategy. Since only active boxes can be chosen, we may assume without loss of generality that strategies inspect only boxes that are active in the corresponding round.

Pandora s Problem with Time Slots. It is possible to further generalize the deadline model to scenarios where each box has a feasible set of rounds (not necessarily contiguous) at which it is available for exploration. This captures many real-life scenarios such as interviewing job candidates,

*For any positive integer x, we denote with [x] the set of the first x numbers: [x] = {1, . . . , x}

The Thirty-Eighth AAAI Conference on Artiﬁcial Intelligence (AAAI-24)

where each employee has a set of days when she is available for the interview. Formally, there are m days, and n boxes, where each box i, in addition to having a deadline di, a hidden value Vi Xi, and an inspection cost ci, has a set of feasible days Ti [m]. An instance of Pandora s Problem with Time Slots is then characterized as follows: I = (Xi, ci, di, Ti)i [n]. Each day t = 1, . . . , m, the decision-maker can choose one box i such that t Ti (i.e., the box is available for exploration on this day) or she can skip inspecting a box at that day. If the decision-maker chooses to open some box i then the cost ci is incurred, and Vi is observed. For any strategy π it is possible to define, similarly to what is done for the deadline model, the ordered tuple of opened boxes S(π), the maximium value V (π), and the decision-maker s utility u, which is the maximum observed value that did not expire minus the sum of the inspection costs. This new model is more general than the previous one, as deadlines are captured by setting m = n, and Ti = [n] for every box i.

Efficiency. It is clear that both new versions of Pandora s Problem can be solved exactly by exponential time algorithms via dynamic programming; therefore our goal is to find algorithms that are efficient and provide expected utility that at least approximates the one achievable by the optimal strategy. To simplify the analysis of our algorithms, we assume access to an exp-max oracle that, given in input a set of boxes S, outputs the expected maximum of the random variables min{Vi, ri} for i S. When the support of the distributions is polynomially supported, this expected maximum can be computed directly, while in general it can be estimated via sampling (we refer to Guo et al. (2021) for further details on how sample-based discrete distributions can be used to approximate continuous ones in our setting).

Submodular Optimization and Matroid Constraints. An important ingredient for our analysis is submodular maximization subject to matroid constraints. We report here some of the basic definitions and relevant results; we refer the interested reader to Part IV of Schrijver et al. (2003) for further details. A pair (E, M) is called a matroid if E is a finite set and M is a nonempty collection of subsets of S satisfying the following two properties: (Downward-closure) If S M and T S, then T M (Exchange property) If S, T M and |T| < |S|, then T {x} M, for some x S \ T. Example 1 (Transversal Matroids). Starting from a bipartite graph G = (L, R; E), it is possible to construct a matroid (L, M) on the left nodes L as follows: S L belongs to M if there exists a matching in G such that S constitutes the endpoints of the matching in L. A set function f : 2E R 0 is submodular if, for any subsets T S E and element x / S, the following inequality holds: f(S {x}) f(S) f(T {x}) f(T). A set function is monotone (with respect to inclusion), if for any subsets T S E it holds that f(T) f(S). The state-of-the-art for monotone submodular maximization subject to a matroid constraint is an algorithm by Vondr ak

(2008) which combines a continuous greedy approach with the pipage rounding technique; we report here its properties.

Lemma 1 (Vondr ak 2008). For every monotone submodular function f defined on a base set E, and for every matroid (E, M) and precision constant ε (0, 1), there exists an efficient randomized algorithm that finds a set S M such that E[f( S)] (1 1/e ε)f(S ), where S = arg max S M f(S).

The running time of a submodular optimization algorithm is typically measured in terms of the calls to two specific oracles: the value oracle (which returns the value f(S) on given set S) and the independence oracle (which returns whether S E belongs to M). The algorithm in Vondr ak (2008) is efficient as it issues a number of oracle calls that is polynomial in 1/ε and in the cardinality of the base set E.

Set and sequence constraints. Pandora s problem with deadlines or time slots imposes constraints on the boxes that may be chosen by an algorithm. In what follows, we introduce relaxations of the two models which are used in our analysis. These relaxations impose restrictions only on the time at which boxes can be inspected, but not on the time at which they can be chosen, as in the deadlines or time slots models. Hence, in the models presented below, the value obtained from a strategy is the maximum value of an inspected box, as in Weitzman s original model. We first make a distinction between a sequence constraint and a set constraint. A sequence constraint is a collection of valid tuples of boxes, namely, a collection of inspection orderings that a strategy may undertake. A set constraint is a collection of valid sets of boxes (that does not take into account the inner ordering of the boxes). We say that a sequence constraint F is prefix-closed if for any tuple (i1, . . . , ik) F and any j = 0, 1, . . . , k we have (i1, . . . , ij) F. A set constraint F is downward-closed if for any set S F and any subset T S we have T F. The main sequence constraint that we consider in this work is EXP-SEQ, where inspection times respect the boxes deadlines and the time slots constraints (if any). Formally, it is defined by

t=0 {(i1, . . . , it) | j Tij [dij] j [t]}.

Given a sequence (respectively, set) constraint F, we say that a tuple (resp., set) of boxes S is feasible under F if S F. A strategy π is consistent with a constraint F, if S(π) F with probability 1.

We denote by EXP-SET the set constraint induced by EXP-SEQ. In other words, a set of boxes S is feasible under EXP-SET if there exists some ordering of S which is compatible with the given deadlines and possibly time slots, i.e., some ordering of S which is in EXP-SEQ. The following lemma shows that EXP-SET is a transversal matroid.

Lemma 2. EXP-SET is a transversal matroid constraint.

In the case that F is a set constraint, S(π) although technically a tuple is interpreted as the corresponding set.

The Thirty-Eighth AAAI Conference on Artiﬁcial Intelligence (AAAI-24)

Proof. Consider the following bipartite graph, where the vertices on the left are the boxes, and the vertices on the right are the integers 1, . . . , m. Each box i has edges to times {1, . . . , di} Ti. A subset of boxes S is feasible under EXP-SET, (i.e., there exists an inspection order compatible with the deadlines) if and only if the sub-graph induced by S admits a matching of cardinality |S|. Therefore, by definition, EXP-SET is a transversal matroid.

Given a constraint F, we denote by OPTF the performance of an optimal strategy for Pandora s problem with a feasibility constraint F, i.e., this is the highest utility attainable by a strategy consistent with F. Clearly, the TIMESLOTS constraint induced by the Pandora s problem with time slots is stronger than the corresponding EXP-SEQ constraint, which is in turn stronger than EXP-SET. Therefore, the following inequality follows:

OPTEXP-SET OPTEXP-SEQ OPTTIME-SLOTS (1)

The same holds for DEADLINE. The following example shows how Formula (1) may be strict even in the special case of deadlines. Example 2. Consider an instance of the Pandora s problem with deadlines composed by two boxes with deadlines d1 = 1, d2 = 2 and costs c1 = 2, c2 = 1. The first box has value V1 = 20 with probability 1/5 and value V1 = 10 otherwise. The second box has value V2 = 20 with probability 1/5 and value 0 otherwise. If we look at the sequence constraint, we note that it is not possible to open the box 1 after the box 2, therefore EXP-SEQ = { , (1), (2), (1, 2)}. On the contrary, it is possible to open the box 2 after box 1, thus the EXP-SET does not impose any actual constraint on the set of boxes that can be opened: EXP-SET = { , {1}, {2}, {1, 2}}. In other words, EXP-SET is equivalent to the original version of Pandora s problem. In the EXP-SEQ setting there is a small number of strategies to consider, as once box 2 is opened then box 1 cannot be opened afterwards due to its deadline. A straightforward calculation shows that the optimal strategy in the EXP-SEQ setting is to first open box 1, halt if V1 = 20 and open box 2 otherwise. The expected cost of this strategy is 2 + 4/5 = 14/5. The expected reward of this strategy is

5 Thus, the expected utility is OPTEXP-SEQ = (68 14)/5 = 54/5. On the other hand, if box 2 is opened first then there is clearly no point in opening box 1 in the second round. Therefore an optimal strategy for the DEADLINE setting will open only one box, and between opening just box 1 or box 2 the former is strictly better. We thus have

OPTDEADLINE = 20 1

5 2 = 10 < OPTEXP-SEQ.

As for the EXP-SET setting, since the deadlines do not impose any constraints, the optimal strategy for this setting is to follow Weitzman s rule which for this instance would be to first open box 2 and then open box 1 in case V2 is observed to be 0. Similarly to the calculations above, the expected utility for this strategy is

OPTEXP-SET = 55

5 > OPTEXP-SEQ

Our Algorithm In this section we present our main result: an efficient strategy for the Pandora s Problem with Time Slots which yields an expected utility that is a constant factor approximation to the optimal one. As a corollary, we obtain the same approximation guarantee for the simpler problem of deadlines. We achieve our approximation result using a threshold strategy. A threshold strategy for a generic instance I = (Xi, ci, di, Ti)i [n] of the Pandora s Problem with Time Slots is defined by a threshold τ, and a feasible inspection ordering σ = (i1, . . . , ik) for some k [n] (by convention, we introduce dummy boxes to model the choice of skipping turn without opening any box). Such a strategy opens boxes according to σ and stops when Vit τ, or after all boxes in σ have been opened. Note, σ is feasible if any time step j k falls before deadline dij and belongs to the admissible time slots Tij. Given an instance of the problem, we compute threshold τ and ordering σ in three steps:

Finding the right set of boxes. Start computing for each box i its reservation value ri, and define the random variable Yi = min{Vi, ri}. The function f that maps a set of boxes S [n] to the expected value of the maximum Yi in S is then well defined:

f(S) = E max i S Yi

It is an easy exercise to see that f is a monotone submodular set function over the set of boxes [n]. In the previous Section we showed that the set constraint EXP-SET is a transversal matroid over [n], so it is possible to find a subset ˆS of the boxes that is feasible and has good value (Lemma 1). It is possible to find ˆS efficiently as the value oracle for the submodular function f is provided by the exp-max oracle for the underlying random variables, while the independence oracle can be obtained via a maximum matching routine on the bipartite graph that defines the transversal matroid.

Finding the right order. We know that ˆS is a feasible solution according to EXP-SET, therefore it is possible to find an ordering ˆσ of the boxes that respects the EXP-SEQ family of constraints. The ordering ˆσ can be computed efficiently by reducing the problem to finding a perfect matching in a bipartite graph (one side will have the boxes, and the other side the time slots).

Finding the right threshold. Now that we have the (nonadaptive) sequence ˆσ according to which the boxes in ˆS will be opened, we need to find a stopping rule (in our case governed by a certain threshold ˆτ) that balances the explorationexploitation trade off, while taking into account the deadlines of the various boxes. This can be done by setting:

2E max i S {Yi} = 1

This choice draws inspiration from the literature on prophet inequalities, and has already been proposed in the Pandora s setting in Esfandiari et al. (2019). Note, ˆτ can be computed via a single call to the exp-max oracle.

The Thirty-Eighth AAAI Conference on Artiﬁcial Intelligence (AAAI-24)

Theorem 1. For any constant ε (0, 1), there exists a threshold strategy for the Pandora s Problem with Time Slots that can be computed efficiently and provides a e 1

4e ε -approximation to the optimal expected utility.

Proof. We have already argued that it is possible to compute a threshold ˆτ and order ˆσ in time that is polynomial in 1/ε and n; so we only need to prove the approximation guarantee. Recall, we denote with OPTTIME-SLOTS the expected utility guaranteed by the optimal strategy, while OPTEXP-SET is the expected utility achievable when the deadlines and time slots constraints are removed from the exploitation and only limit the feasible subset of boxes that can be explored. For convenience, we denote with ALG the expected utility of the threshold strategy with ˆσ and ˆτ. We know, by Equation (1), that the utility of the optimal strategy for the time slots problem is dominated by that achievable under the weaker EXP-SET constraints. So, as a first step in the analysis, we recall a result by Kleinberg and Kleinberg (2018) which relates OPTEXP-SET with a specific instance of the stochastic probing problem (Asadpour and Nazerzadeh 2016). In this latter problem, a decisionmaker faces the same set of boxes with the random values Y1, . . . , Yn that can be opened subject to the prefix-closed constraint EXP-SET, and her utility is the maximum observed value. At each round the decision maker can (adaptively) choose one box to open, as long as the feasibility constraint is satisfied. Let π be an optimal strategy for the above problem, and denote by S(π ) the random set of variables Yi which were probed by the algorithm, the following Lemma holds (we report the proof for completeness).

Lemma 3 (Kleinberg and Kleinberg 2018). The following inequality holds:

E max i S(π ){Yi} OPTEXP-SET.

Proof of Lemma 3. Let π be an optimal strategy for the Pandora s problem under inspection constraints EXP-SET, i.e., π achieves utility OPTEXP-SET. For every i [n], let Ii be the indicator function for box i being inspected by π, and let Ai be the indicator function for box i being chosen by π. Then OPTEXP-SET, the expected utility achieved by π equals:

i=1 Ai Vi Iici

i=1 Ai Vi Ii E (Vi ri)+ #

i=1 E [Ai Vi] E Ii(Vi ri)+

(Ii and Vi are independent)

i=1 E Ai Yi + Ai(Vi ri)+ Ii(Vi ri)+

i=1 E Ai Yi + Ii(Vi ri)+ Ii(Vi ri)+

(Ii = 0 implies Ai = 0)

i=1 E [Ai Yi] E max i S(π){Yi} ,

where the last inequality follows because only one box in S(π) is chosen. To conclude the proof we note that by definition of π (i.e., the adaptive strategy that maximizes Yi) we have E maxi S(π){Yi} E maxi S(π ){Yi} , concluding the proof.

Our focus has now shifted towards upper bounding this new quantity E maxi S(π ){Yi} . This optimization task is extremely challenging, as one needs to compare against all adaptive strategies, which may change the set of boxes to open according to the realized Yi. To overcome this issue, we lean on an elegant result by Bradac, Singla, and Zuzic (2019) that holds for general monotone submodular function (we are using the function f defined in Equation (2)), which bounds the the gap in performance between adaptive and non-adaptive strategies (the so-called adaptivity gap). As the proof of this result is involved and technical, we only report the statement.

Lemma 4 (Bradac, Singla, and Zuzic 2019). The following inequality holds:

max S EXP-SET E max i S {Yi} 1

2 E max i S(π ){Yi} .

We have proved in the previous Section that the family of constraints EXP-SET is a transversal matroid, so it is possible to apply the approximation guarantees of Lemma 1 for the submodular function f as in Equation (2) and the matroid constraint EXP-SET, to argue that the set ˆS output by continuous greedy enjoys the following property:

E max i ˆS {Yi} 1 1

e ε max S EXP-SET E max i S {Yi} .

(3) Let s recap what we achieved so far: starting from Lemma 3 and then with Lemma 4 and finally Equation (3), we proved that the expected utility of the optimal solution is close to the value of the submodular function f on ˆS. In the next step of the analysis we prove how the threshold strategy characterized by ˆσ and ˆτ manages to achieve an expected utility that is comparable with f( ˆS). This passage is analogous to what is done in the Prophet Pandora setting in Beyhaghi and Kleinberg (2019). Once the set of boxes ˆS is chosen, and the compatible ordering ˆσ is fixed, the crucial observation is that f( ˆS) = E maxi ˆS Yi is the performance of the prophet in the prophet inequality problem , therefore the following bound holds (we add our version of the proof for completeness):

Lemma 5 (Esfandiari et al. 2019). The following inequality holds:

2 E max i ˆS {Yi} .

In the prophet inequality problem, a decision-maker observes random variables given in some order, and needs to select one of them in an immediate and irrevocable manner. The goal is to maximize the chosen value.

The Thirty-Eighth AAAI Conference on Artiﬁcial Intelligence (AAAI-24)

Proof of Lemma 5. Consider the prophet inequality problem with random variables {Yi}i S that arrive in the given order ˆσ. It is well known (Kleinberg and Weinberg 2019) that the threshold algorithm with the above threshold ˆτ = 1/2E maxi S{Yi} achieves expected utility (with respect to the Yi) which is at least ˆτ. For each box i, the probability that ALG halts upon consideration of box i is exactly Pr(Yi ˆτ), the same as the corresponding probability with respect to the threshold algorithm for the prophet inequality problem. Therefore, to conclude the proof of the Lemma, it is enough to show that the utility obtained by ALG from each box i conditioned on that box being considered, denoted u(i), is at least as much as the conditional utility that the aforementioned prophet inequality threshold algorithm obtains from box i. Note that the latter equals E Yi I{Yi τ} = E min{Vi, ri} I{Yi τ} . Therefore, to finish the proof we establish the following inequality: u(i) E min{Vi, ri} I{Yi τ} (4) Assume that ALG considers box i in its execution. We first consider the case ri < τ. In this case, ALG does not open box i, implying that the utility achieved from that box is u(i) = 0. But in this case we also have I{Yi τ} = 0, implying in particular that E min{Vi, ri} I{Yi τ} = 0, and we are done. We now consider the case ri τ. Recall that in this case, upon considering box i, ALG inspects the box (incurring its cost), and stops and obtains the value Vi if Vi τ. Thus, in this case the utility u(i) is at least

E ci + Vi I{Vi τ}

= E E [max{Vi ri, 0}] + Vi I{Vi τ}

= E E [min{ri Vi, 0}] + Vi I{Vi τ}

= E min{ri Vi, 0} + Vi I{Vi τ}

= E min{ri Vi, 0} I{Vi τ} + Vi I{Vi τ}

= E (min{ri Vi, 0} + Vi) I{Vi τ}

= E min{ri, Vi} I{Vi τ}

= E min{Vi, ri} I{min{Vi,ri} τ}

The fourth and last equalities in the chain above hold since we are in the case ri τ.

We have all the ingredients to conclude the proof of the Theorem, as chaining the results in Lemmas 3 and 4, Inequality (3) and Lemma 5 yields the desired bound (together with rescaling the precision ε used in pipage rounding).

Since the Pandora s Problem with Deadlines is a special case of the Time Slots model, we have immediately the following Corollary. Note, the only difference in the algorithm is that the ordering ˆσ can be easily computed starting from the set of boxes ˆS by simply sorting them in increasing order of deadlines. Corollary 1. For any constant ε (0, 1), there exists a threshold strategy for the Pandora s Problem with Deadlines that can be computed efficiently and provides a e 1

4e ε - approximation to the optimal expected utility.

Discussion and Further Directions

In this paper we have introduced the Pandora s Problem with Deadlines and Time Slots, where each box is associated with a deadline and, possibly, with a subset of the time slots where the exploration is allowed. Carefully combining techniques from submodular maximization, stochastic probing and prophet inequalities we have constructed an efficient algorithm that is guaranteed to achieve at least a 0.15 fraction of the optimal utility. A natural open question is whether this approximation factor is tight for efficient algorithms or not. Since the three approximation steps in our approach are known in general to be tight, namely the factor (1 1/e) for submodular maximization, the adaptivity gap of 1/2 and the factor 1/2 for prophet inequalities, in order to improve on the 0.15 term a new possibly more direct approach is needed.

Acknowledgments

Ben Berger s work was done while being a Ph.D. student at Tel-Aviv University. Feldman and Berger received funding from the European Research Council (ERC) under the European Union s Horizon 2020 research and innovation program (grant agreement No. 866132), by an Amazon Research Award, and by the NSF-BSF (grant number 2020788), and by a grant from the Tel Aviv University Center for AI and Data Science (TAD). Federico Fusco is partially supported by ERC Advanced Grant 788893 AMDROMA Algorithmic and Mechanism Design Research in Online Markets , PNRR MUR project PE0000013FAIR , and PNRR MUR project IR0000013-So Big Data.it. Part of the work of Federico Fusco was done while visiting Michal Feldman at Tel Aviv University. This work was also partially supported by the National Science Foundation under Grant No. DMS-1928930 and by the Alfred P. Sloan Foundation under grant G-2021-16778, while Tomer was in residence at the Simons Laufer Mathematical Sciences Institute (formerly MSRI) in Berkeley, California, during the Fall 2023 semester.

References Asadpour, A.; and Nazerzadeh, H. 2016. Maximizing stochastic monotone submodular functions. Management Science, 62(8): 2374 2391. Berger, B.; Ezra, T.; Feldman, M.; and Fusco, F. 2023. Pandora s Problem with Combinatorial Cost. In EC, 273 292. ACM. Beyhaghi, H.; and Cai, L. 2023. Pandora s Problem with Nonobligatory Inspection: Optimal Structure and a PTAS. In STOC, 803 816. ACM. Beyhaghi, H.; and Kleinberg, R. 2019. Pandora s Problem with Nonobligatory Inspection. In EC, 131 132. ACM. Boodaghians, S.; Fusco, F.; Lazos, P.; and Leonardi, S. 2023. Pandora s Box Problem with Order Constraints. Mathematics of Operations Research, 48(1): 498 519. Bradac, D.; Singla, S.; and Zuzic, G. 2019. (Near) Optimal Adaptivity Gaps for Stochastic Multi-Value Probing.

The Thirty-Eighth AAAI Conference on Artiﬁcial Intelligence (AAAI-24)

In APPROX-RANDOM, volume 145 of LIPIcs, 49:1 49:21. Schloss Dagstuhl - Leibniz-Zentrum f ur Informatik. Chawla, S.; Gergatsouli, E.; Mc Mahan, J.; and Tzamos, C. 2023. Approximating Pandora s Box with Correlations. In APPROX/RANDOM, volume 275 of LIPIcs, 26:1 26:24. Schloss Dagstuhl - Leibniz-Zentrum f ur Informatik. Chawla, S.; Gergatsouli, E.; Teng, Y.; Tzamos, C.; and Zhang, R. 2020. Pandora s Box with Correlations: Learning and Approximation. In FOCS, 1214 1225. IEEE. Doval, L. 2018. Whether or not to open Pandora s box. Journal of Economic Theory, 175: 127 158. Esfandiari, H.; Hajiaghayi, M. T.; Lucier, B.; and Mitzenmacher, M. 2019. Online Pandora s Boxes and Bandits. In AAAI, 1885 1892. AAAI Press. Fu, H.; Li, J.; and Liu, D. 2023. Pandora Box Problem with Nonobligatory Inspection: Hardness and Approximation Scheme. In STOC, 789 802. ACM. Fu, H.; Li, J.; and Xu, P. 2018. A PTAS for a Class of Stochastic Dynamic Programs. In ICALP, volume 107 of LIPIcs, 56:1 56:14. Schloss Dagstuhl - Leibniz-Zentrum f ur Informatik. Gatmiry, K.; Kesselheim, T.; Singla, S.; and Wang, Y. 2022. Bandit Algorithms for Prophet Inequality and Pandora s Box. Co RR, abs/2211.08586. Gergatsouli, E.; and Tzamos, C. 2022. Online Learning for Min Sum Set Cover and Pandora s Box. In ICML, volume 162 of Proceedings of Machine Learning Research, 7382 7403. PMLR. Guo, C.; Huang, Z.; Tang, Z. G.; and Zhang, X. 2021. Generalizing Complex Hypotheses on Product Distributions: Auctions, Prophet Inequalities, and Pandora s Problem. In COLT, volume 134 of Proceedings of Machine Learning Research, 2248 2288. PMLR. Kleinberg, J. M.; and Kleinberg, R. 2018. Delegated Search Approximates Efficient Search. In EC, 287 302. ACM. Kleinberg, R.; and Weinberg, S. M. 2019. Matroid prophet inequalities and applications to multi-dimensional mechanism design. Games and Economic Behavior, 113: 97 115. Schrijver, A.; et al. 2003. Combinatorial optimization: polyhedra and efficiency, volume 24. Springer. Segev, D.; and Singla, S. 2021. Efficient Approximation Schemes for Stochastic Probing and Prophet Problems. In EC, 793 794. ACM. Singla, S. 2018. The Price of Information in Combinatorial Optimization. In SODA, 2523 2532. SIAM. Vondr ak, J. 2008. Optimal approximation for the submodular welfare problem in the value oracle model. In STOC, 67 74. ACM. Weitzman, M. L. 1979. Optimal search for the best alternative. Econometrica: Journal of the Econometric Society, 641 654.

The Thirty-Eighth AAAI Conference on Artiﬁcial Intelligence (AAAI-24)