AFTD Auto-Formalizing Theoretical Domains

two_box_dtd_le_one

theoremverified

Under deferred-to-deadline commitment, every valid policy on the two-box instance gets expected utility at most 1.

Statement

theorem two_box_dtd_le_one (M : ℕ) (hM : 1 < M) (π : AdaptivePolicy 2)
    (hπ : IsValidPolicy (two_box_deadline_inst M hM) π) :
    expectedUtilityDTD (two_box_deadline_inst M hM) π ≤ 1
Source
step towards two_box_counterexample_family
Verified
24 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 12
  • 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_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.
  • PandoraDeadlineInstanceAn instance of Pandora's problem with deadlines consisting of n boxes, each with a non-negative opening cost, a positive integer deadline,…
  • 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_risky_value_distThe distribution taking the value M with probability 1/M and the value 0 with probability 1 - 1/M.
  • two_box_fair_value_distThe degenerate discrete distribution taking the value 1 with probability 1.
  • DiscreteDistA discrete probability distribution with finite support on non-negative real values, defined by a finite support set, non-negative…
  • expectedUtilityDTDThe expected net utility of an adaptive policy π : AdaptivePolicy inst.n under deferred-to-deadline commitment on a Pandora's problem…
  • 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…
  • 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.
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

The proof proceeds by case analysis on the first action of the policy. If the policy stops immediately, it receives 0 utility. If it first opens box 0, the deterministic value 1 and deadline constraint ensure expected utility at most 1 by an auxiliary lemma. If it first opens box 1, box 0's deadline of 1 expires immediately, forcing any valid continuation policy to stop, which limits the utility to the realized value of box 1; taking the expectation over this risky distribution yields at most 1 since its mean is 1.

  1. If the policy stops immediately without opening any box, its expected utility is 0, which is at most 1. automation

    A policy that stops immediately opens no boxes. In the auxiliary expected utility function, an empty history of opened boxes yields 0 payoff, so the expected utility is 0 ≤ 1, closed by simp.

    lines 5–6

      cases π with
      | stop => simp [expectedUtilityDTD, expectedUtilityDTD.aux]
  2. For a policy that opens box b with continuation cont, the policy is valid and its expected utility is the expected continuation utility over the distribution of box b.

    We reformulate the goal using the auxiliary expected utility function on an empty history. By unfolding policy validity (`IsValidPolicyAux.eq_def`), we obtain the hypotheses that box b is not in the opened list, the deadline condition holds, and for every outcome v in the support of box b, the continuation policy `cont v` is valid. Expanding the auxiliary expected utility for opening box b gives the expectation of continuation utilities minus the opening cost (which is 0).

    lines 7–12

    uses IsValidPolicyAux.eq_def

      | openBox b cont =>
        show expectedUtilityDTD.aux (two_box_deadline_inst M hM) [] (AdaptivePolicy.openBox b cont) ≤ 1
        unfold IsValidPolicy at hπ
        rw [IsValidPolicyAux.eq_def] at hπ
        obtain ⟨hb, hd, hv⟩ := hπ
        simp only [expectedUtilityDTD.aux]
  3. If the first box opened is box 0, the expected utility is at most 1.

    We perform a case distinction on whether b = 0. In this case, box 0 has the deterministic distribution `two_box_fair_value_dist`, which yields value 1 with probability 1, reducing the expected utility to the utility of `cont 1`. By policy validity, `cont 1` is valid after opening box 0. Applying `two_box_dtd_after_box_zero`, any valid continuation policy after opening box 0 earns at most 1.

    lines 13–22

    uses if_pos, Finset.sum_singleton, two_box_dtd_after_box_zero

        by_cases hb0 : b = 0
        · rw [if_pos hb0]
          simp only [two_box_fair_value_dist, Finset.sum_singleton]
          have hzero : IsValidPolicyAux (two_box_deadline_inst M hM) rfl [(0 : Fin 2)] (cont 1) := by
            subst hb0
            have h := hv 1 (by simp [two_box_fair_value_dist])
            simpa using h
          have hle := two_box_dtd_after_box_zero M hM (cont 1) hzero
          subst hb0
          simpa using hle
  4. If the first box opened is not box 0, it must be box 1.

    When b ≠ 0, the distribution in the expectation is the risky distribution `two_box_risky_value_dist M hM`. Since the instance has only two boxes (b ∈ Fin 2), ruling out 0 leaves b = 1 as the only possibility.

    lines 23–28

    uses if_neg

        · rw [if_neg hb0]
          have hb1 : b = 1 := by
            fin_cases b
            · exact absurd rfl hb0
            · rfl
          subst hb1
  5. After opening box 1 with realized outcome x, any valid continuation must stop immediately, achieving utility at most x.

    For any value x in the support of the risky distribution, the continuation `cont x` is valid with opened list [1]. By `two_box_valid_stop_of_mem_one`, because box 1 has been opened and the opened list has length at least 1, any valid continuation policy must immediately be `AdaptivePolicy.stop`, since box 0's deadline of 1 has passed. Stopping with history [(1, x)] at time 1 meets box 1's deadline of 2; since x ≥ 0, the resulting utility is exactly max(0, x) = x.

    lines 29–39

    uses two_box_valid_stop_of_mem_one, List.length_cons, List.length_nil

          have hbound : ∀ x ∈ (two_box_risky_value_dist M hM).support,
              expectedUtilityDTD.aux (two_box_deadline_inst M hM) [((1 : Fin 2), x)] (cont x) ≤ x := by
            intro x hx
            have hvalid : IsValidPolicyAux (two_box_deadline_inst M hM) rfl [(1 : Fin 2)] (cont x) := by
              have h := hv x (by simpa using hx)
              simpa using h
            have hstop := two_box_valid_stop_of_mem_one M hM [(1 : Fin 2)] (cont x) hvalid (by simp) (by simp)
            have hx0 : 0 ≤ x := (two_box_risky_value_dist M hM).val_nonneg x hx
            rw [hstop]
            simp only [expectedUtilityDTD.aux, List.length_cons, List.length_nil]
            simp [hx0]
  6. The total expected utility when opening box 1 first is at most 1. automation

    Weighting the pointwise bound on continuation utility by the non-negative probabilities and summing over the support of the risky distribution via `Finset.sum_le_sum` and `mul_le_mul_of_nonneg_left`, the total expected utility is bounded by the mean of the risky distribution. By `two_box_risky_value_mean`, this mean is exactly 1, and linear arithmetic finishes the proof.

    lines 40–49

    uses Finset.sum_le_sum, mul_le_mul_of_nonneg_left, two_box_risky_value_mean

          have hsum : ∑ x ∈ (two_box_risky_value_dist M hM).support,
              (two_box_risky_value_dist M hM).prob x *
                expectedUtilityDTD.aux (two_box_deadline_inst M hM) [((1 : Fin 2), x)] (cont x)
              ≤ ∑ x ∈ (two_box_risky_value_dist M hM).support,
                  (two_box_risky_value_dist M hM).prob x * x := by
            apply Finset.sum_le_sum
            intro x hx
            exact mul_le_mul_of_nonneg_left (hbound x hx) ((two_box_risky_value_dist M hM).prob_nonneg x hx)
          rw [two_box_risky_value_mean M hM] at hsum
          linarith
