opt_dus_nonneg
theoremverified
For any Pandora deadline instance inst, 0 ≤ optDUS inst.
Statement
theorem opt_dus_nonneg (inst : PandoraDeadlineInstance) :
0 ≤ optDUS inst- Source
- step towards op184_partially_adaptive_beyond_half
- Verified
- 26 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 7
- expected_utility_dus_le_opt_dusFor any Pandora's problem instance with deadlines
instand any valid policyπ,expectedUtilityDUS inst π ≤ optDUS inst. - is_valid_policy_stopFor every Pandora's problem instance with deadlines
inst : PandoraDeadlineInstance, the policyAdaptivePolicy.stopsatisfies… - expected_utility_dus_stopFor any Pandora deadline instance
inst, the expected net utilityexpectedUtilityDUS inst AdaptivePolicy.stopis zero. - expectedUtilityDUSThe expected net utility of an adaptive policy
π : AdaptivePolicy inst.nunder deferred-until-stopping commitment on a Pandora's problem… - optDUSThe optimal expected net utility
optDUS instunder deferred-until-stopping commitment for a Pandora's problem instance with deadlines… - 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…
- expected_utility_dus_le_opt_dusFor any Pandora's problem instance with deadlines
- Used by 1
- 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…
Lean source view module on GitHub
/-- The optimal expected utility under deferred-until-stopping commitment is non-negative. -/ theorem opt_dus_nonneg (inst : PandoraDeadlineInstance) : 0 ≤ optDUS inst := by rw [← expected_utility_dus_stop inst] exact expected_utility_dus_le_opt_dus inst _ (is_valid_policy_stop inst)