two_box_pi01_dus
The DUS utility of the policy opening box 0 then box 1 is 2 - 1/M.
Statement
theorem two_box_pi01_dus (M : ℕ) (hM : 1 < M) : expectedUtilityDUS (two_box_deadline_inst M hM) (AdaptivePolicy.openBox (0 : Fin 2) (fun _ => AdaptivePolicy.openBox (1 : Fin 2) (fun _ => AdaptivePolicy.stop))) = 2 - 1 / (M : ℝ)
- Source
- step towards two_box_counterexample_family
- Verified
- 24 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 7
- 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_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. - expectedUtilityDUSThe expected net utility of an adaptive policy
π : AdaptivePolicy inst.nunder deferred-until-stopping commitment on a Pandora's problem… - 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…
- 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 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π…
- two_box_counterexample_familyFor any integer
The proof, explained
Under the deferred-until-stopping (DUS) policy, opening box 0 first yields a deterministic value of 1, after which box 1 yields either M (with probability 1/M) or 0 (with probability 1 - 1/M). Because opening costs are zero and values are retained until stopping, the payoff is max(1, v) where v is the outcome of box 1. Unfolding the definition of expected utility leaves a two-point expectation (1 - 1/M) · 1 + (1/M) · M, which simplifies directly to 2 - 1/M.
The inequalities 1 < M, 1 ≤ M, 0 < M, and 0 ≠ M hold in ℝ
Casting the hypothesis 1 < M from ℕ to ℝ via Nat.one_lt_cast.mpr gives 1 < M, which implies 1 ≤ M by le_of_lt. Arithmetic positivity establishes 0 < M, from which 0 ≠ M follows by ne_of_lt.
uses
Nat.one_lt_cast.mpr,le_of_lt,ne_of_lthave hMgt1 : (1 : ℝ) < (M : ℝ) := Nat.one_lt_cast.mpr hM have h1M : (1 : ℝ) ≤ (M : ℝ) := le_of_lt hMgt1 have hMpos : (0 : ℝ) < (M : ℝ) := by positivity have hne : (0 : ℝ) ≠ (M : ℝ) := ne_of_lt hMpos
The expected utility reduces to the expected payoff over the risky distribution of box 1
Unfolding the recursive definition of expectedUtilityDUS and the two-box instance parameters, the policy first opens box 0, which reveals a deterministic reward of 1 with probability 1. Eliminating this deterministic sum leaves only the expectation over the outcome v of box 1, where the accumulated payoff at stopping is max (max 0 v) 1.
simp only [expectedUtilityDUS, expectedUtilityDUS.aux, two_box_deadline_inst] simp [two_box_fair_value_dist] simp only [two_box_risky_value_dist]
The sum over the support {0, M} splits into the terms for v = 0 and v = M
Because 0 ≠ M, Finset.sum_pair expands the sum over {0, M} into two explicit summands for v = 0 and v = M. Evaluating the conditional probabilities with if_true and if_neg gives weight 1 - 1/M to outcome 0 and weight 1/M to outcome M.
uses
Finset.sum_pair,if_true,if_negrw [Finset.sum_pair hne] simp only [if_true, if_neg hne.symm]
The payoffs in the two branches simplify to 1 and M, respectively
For v = 0, the maximum max (max 0 0) 1 evaluates to 1 by numerical normalization (norm_num). For v = M, since 0 < M and 1 ≤ M, max_eq_right and max_eq_left simplify max (max 0 M) 1 to M. Substituting these values reduces the goal to (1 - 1/M) * 1 + (1/M) * M = 2 - 1/M.
uses
max_eq_right,le_of_lt,max_eq_lefthave hA : max (max 0 0) (1 : ℝ) = 1 := by norm_num have hB : max (max 0 (M : ℝ)) 1 = M := by rw [max_eq_right (le_of_lt hMpos), max_eq_left h1M] rw [hA, hB]
The expected utility equals 2 - 1/M automation
Since M > 0, the product M * M⁻¹ equals 1 by mul_inv_cancel₀ and ne_of_gt. Linear arithmetic (linarith) simplifies (1 - 1/M) * 1 + (1/M) * M to 2 - 1/M, closing the proof.
uses
mul_inv_cancel₀,ne_of_gthave hinv : (M : ℝ) * (M : ℝ)⁻¹ = 1 := mul_inv_cancel₀ (ne_of_gt hMpos) linarith
Nat.one_lt_cast.mpr- for a natural number n, 1 < n as natural numbers implies 1 < n when cast to the real numbers
le_of_lt- a strict inequality a < b implies the non-strict inequality a ≤ b
ne_of_lt- a strict inequality a < b implies a ≠ b
Finset.sum_pair- if a ≠ b, the sum of a function over the two-element set {a, b} equals f(a) + f(b)
if_true- an if-then-else expression whose condition is True simplifies to the then branch
if_neg- an if-then-else expression whose condition is false simplifies to the else branch
max_eq_right- if a ≤ b, then max a b = b
max_eq_left- if b ≤ a, then max a b = a
mul_inv_cancel₀- any non-zero element a in a group with zero satisfies a * a⁻¹ = 1
ne_of_gt- if b < a, then a ≠ b
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.
/-- Under deferred-until-stopping, opening box 0 then box 1 yields `2 - 1/M`: box 0's value 1 is never forgotten and box 1 adds mean `1/M · M = 1`. -/theorem two_box_pi01_dus (M : ℕ) (hM : 1 < M) : expectedUtilityDUS (two_box_deadline_inst M hM) (AdaptivePolicy.openBox (0 : Fin 2) (fun _ => AdaptivePolicy.openBox (1 : Fin 2) (fun _ => AdaptivePolicy.stop))) = 2 - 1 / (M : ℝ) := by have hMgt1 : (1 : ℝ) < (M : ℝ) := Nat.one_lt_cast.mpr hM have h1M : (1 : ℝ) ≤ (M : ℝ) := le_of_lt hMgt1 have hMpos : (0 : ℝ) < (M : ℝ) := by positivity have hne : (0 : ℝ) ≠ (M : ℝ) := ne_of_lt hMpos simp only [expectedUtilityDUS, expectedUtilityDUS.aux, two_box_deadline_inst] simp [two_box_fair_value_dist] simp only [two_box_risky_value_dist] rw [Finset.sum_pair hne] simp only [if_true, if_neg hne.symm] have hA : max (max 0 0) (1 : ℝ) = 1 := by norm_num have hB : max (max 0 (M : ℝ)) 1 = M := by rw [max_eq_right (le_of_lt hMpos), max_eq_left h1M] rw [hA, hB] have hinv : (M : ℝ) * (M : ℝ)⁻¹ = 1 := mul_inv_cancel₀ (ne_of_gt hMpos) linarith