AFTD Auto-Formalizing Theoretical Domains

two_box_valid_stop_of_mem_one

theoremverified

If a valid policy execution has box 1 in its already-opened list and at least one round has elapsed, then the remaining policy is stop.

Statement

theorem two_box_valid_stop_of_mem_one (M : ℕ) (hM : 1 < M) (opened : List (Fin 2)) (π : AdaptivePolicy 2)
    (hv : IsValidPolicyAux (two_box_deadline_inst M hM) rfl opened π) (h1 : (1 : Fin 2) ∈ opened)
    (h2 : 1 ≤ opened.length) : π = AdaptivePolicy.stop
Source
step towards two_box_counterexample_family
Verified
24 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 5
  • 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…
  • PandoraDeadlineInstanceAn instance of Pandora's problem with deadlines consisting of n boxes, each with a non-negative opening cost, a positive integer deadline,…
  • DiscreteDistA discrete probability distribution with finite support on non-negative real values, defined by a finite support set, non-negative…
  • 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…
Used by 3
  • two_box_dtd_le_oneUnder deferred-to-deadline commitment, every valid policy on the two-box instance gets expected utility at most 1.
  • two_box_dtd_after_box_zeroWith the history [(0, 1)], any valid policy has deferred-to-deadline expected utility at most 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 theorem shows that if box 1 has already been opened and at least one round has elapsed, no further box can be opened in a valid policy, so the policy must be `stop`. The proof splits on the policy structure: `stop` is immediate, while opening a box `b` is impossible because neither box 0 (whose deadline of 1 has already passed) nor box 1 (which is already in the opened list) can legally be chosen.

  1. If the policy is `stop`, the equality holds by definition.

    We perform case analysis on the policy π. In the case where π is `stop`, the goal becomes `stop = stop`, which holds by reflexivity.

    lines 5–6

      cases π with
      | stop => rfl
  2. If the policy attempts to open a box `b`, validity implies that `b` has not been opened yet and its deadline has not been exceeded.

    In the case where π is `openBox b cont`, we rewrite the validity hypothesis `hv` using `IsValidPolicyAux.eq_def`. This decomposes `hv` into the conditions that `b ∉ opened` (hb) and `opened.length + 1 ≤ deadline(b)` (hd).

    lines 7–9

    uses IsValidPolicyAux.eq_def

      | openBox b cont =>
        rw [IsValidPolicyAux.eq_def] at hv
        obtain ⟨hb, hd, -⟩ := hv
  3. It suffices to check the two possible choices for box `b`, namely `b = 0` and `b = 1`.

    Since `b` is an index in `Fin 2`, there are only two possible values: 0 and 1. We split into these two cases.

    line 10

        fin_cases b
  4. Box 0 cannot be opened because its deadline is 1, but at least one box has already been opened.

    For `b = 0`, simplifying the instance definition shows that box 0 has deadline 1, so validity requires `opened.length + 1 ≤ 1`. Since at least one box has already been opened (`1 ≤ opened.length`), integer linear arithmetic (`omega`) detects the contradiction `2 ≤ 1`.

    lines 11–12

    uses two_box_deadline_inst, Fin.zero_eta

        · simp only [two_box_deadline_inst, ↓reduceIte, Fin.zero_eta] at hd
          omega
  5. Box 1 cannot be opened because it has already been opened.

    For `b = 1`, validity requires that box 1 is not in `opened` (`hb : 1 ∉ opened`). But this directly contradicts the hypothesis `h1 : 1 ∈ opened`.

    line 13

    uses absurd

        · exact absurd h1 hb
IsValidPolicyAux.eq_def
Characterizes valid policies: `stop` is always valid, while `openBox b cont` is valid if `b` is not already opened, the step count does not exceed `b`'s deadline, and all continuations are valid.
two_box_deadline_inst
The definition of the two-box instance with deadlines, where box 0 has deadline 1 and box 1 has deadline 2.
Fin.zero_eta
In `Fin n`, the element with value 0 equals the numeral 0.
absurd
Derives any conclusion from a proposition and its negation.

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

/-- Once box 1 has been opened (and at least one round has elapsed), no valid policy can continue: box 0 is already past its deadline. -/theorem two_box_valid_stop_of_mem_one (M : ℕ) (hM : 1 < M) (opened : List (Fin 2)) (π : AdaptivePolicy 2)    (hv : IsValidPolicyAux (two_box_deadline_inst M hM) rfl opened π) (h1 : (1 : Fin 2) ∈ opened)    (h2 : 1 ≤ opened.length) : π = AdaptivePolicy.stop := by  cases π with  | stop => rfl  | openBox b cont =>    rw [IsValidPolicyAux.eq_def] at hv    obtain ⟨hb, hd, -⟩ := hv    fin_cases b    · simp only [two_box_deadline_inst, ↓reduceIte, Fin.zero_eta] at hd      omega    · exact absurd h1 hb
See it in the graphDiscuss this resultChallenge it