Is there a 1/2-approximation for Pandora's problem with deadlines?

What the 1/2 guarantee actually measures

Pandora's problem models sequential search among costly alternatives: each box holds an uncertain value from a known distribution, opening it costs a known amount, and the searcher decides when to stop and take the best opened value. In the deadline variant introduced by Berger et al., each box also has a publicly known deadline, and both opening and commitment must respect it. The objective is the value of the selected box minus the total opening cost.

The number 1/2 is a ratio between two expected utilities on the same instance. The lower side is what the paper's algorithm earns. The upper side, written OPT, is the best fully adaptive strategy with deferred-until-stopping commitment: it may choose the next box based on everything observed so far, and it may commit to any previously opened box even if that box's deadline has passed. Deadlines constrain only its openings. Because this benchmark is the most permissive of the three commitment rules the paper defines, a guarantee against it also holds against the fully adaptive optimum under deferred-to-deadline or immediate commitment.

That choice of benchmark matters for reading the result. The algorithm itself is deliberately weak in two ways: it is partially adaptive, fixing the set of boxes and their opening order before any value is observed, and it uses immediate commitment, accepting or discarding each box irrevocably the moment it is opened. The 1/2 is therefore earned by a restrictive policy against a permissive comparator, not by matching like with like.

Why Weitzman's rule breaks under deadlines

In the classical problem, Weitzman's rule is optimal. Each box gets a reservation value r_i defined by c_i = E[(v_i - r_i)^+], the opening cost equals the expected excess of the value over that threshold. The rule opens boxes in decreasing reservation-value order and stops once the best observed value reaches the largest reservation value among unopened boxes. The order is fixed in advance, but the stopping decision adapts to observed values.

Deadlines break the opening order. Opening one box can make another unavailable, so the order now determines not only costs and information but which options remain feasible. The paper gives a two-box instance where this failure is unbounded. Box 1 has deadline 1, box 2 has deadline 2, and box 2 has a slightly larger reservation value, so Weitzman's rule opens box 2 first. Box 1 can then no longer be opened, and if box 2 yields zero there is no fallback. The rule's expected utility is 1/N + 1/N^2, while opening box 1 first and committing immediately yields at least 1, so the ratio tends to zero as N grows.

The diagnosis is specific: the reservation-value order ignores deadlines, and deferred-until-stopping commitment cannot recover an unopened box whose deadline has passed. Any fix has to choose a feasible set and an order that respect deadlines, then decide how much of that set's value survives immediate commitment.

A direct bridge to prophet inequalities

The previous 0.158 guarantee came from chaining black-box reductions. Berger et al. related the deadline model to a prophet inequality through reservation-value identities, an adaptivity-gap bound contributing a factor of 1/2, and submodular maximization contributing 1 - 1/e, then invoked the classical prophet inequality for another factor of 1/2. Multiplying gives (1/2)·(1 - 1/e)·(1/2) = (e-1)/(4e) ≈ 0.158.

This paper replaces that chain with one object. For each box, cap its value at its reservation value, y_i = min{v_i, r_i}, and define the reservation-capped threshold surplus w_i(t) = E[(y_i - t)^+] for a threshold t. For a deadline-feasible set S, the benchmark is B_t(S) = t + sum over i in S of w_i(t). The surplus measures how much capped reward a box contributes above the threshold in expectation.

Two properties make this the whole argument. First, for every adaptive strategy that respects opening deadlines and every threshold t, expected utility is at most t + W(t), where W(t) is the maximum of the summed surpluses over deadline-feasible sets. The proof uses the fact that the decision to open a box is made before its value is seen, so the expected excess over the reservation value cancels exactly against the opening cost. Second, a simple threshold policy on a well-chosen set earns at least the minimum of t and W(t). Choosing t so the two are equal gives utility at least t and OPT at most 2t, hence the factor 1/2.

The intermediate losses are gone because the deadline structure is handled inside the surplus benchmark rather than through separate relaxations. The paper describes this as a white-box threshold-surplus analysis, in contrast to the earlier black-box composition.

Selecting a feasible set exactly in polynomial time

The benchmark requires maximizing total surplus over deadline-feasible sets, so the paper needs both a feasibility test and an optimization routine. Order a set by nondecreasing deadlines. The set is feasible if and only if the j-th box in that order has deadline at least j, since the j boxes with the smallest deadlines must occupy distinct rounds within the first d_ij rounds.

