two_box_valid_stop_of_mem_one
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
Mwith probability1/Mand 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…
- two_box_deadline_instTwo boxes with zero cost: box 0 has deadline 1 and deterministic value 1; box 1 has deadline 2, value
- 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 that2 - 1 / M ≤ optDUS instand 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.
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.
cases π with | stop => rfl
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).
uses
IsValidPolicyAux.eq_def| openBox b cont => rw [IsValidPolicyAux.eq_def] at hv obtain ⟨hb, hd, -⟩ := hvIt 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.
fin_cases b
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`.
uses
two_box_deadline_inst,Fin.zero_eta· simp only [two_box_deadline_inst, ↓reduceIte, Fin.zero_eta] at hd omega
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`.
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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
/-- 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