AFTD Auto-Formalizing Theoretical Domains

dus_approx_of_pos_opt

theoremverified

If a constant factor approximation ratio c is achieved by partially adaptive policies on all instances with optDUS > 0, then it is achieved on all instances.

Statement

theorem dus_approx_of_pos_opt (c : ℝ)
    (h_pos : ∀ inst : PandoraDeadlineInstance, 0 < optDUS inst →
      ∃ π : AdaptivePolicy inst.n, IsValidPolicy inst π ∧ IsPartiallyAdaptive π ∧
        c * optDUS inst ≤ expectedUtilityDUS inst π)
    (inst : PandoraDeadlineInstance) :
    ∃ π : AdaptivePolicy inst.n, IsValidPolicy inst π ∧ IsPartiallyAdaptive π ∧
      c * optDUS inst ≤ expectedUtilityDUS inst π
Source
step towards op184_partially_adaptive_beyond_half
Verified
26 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 10
  • opt_dus_nonnegFor any Pandora deadline instance inst, 0 ≤ optDUS inst.
  • is_valid_policy_stopFor every Pandora's problem instance with deadlines inst : PandoraDeadlineInstance, the policy AdaptivePolicy.stop satisfies…
  • is_partially_adaptive_stopFor any natural number n, the policy AdaptivePolicy.stop : AdaptivePolicy n is partially adaptive (…
  • expected_utility_dus_stopFor any Pandora deadline instance inst, the expected net utility expectedUtilityDUS inst AdaptivePolicy.stop is zero.
  • PandoraDeadlineInstanceAn instance of Pandora's problem with deadlines consisting of n boxes, each with a non-negative opening cost, a positive integer deadline,…
  • 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.
  • 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…
  • IsPartiallyAdaptiveA search policy π : AdaptivePolicy n for Pandora's problem is partially adaptive if there exists a predetermined ordered list of boxes…
  • optDUSThe optimal expected net utility optDUS inst under deferred-until-stopping commitment for a Pandora's problem instance with deadlines…
  • expectedUtilityDUSThe expected net utility of an adaptive policy π : AdaptivePolicy inst.n under deferred-until-stopping commitment on a Pandora's problem…

Lean source view module on GitHub

/-- Reduction of approximation ratio guarantee to instances with strictly positive optDUS. -/
theorem dus_approx_of_pos_opt (c : ℝ)
    (h_pos : ∀ inst : PandoraDeadlineInstance, 0 < optDUS inst →
      ∃ π : AdaptivePolicy inst.n, IsValidPolicy inst π ∧ IsPartiallyAdaptive π ∧
        c * optDUS inst ≤ expectedUtilityDUS inst π)
    (inst : PandoraDeadlineInstance) :
    ∃ π : AdaptivePolicy inst.n, IsValidPolicy inst π ∧ IsPartiallyAdaptive π ∧
      c * optDUS inst ≤ expectedUtilityDUS inst π := by
  by_cases h : 0 < optDUS inst
  · exact h_pos inst h
  · have h0 : optDUS inst = 0 := by
      have := opt_dus_nonneg inst
      linarith
    use AdaptivePolicy.stop
    refine ⟨is_valid_policy_stop inst, is_partially_adaptive_stop inst.n, ?_⟩
    rw [expected_utility_dus_stop, h0, mul_zero]
See it in the graphDiscuss this resultChallenge it