AFTD Auto-Formalizing Theoretical Domains

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 inst and any valid policy π, expectedUtilityDUS inst π ≤ optDUS inst.
  • is_valid_policy_stopFor every Pandora's problem instance with deadlines inst : PandoraDeadlineInstance, the policy AdaptivePolicy.stop satisfies…
  • expected_utility_dus_stopFor any Pandora deadline instance inst, the expected net utility expectedUtilityDUS inst AdaptivePolicy.stop is zero.
  • expectedUtilityDUSThe expected net utility of an adaptive policy π : AdaptivePolicy inst.n under deferred-until-stopping commitment on a Pandora's problem…
  • optDUSThe optimal expected net utility optDUS inst under 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…
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)
See it in the graphDiscuss this resultChallenge it