Maximizing total weight over feasible sets then becomes a dynamic program with O(n^2) state transitions. Sorting boxes by deadline, the state records the best weight for choosing exactly j boxes from the first i, and box i can be taken as the j-th selected box only when d_i ≥ j. Running this with weights w_i(t) computes W(t) and returns a maximizing set for each fixed threshold.

Finding the balancing threshold is also constructive. Since W is n-Lipschitz and the balancing point is at least W(0)/(n+1), binary search on [0, W(0)] needs O(log(n/ε)) iterations for a ratio of 1/2 - ε, assuming exact evaluations. For explicitly represented finite-support distributions, the exact threshold can be written as a linear program with O(M + n^2) variables and constraints, where M is the total number of support points, and solved exactly in polynomial time for rational inputs. The exact 1/2 guarantee therefore comes with an efficient procedure, not just an existence claim.

Half is tight for immediate commitment

The 1/2 is not an artifact of the analysis. The paper shows that no immediate-commitment policy, even a fully adaptive one, can beat 1/2 against the best partially adaptive strategy with deferred-until-stopping commitment. The construction simulates the classical tight example for prophet inequalities: two zero-cost boxes, the first with deadline 1 and value 1, the second with deadline 2 and value 1/ε with probability ε and 0 otherwise.

A partially adaptive strategy with deferred commitment opens both boxes and takes the larger value, earning 2 - ε in expectation. Any immediate-commitment policy earns at most 1: opening box 2 first precludes opening box 1 later, while opening box 1 first forces a choice between accepting 1 and continuing to a box whose expectation is also 1. The ratio is at most 1/(2 - ε), which tends to 1/2.

This pins the guarantee to the commitment rule rather than to the algorithm's simplicity. Within the immediate-commitment class, 1/2 is the ceiling; improving it requires relaxing how long an opened box stays available.

Partial adaptivity alone costs a factor of 0.778

A separate result isolates the cost of fixing the opening order. The paper constructs an instance with at least k boxes of each of two types, all with deadline k and zero opening cost, so at most k boxes can be opened. Type-1 boxes yield 1 with probability p_1 = 1/(λ_1 k); type-2 boxes yield k with probability p_2 = 1/(λ_2 k^2).

A partially adaptive strategy fixes its order in advance and, since opening is free, optimally opens exactly k boxes. Writing α for the fraction of type-1 boxes, its limiting utility is 1 - e^{-α/λ_1} + (1-α)/λ_2, maximized at α* = λ_1 ln(λ_2/λ_1). A fully adaptive policy instead opens type-1 boxes until it sees a 1, then spends the remaining rounds on type-2 boxes, which lets it exploit the timing of the first success.

With λ_1 = 0.513 and λ_2 = 1.541, the ratio of the limiting utilities is bounded below 0.77792, so for all sufficiently large finite k the partially adaptive optimum is strictly less than 0.778 times the fully adaptive optimum. No partially adaptive policy, even with unlimited computation, can guarantee more than 0.778. This is a separation from the classical problem, where Weitzman's partially adaptive rule is already optimal against fully adaptive policies; deadlines make partial adaptivity strictly weaker.

Where the open questions remain

The two bounds answer different questions and should not be combined into a single number. The 1/2 is tight for immediate-commitment policies against the deferred-until-stopping benchmark. The 0.778 is a ceiling on partially adaptive policies under deferred-until-stopping commitment, a more permissive commitment rule than the algorithm uses. Neither bound settles the best ratio achievable by efficient algorithms that use deferred-to-deadline commitment, which keeps an opened box selectable until its deadline and lets a policy gather more observations while retaining earlier options. Neither this algorithm nor Berger et al.'s exploits that flexibility.

The other open direction is full adaptivity in the opening order. The separation result shows that deadlines make partial adaptivity strictly weaker than full adaptivity, unlike the classical setting, so it is natural to ask whether efficient fully adaptive algorithms can beat 1/2 under a common deferred commitment rule.

The practical reading follows the same split. When evaluations must be scheduled in advance and each evaluation forces an accept-or-reject decision, the paper's partially adaptive, immediate-commitment policy delivers the 1/2 guarantee against the most permissive benchmark, and no policy in that class can do better. When the application can keep opened options alive until their deadlines, the 1/2 ceiling no longer applies, and the question of how much deferred commitment buys is left open.

Sources used in this answer