AFTD Auto-Formalizing Theoretical Domains

two_box_pi01_dus

theoremverified

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 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.
  • expectedUtilityDUSThe expected net utility of an adaptive policy π : AdaptivePolicy inst.n under 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…
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

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.

  1. 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.

    lines 6–9

    uses Nat.one_lt_cast.mpr, le_of_lt, ne_of_lt

      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
  2. 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.

    lines 10–12

      simp only [expectedUtilityDUS, expectedUtilityDUS.aux, two_box_deadline_inst]
      simp [two_box_fair_value_dist]
      simp only [two_box_risky_value_dist]
  3. 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.

    lines 13–14

    uses Finset.sum_pair, if_true, if_neg

      rw [Finset.sum_pair hne]
      simp only [if_true, if_neg hne.symm]
  4. 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.

    lines 15–17

    uses max_eq_right, le_of_lt, max_eq_left

      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]
  5. 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.

    lines 18–19

    uses mul_inv_cancel₀, ne_of_gt

      have 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

/-- 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
See it in the graphDiscuss this resultChallenge it