IsValidPolicyAux.eq_def
Unfolds the definition of a valid policy: stopping is always valid, while opening a box requires that it was not previously opened, that opening it does not exceed its deadline, and that every possible realized value leads to a valid continuation policy.
if_pos
If the condition c holds, the conditional expression (if c then t else e) simplifies to t.
Finset.sum_singleton
The sum of a function over a singleton set {a} equals the function evaluated at a.
two_box_dtd_after_box_zero
Under deferred-to-deadline commitment, any valid continuation policy after opening box 0 (which has value 1 and deadline 1) achieves expected utility at most 1.
if_neg
If the condition c does not hold, the conditional expression (if c then t else e) simplifies to e.
two_box_valid_stop_of_mem_one
Any valid continuation policy after opening box 1 must stop immediately, because opening box 0 would violate box 0's deadline of 1.
List.length_cons
The length of a list with an element prepended is one more than the length of the tail.
List.length_nil
The empty list has length 0.
Finset.sum_le_sum
If f(i) ≤ g(i) for all elements i in a finite set, then the sum of f over the set is at most the sum of g over the set.
mul_le_mul_of_nonneg_left
Multiplying both sides of an inequality b ≤ c by a non-negative scalar a preserves the inequality: a * b ≤ a * c.
two_box_risky_value_mean
The expected value of the risky distribution for box 1 is 1.

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

