two_box_counterexample_family
For any integer M > 1, there exists a 2-box Pandora deadline instance such that 2 - 1 / M ≤ optDUS inst and every valid policy π achieves expectedUtilityDTD inst π ≤ 1.
Statement
theorem two_box_counterexample_family (M : ℕ) (hM : 1 < M) :
∃ inst : PandoraDeadlineInstance,
2 - (1 : ℝ) / M ≤ optDUS inst ∧
∀ π : AdaptivePolicy inst.n, IsValidPolicy inst π → expectedUtilityDTD inst π ≤ 1- Source
- step towards op182_deferred_to_deadline_beyond_half_against_stopping
- Verified
- 24 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 16
- expected_utility_dus_le_opt_dusFor any Pandora's problem instance with deadlines
instand any valid policyπ,expectedUtilityDUS inst π ≤ optDUS inst. - optDUSThe optimal expected net utility
optDUS instunder deferred-until-stopping commitment for a Pandora's problem instance with deadlines… - expectedUtilityDTDThe expected net utility of an adaptive policy
π : AdaptivePolicy inst.nunder deferred-to-deadline commitment on a Pandora's problem… - 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.
- two_box_fair_value_distThe degenerate discrete distribution taking the value
1with probability1. - two_box_risky_value_distThe distribution taking the value
Mwith probability1/Mand the value0with probability1 - 1/M. - 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… - two_box_risky_value_meanThe mean of the risky distribution is 1.
- two_box_valid_stop_of_mem_oneIf 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. - two_box_dtd_after_box_zeroWith the history
[(0, 1)], any valid policy has deferred-to-deadline expected utility at most 1. - two_box_pi01_validThe policy "open box 0, then box 1, then stop" is valid for the two-box instance.
- two_box_pi01_dusThe DUS utility of the policy opening box 0 then box 1 is
2 - 1/M. - two_box_dtd_le_oneUnder deferred-to-deadline commitment, every valid policy on the two-box instance gets expected utility at most 1.
- expectedUtilityDUSThe expected net utility of an adaptive policy
π : AdaptivePolicy inst.nunder 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,…
- expected_utility_dus_le_opt_dusFor any Pandora's problem instance with deadlines
- Used by 1
- op182_deferred_to_deadline_beyond_half_against_stoppingRefutation of Open Problem OP-182 against the deferred-until-stopping benchmark: there does not exist any constant
c > 1/2such that for…
- op182_deferred_to_deadline_beyond_half_against_stoppingRefutation of Open Problem OP-182 against the deferred-until-stopping benchmark: there does not exist any constant
The proof, explained
The existence claim is proved by exhibiting an explicit witness: the two-box deadline instance `two_box_deadline_inst M hM`. The lower bound on optDUS is established by evaluating the valid policy that opens box 0 followed by box 1, which attains expected utility 2 - 1/M. The upper bound on DTD expected utility is established by invoking the lemma `two_box_dtd_le_one`, which shows that no valid policy can achieve more than 1 under DTD.
To prove the existential statement, it suffices to consider the specific instance two_box_deadline_inst M hM and prove the two conditions for it.
We provide `two_box_deadline_inst M hM` as the witness for the existential quantifier using `refine`. This divides the proof into two subgoals: demonstrating that the optimal DUS utility is at least 2 - 1/M, and demonstrating that all valid DTD policies achieve an expected utility of at most 1.
refine ⟨two_box_deadline_inst M hM, ?_, ?_⟩2 - 1 / M ≤ optDUS (two_box_deadline_inst M hM)
By a calculation chain, 2 - 1/M is first shown to equal the expected utility under DUS of the policy that opens box 0 and then box 1 (by `two_box_pi01_dus`). Next, since this policy is valid for the instance (by `two_box_pi01_valid`), its expected utility is at most the supremum over all valid policies, optDUS (by `expected_utility_dus_le_opt_dus`).
uses
two_box_pi01_dus,expected_utility_dus_le_opt_dus,two_box_pi01_valid· calc 2 - (1 : ℝ) / M = expectedUtilityDUS (two_box_deadline_inst M hM) (AdaptivePolicy.openBox (0 : Fin 2) (fun _ => AdaptivePolicy.openBox (1 : Fin 2) (fun _ => AdaptivePolicy.stop))) := (two_box_pi01_dus M hM).symm _ ≤ optDUS (two_box_deadline_inst M hM) := expected_utility_dus_le_opt_dus _ _ (two_box_pi01_valid M hM)
For any policy π valid on two_box_deadline_inst M hM, expectedUtilityDTD (two_box_deadline_inst M hM) π ≤ 1
We introduce an arbitrary policy π and the hypothesis hπ that π is valid on this instance. Applying the specialized lemma `two_box_dtd_le_one` directly establishes that the expected utility of π under DTD is at most 1.
uses
two_box_dtd_le_one· intro π hπ exact two_box_dtd_le_one M hM π hπ
two_box_pi01_dus- For the 2-box deadline instance parameterized by M, the policy opening box 0 followed by box 1 achieves an expected utility under DUS of 2 - 1/M.
expected_utility_dus_le_opt_dus- For any instance, the expected utility under DUS of any valid policy is at most optDUS, the supremum of expected utility over all valid policies.
two_box_pi01_valid- For the 2-box deadline instance parameterized by M, the policy opening box 0 followed by box 1 is a valid policy.
two_box_dtd_le_one- For the 2-box deadline instance parameterized by M, every valid policy achieves an expected utility of at most 1 under DTD.
- The proof relies on pre-proven helper lemmas (`two_box_pi01_dus`, `two_box_pi01_valid`, and `two_box_dtd_le_one`) that perform the distribution calculations and policy-tree case analysis.
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.
/-- For any integer M > 1, there exists a 2-box instance with deadlines where optDUS is at least 2 - 1/M and every valid policy under DTD achieves expected utility at most 1. -/theorem two_box_counterexample_family (M : ℕ) (hM : 1 < M) : ∃ inst : PandoraDeadlineInstance, 2 - (1 : ℝ) / M ≤ optDUS inst ∧ ∀ π : AdaptivePolicy inst.n, IsValidPolicy inst π → expectedUtilityDTD inst π ≤ 1 := by refine ⟨two_box_deadline_inst M hM, ?_, ?_⟩ · calc 2 - (1 : ℝ) / M = expectedUtilityDUS (two_box_deadline_inst M hM) (AdaptivePolicy.openBox (0 : Fin 2) (fun _ => AdaptivePolicy.openBox (1 : Fin 2) (fun _ => AdaptivePolicy.stop))) := (two_box_pi01_dus M hM).symm _ ≤ optDUS (two_box_deadline_inst M hM) := expected_utility_dus_le_opt_dus _ _ (two_box_pi01_valid M hM) · intro π hπ exact two_box_dtd_le_one M hM π hπ