AFTD Auto-Formalizing Theoretical Domains

two_box_pi01_valid

theoremverified

The policy "open box 0, then box 1, then stop" is valid for the two-box instance.

Statement

theorem two_box_pi01_valid (M : ℕ) (hM : 1 < M) :
    IsValidPolicy (two_box_deadline_inst M hM)
      (AdaptivePolicy.openBox (0 : Fin 2) (fun _ => AdaptivePolicy.openBox (1 : Fin 2) (fun _ => AdaptivePolicy.stop)))
Source
step towards two_box_counterexample_family
Verified
24 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 8
  • two_box_deadline_instTwo boxes with zero cost: box 0 has deadline 1 and deterministic value 1; box 1 has deadline 2, value M with probability 1/M and 0…
  • two_box_fair_value_distThe degenerate discrete distribution taking the value 1 with probability 1.
  • two_box_risky_value_distThe distribution taking the value M with probability 1/M and the value 0 with probability 1 - 1/M.
  • PandoraDeadlineInstanceAn instance of Pandora's problem with deadlines consisting of n boxes, each with a non-negative opening cost, a positive integer deadline,…
  • IsValidPolicyAuxA policy execution is valid if it never re-opens an already opened box, respects the deadline of each opened box, and remains valid on all…
  • 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…
  • 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.
  • DiscreteDistA discrete probability distribution with finite support on non-negative real values, defined by a finite support set, non-negative…
Used by 1
  • two_box_counterexample_familyFor any integer M > 1, there exists a 2-box Pandora deadline instance such that 2 - 1 / M ≤ optDUS inst and every valid policy π…

The proof, explained

The proof verifies step by step that the adaptive policy of opening box 0, then box 1, and then stopping is valid for the two-box deadline instance. Opening box 0 at step 1 meets its deadline of 1, opening box 1 at step 2 meets its deadline of 2 without repeating an opened box, and stopping is unconditionally valid.

  1. Opening box 0 as the initial action satisfies the non-repetition and deadline constraints, leaving only the validity of the continuation.

    Unfolding the definition of policy validity (`IsValidPolicy`), opening a box requires that the box has not yet been opened, that the number of opened boxes plus one does not exceed the box's deadline, and that the continuation policy is valid for every outcome in the box's value distribution. For box 0, the history of opened boxes is empty, so 0 ∉ [] is immediate. Furthermore, the step count 0 + 1 = 1 is at most the deadline of box 0 (which is 1 according to `two_box_deadline_inst`), satisfying the deadline constraint.

    lines 5–7

      unfold IsValidPolicy
      refine ⟨by simp, ?_, ?_⟩
      · simp [two_box_deadline_inst]
  2. For any outcome of box 0, opening box 1 satisfies the non-repetition and deadline constraints.

    Given an observed value v in the support of box 0's distribution, the policy opens box 1 with history [0]. Box 1 is not in the history (1 ∉ [0]), and the new step count 1 + 1 = 2 is at most box 1's deadline of 2 in `two_box_deadline_inst`. This leaves the validity of the subsequent policy for every outcome of box 1.

    lines 8–10

      · intro v hv
        refine ⟨by simp, ?_, ?_⟩
        · simp [two_box_deadline_inst]
  3. For any outcome of box 1, stopping is valid.

    Given an observed value w in the support of box 1's distribution, the policy chooses to stop (`AdaptivePolicy.stop`). By definition, stopping imposes no further conditions (`True`) and is always valid.

    lines 11–12

        · intro w hw
          trivial

Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.

Lean source view module on GitHub

/-- Opening box 0 then box 1 is a valid policy for the two-box instance. -/theorem two_box_pi01_valid (M : ℕ) (hM : 1 < M) :    IsValidPolicy (two_box_deadline_inst M hM)      (AdaptivePolicy.openBox (0 : Fin 2) (fun _ => AdaptivePolicy.openBox (1 : Fin 2) (fun _ => AdaptivePolicy.stop))) := by  unfold IsValidPolicy  refine ⟨by simp, ?_, ?_⟩  · simp [two_box_deadline_inst]  · intro v hv    refine ⟨by simp, ?_, ?_⟩    · simp [two_box_deadline_inst]    · intro w hw      trivial
See it in the graphDiscuss this resultChallenge it