expectedUtilityDUS
The expected net utility of an adaptive policy π : AdaptivePolicy inst.n under deferred-until-stopping commitment on a Pandora's problem instance with deadlines inst : PandoraDeadlineInstance. Evaluated recursively starting with an empty history: upon opening a box b, the box cost inst.cost b is subtracted and the expectation over the realized values v in the support of (inst.dist b) of continuing with (b, v) :: history is taken; upon stopping, the policy receives the maximum realized value among all opened boxes in the history (or 0 if empty).
Statement
noncomputable def expectedUtilityDUS (inst : PandoraDeadlineInstance) (π : AdaptivePolicy inst.n) : ℝ
- Defined in
- arXiv:2610.13775 Sec. 2.1
- Verified
- 18 Oct 2026
- Axioms
- none listed
- Built on 3
- PandoraDeadlineInstanceAn instance of Pandora's problem with deadlines consisting of n boxes, each with a non-negative opening cost, a positive integer deadline,…
- AdaptivePolicyA fully adaptive search policy for Pandora's problem with n boxes, represented as a decision tree that at each step either stops or opens…
- DiscreteDistA discrete probability distribution with finite support on non-negative real values, defined by a finite support set, non-negative…
- Used by 20
- optDUSThe optimal expected net utility
optDUS instunder deferred-until-stopping commitment for a Pandora's problem instance with deadlines… - opt_dus_nonnegFor any Pandora deadline instance
inst,0 ≤ optDUS inst. - expected_utility_dus_le_opt_dusFor any Pandora's problem instance with deadlines
instand any valid policyπ,expectedUtilityDUS inst π ≤ optDUS inst. - pandora_is_reservationr is a vector of reservation values: for every box i, the expected excess E[(v_i - r_i)^+] of its value over r_i equals its opening cost…
- pandora_exists_deadline_orderLemma 2: a deadline-feasible set can be listed without repetition so that the j-th box (j from 1) has deadline at least j.
- expected_utility_dus_stopFor any Pandora deadline instance
inst, the expected net utilityexpectedUtilityDUS inst AdaptivePolicy.stopis zero. - two_box_pi01_dusThe DUS utility of the policy opening box 0 then box 1 is
2 - 1/M. - expected_utility_dtd_le_dusFor every Pandora's problem instance with deadlines
inst : PandoraDeadlineInstanceand every adaptive policy… - pandora_deadline_feasibleA set S of boxes is deadline-feasible if for every j at most j of its boxes have deadline at most j (equivalently, by Lemma 2, its boxes…
- opt_dtd_le_opt_dusFor every Pandora's problem instance with deadlines
inst : PandoraDeadlineInstance, the optimal expected utility under… - op184_partially_adaptive_half_approximationFor every Pandora's problem instance with deadlines
inst : PandoraDeadlineInstance, there exists a valid partially adaptive policy… - pandora_threshold_policy_lower_boundLemma 3: for reservation values r, t >= 0 and a duplicate-free list of boxes each with positive capped surplus at t, the threshold policy…
- pandora_adaptive_surplus_upper_boundLemma 1: for reservation values r and any threshold t >= 0, every valid adaptive policy has expected DUS utility at most t plus the total…
- pandora_capped_surplusThe reservation-capped threshold surplus of box i at threshold t: w_i(t) = E[(min(v_i, r_i) - t)^+].
- dus_approx_of_pos_optIf a constant factor approximation ratio c is achieved by partially adaptive policies on all instances with optDUS > 0, then it is…
- two_box_counterexample_familyFor any integer
M > 1, there exists a 2-box Pandora deadline instance such that2 - 1 / M ≤ optDUS instand every valid policyπ… - pandora_threshold_policyThe threshold policy on a list of boxes: open them in the given order and stop as soon as an opened value exceeds t (stop after the last…
- pandora_exists_reservationEvery Pandora instance with deadlines has reservation values: for every box i there is r_i with E[(v_i - r_i)^+] = c_i.
- pandora_exists_balancing_thresholdThere is a threshold t >= 0 at which the maximum total capped surplus over deadline-feasible sets equals t, attained by some feasible set.
- pandora_threshold_policy_validA threshold policy on a duplicate-free list whose j-th box has deadline at least j is a valid policy and is partially adaptive.
- optDUSThe optimal expected net utility
Read back from the Lean
Given an instance inst of PandoraDeadlineInstance (specifying a number of boxes n : ℕ, box opening costs cost : Fin n → ℝ, deadlines deadline : Fin n → ℕ, and discrete probability distributions dist : Fin n → DiscreteDist) and an adaptive policy π : AdaptivePolicy inst.n (a tree whose nodes either stop or open a box b : Fin inst.n and branch on the observed value v : ℝ to a continuation policy cont v), expectedUtilityDUS inst π is the real number computed by an auxiliary recursive function aux initialized with an empty history []:
- If the policy is .stop, it returns the maximum observed prize in history, or 0 if history is empty (computed via history.foldl (fun acc bv => max acc bv.2) 0).
- If the policy is .openBox b cont, it computes the sum over all values v in the finite support of inst.dist b of the probability (inst.dist b).prob v multiplied by the recursive utility aux ((b, v) :: history) (cont v), minus the opening cost inst.cost b.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
Lean source view module on GitHub
/-- Expected net utility of an adaptive policy under deferred-until-stopping commitment in Pandora's problem with deadlines. -/ noncomputable def expectedUtilityDUS (inst : PandoraDeadlineInstance) (π : AdaptivePolicy inst.n) : ℝ := aux [] π where aux (history : List (Fin inst.n × ℝ)) : AdaptivePolicy inst.n → ℝ | .stop => history.foldl (fun acc bv => max acc bv.2) 0 | .openBox b cont => (∑ v ∈ (inst.dist b).support, (inst.dist b).prob v * aux ((b, v) :: history) (cont v)) - inst.cost b