optDUS
def
The optimal expected net utility optDUS inst under deferred-until-stopping commitment for a Pandora's problem instance with deadlines inst : PandoraDeadlineInstance, defined as the supremum of expectedUtilityDUS inst π over all valid adaptive policies π : AdaptivePolicy inst.n satisfying IsValidPolicy inst π.
Statement
noncomputable def optDUS (inst : PandoraDeadlineInstance) : ℝ
- Defined in
- arXiv:2610.13775 Sec. 2.1
- Verified
- 18 Oct 2026
- Axioms
- none listed
- Built on 4
- expectedUtilityDUSThe expected net utility of an adaptive policy
π : AdaptivePolicy inst.nunder deferred-until-stopping commitment on a Pandora's problem… - IsValidPolicyA policy is valid for a Pandora's problem instance with deadlines if it respects opening deadlines and never opens any box more than once.
- 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…
- expectedUtilityDUSThe expected net utility of an adaptive policy
- Used by 7
- 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. - 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… - op182_deferred_to_deadline_beyond_half_against_stoppingRefutation of Open Problem OP-182 against the deferred-until-stopping benchmark: there does not exist any constant
c > 1/2such that for… - 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π…
- opt_dus_nonnegFor any Pandora deadline instance
Read back from the Lean
Given an instance inst : PandoraDeadlineInstance, optDUS inst is defined as the supremum (⨆) in ℝ of expectedUtilityDUS inst π over all policies π : AdaptivePolicy inst.n satisfying IsValidPolicy inst π.
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
/-- Optimal expected net utility over all valid adaptive policies under deferred-until-stopping commitment (benchmark OPT). -/ noncomputable def optDUS (inst : PandoraDeadlineInstance) : ℝ := ⨆ (π : AdaptivePolicy inst.n) (_ : IsValidPolicy inst π), expectedUtilityDUS inst π