/-- Every valid policy achieves DTD expected utility at most 1 on the two-box instance. -/theorem two_box_dtd_le_one (M : ℕ) (hM : 1 < M) (π : AdaptivePolicy 2)    (hπ : IsValidPolicy (two_box_deadline_inst M hM) π) :    expectedUtilityDTD (two_box_deadline_inst M hM) π ≤ 1 := by  cases π with  | stop => simp [expectedUtilityDTD, expectedUtilityDTD.aux]  | openBox b cont =>    show expectedUtilityDTD.aux (two_box_deadline_inst M hM) [] (AdaptivePolicy.openBox b cont) ≤ 1    unfold IsValidPolicy at hπ    rw [IsValidPolicyAux.eq_def] at hπ    obtain ⟨hb, hd, hv⟩ := hπ    simp only [expectedUtilityDTD.aux]    by_cases hb0 : b = 0    · rw [if_pos hb0]      simp only [two_box_fair_value_dist, Finset.sum_singleton]      have hzero : IsValidPolicyAux (two_box_deadline_inst M hM) rfl [(0 : Fin 2)] (cont 1) := by        subst hb0        have h := hv 1 (by simp [two_box_fair_value_dist])        simpa using h      have hle := two_box_dtd_after_box_zero M hM (cont 1) hzero      subst hb0      simpa using hle    · rw [if_neg hb0]      have hb1 : b = 1 := by        fin_cases b        · exact absurd rfl hb0        · rfl      subst hb1      have hbound : ∀ x ∈ (two_box_risky_value_dist M hM).support,          expectedUtilityDTD.aux (two_box_deadline_inst M hM) [((1 : Fin 2), x)] (cont x) ≤ x := by        intro x hx        have hvalid : IsValidPolicyAux (two_box_deadline_inst M hM) rfl [(1 : Fin 2)] (cont x) := by          have h := hv x (by simpa using hx)          simpa using h        have hstop := two_box_valid_stop_of_mem_one M hM [(1 : Fin 2)] (cont x) hvalid (by simp) (by simp)        have hx0 : 0 ≤ x := (two_box_risky_value_dist M hM).val_nonneg x hx        rw [hstop]        simp only [expectedUtilityDTD.aux, List.length_cons, List.length_nil]        simp [hx0]      have hsum : ∑ x ∈ (two_box_risky_value_dist M hM).support,          (two_box_risky_value_dist M hM).prob x *            expectedUtilityDTD.aux (two_box_deadline_inst M hM) [((1 : Fin 2), x)] (cont x)          ≤ ∑ x ∈ (two_box_risky_value_dist M hM).support,              (two_box_risky_value_dist M hM).prob x * x := by        apply Finset.sum_le_sum        intro x hx        exact mul_le_mul_of_nonneg_left (hbound x hx) ((two_box_risky_value_dist M hM).prob_nonneg x hx)      rw [two_box_risky_value_mean M hM] at hsum      linarith
See it in the graphDiscuss this resultChallenge it