AFTD Auto-Formalizing Theoretical Domains

expected_utility_dus_stop

theoremverified

For any Pandora deadline instance inst, the expected net utility expectedUtilityDUS inst AdaptivePolicy.stop is zero.

Statement

theorem expected_utility_dus_stop (inst : PandoraDeadlineInstance) :
    expectedUtilityDUS inst AdaptivePolicy.stop = 0
Source
step towards op184_partially_adaptive_beyond_half
Verified
26 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 3
  • expectedUtilityDUSThe expected net utility of an adaptive policy π : AdaptivePolicy inst.n under deferred-until-stopping commitment on a Pandora's problem…
  • 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…
  • PandoraDeadlineInstanceAn instance of Pandora's problem with deadlines consisting of n boxes, each with a non-negative opening cost, a positive integer deadline,…
Used by 2
  • opt_dus_nonnegFor any Pandora deadline instance inst, 0 ≤ optDUS inst.
  • 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 expected net utility of the stop policy under deferred-until-stopping commitment is zero. -/
theorem expected_utility_dus_stop (inst : PandoraDeadlineInstance) :
    expectedUtilityDUS inst AdaptivePolicy.stop = 0 := by
  rfl
See it in the graphDiscuss this resultChallenge it