AFTD Auto-Formalizing Theoretical Domains

two_box_dtd_after_box_zero

theoremverified

With the history [(0, 1)], any valid policy has deferred-to-deadline expected utility at most 1.

Statement

theorem two_box_dtd_after_box_zero (M : ℕ) (hM : 1 < M) (π : AdaptivePolicy 2)
    (hπ : IsValidPolicyAux (two_box_deadline_inst M hM) rfl [(0 : Fin 2)] π) :
    expectedUtilityDTD.aux (two_box_deadline_inst M hM) [((0 : Fin 2), (1:ℝ))] π ≤ 1
Source
step towards two_box_counterexample_family
Verified
24 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 10
  • 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.
  • 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_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.
  • 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…
  • expectedUtilityDTDThe expected net utility of an adaptive policy π : AdaptivePolicy inst.n under deferred-to-deadline commitment on a Pandora's problem…
Used by 2
  • 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_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 theorem is proved by case analysis on the policy $\pi$. If $\pi$ stops immediately at round 1, box 0 (deadline 1) is unexpired, yielding utility 1. If $\pi$ opens another box, validity forces it to open box 1, after which any valid continuation policy must stop at round 2 by `two_box_valid_stop_of_mem_one`. At round 2, box 0 has expired and contributes nothing, while box 1 yields its revealed value $x$. Taking the expectation over $x$, the expected payoff is bounded by the mean of box 1, which equals 1 by `two_box_risky_value_mean`.

  1. If the policy stops immediately, its expected utility is at most 1. automation

    We perform a case split on the policy $\pi$. If $\pi$ is `stop`, the process halts at round 1. Box 0 was opened in round 1 and has deadline 1 ($1 \le 1$), so it is not expired, yielding payoff $\max(0, 1) = 1$. The simplification tactic unfolds the expected utility definition and confirms $1 \le 1$.

    lines 9–11

      cases π with
      | stop =>
        simp [expectedUtilityDTD.aux, two_box_deadline_inst]
  2. If the policy opens another box, it must open box 1.

    If $\pi$ opens some box $b$ with continuation `cont`, the validity condition `IsValidPolicyAux.eq_def` requires $b \notin [0]$ (`List.mem_singleton`), so $b \ne 0$. Since there are only two boxes (0 and 1) in `Fin 2`, case analysis rules out $b = 0$, forcing $b = 1$.

    lines 12–20

    uses IsValidPolicyAux.eq_def, List.mem_singleton, List.length_singleton

      | openBox b cont =>
        rw [IsValidPolicyAux.eq_def] at hπ
        obtain ⟨hb, hd, hv⟩ := hπ
        simp only [List.mem_singleton, List.length_singleton] at hb hd
        have hb1 : b = (1 : Fin 2) := by
          fin_cases b
          · exact absurd rfl hb
          · rfl
        subst hb1
  3. Opening box 1 reduces the utility to an expectation over continuation policies, each valid with history $[1, 0]$.

    Unfolding the expected utility for opening box 1 (which has cost 0) expresses the utility as the expectation of the continuation payoff over outcomes $v$ in the support of box 1's risky distribution. From the validity hypothesis, each continuation policy $\text{cont}(v)$ is valid for the opened list $[1, 0]$.

    lines 21–25

        simp only [Fin.isValue, expectedUtilityDTD.aux, two_box_deadline_inst]
        simp only [Fin.reduceEq, reduceIte]
        have hv' : ∀ v ∈ (two_box_risky_value_dist M hM).support,
            IsValidPolicyAux (two_box_deadline_inst M hM) rfl [(1 : Fin 2), 0] (cont v) := by
          simpa using hv
  4. For every outcome $x$ of box 1, the continuation policy stops immediately, yielding utility at most $x$.

    For any value $x$ in the support of box 1, because box 1 is in the opened list $[1, 0]$ (which has length 2), `two_box_valid_stop_of_mem_one` forces $\text{cont}(x) = \text{stop}$. Stopping at history $[(1, x), (0, 1)]$ means stopping time $t = 2$. At time 2, box 0 (deadline 1) has expired ($2 \le 1$ is false) and contributes 0, while box 1 (deadline 2) is unexpired ($2 \le 2$) and contributes $x \ge 0$. Evaluating the fold over the history with `List.length_cons` and `List.length_nil` simplifies the payoff to $\max(0, x) = x \le x$.

    lines 26–34

    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), (0, 1)] (cont x) ≤ x := by
          intro x hx
          have hcont := two_box_valid_stop_of_mem_one M hM [(1 : Fin 2), 0] (cont x) (hv' x hx) (by simp) (by simp)
          have hx0 : 0 ≤ x := (two_box_risky_value_dist M hM).val_nonneg x hx
          rw [hcont]
          simp only [expectedUtilityDTD.aux, two_box_deadline_inst, List.length_cons, List.length_nil,
            Fin.isValue]
          simp [hx0]
  5. The expected utility of opening box 1 is at most 1, concluding the proof. automation

    Because each continuation payoff is bounded by $x$ and probabilities are nonnegative, `Finset.sum_le_sum` and `mul_le_mul_of_nonneg_left` show that the expected utility is bounded by the mean value $\sum x \cdot P(x)$. Rewriting with `two_box_risky_value_mean` replaces this expectation with 1, and linear arithmetic (`linarith`) completes the proof.

    lines 35–44

    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), (0, 1)] (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
Unfolding equation for `IsValidPolicyAux`: `stop` is always valid, while `openBox b cont` is valid if box $b$ has not yet been opened, the round does not exceed $b$'s deadline, and all continuation policies are valid.
List.mem_singleton
An element belongs to a singleton list $[b]$ if and only if it equals $b$.
List.length_singleton
A singleton list has length 1.
two_box_valid_stop_of_mem_one
In the two-box instance, any valid policy must stop immediately once box 1 has been opened and at least one box is in the opened history.
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
A finite sum of pointwise smaller terms is less than or equal to the sum of the larger terms.
mul_le_mul_of_nonneg_left
Multiplying both sides of an inequality by a nonnegative factor preserves the inequality.
two_box_risky_value_mean
The expected value of the distribution for the risky 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

theorem two_box_dtd_after_box_zero_unfold (M : ℕ) (hM : 1 < M) (π : AdaptivePolicy 2) :    expectedUtilityDTD (two_box_deadline_inst M hM) π      = expectedUtilityDTD.aux (two_box_deadline_inst M hM) [] π := rfl/-- After box 0 (value 1) has been opened, the DTD payoff of any valid policy is at most 1, because box 0 is expired by round 2 and box 1 has mean value 1. -/theorem two_box_dtd_after_box_zero (M : ℕ) (hM : 1 < M) (π : AdaptivePolicy 2)    (hπ : IsValidPolicyAux (two_box_deadline_inst M hM) rfl [(0 : Fin 2)] π) :    expectedUtilityDTD.aux (two_box_deadline_inst M hM) [((0 : Fin 2), (1:ℝ))] π ≤ 1 := by  cases π with  | stop =>    simp [expectedUtilityDTD.aux, two_box_deadline_inst]  | openBox b cont =>    rw [IsValidPolicyAux.eq_def] at hπ    obtain ⟨hb, hd, hv⟩ := hπ    simp only [List.mem_singleton, List.length_singleton] at hb hd    have hb1 : b = (1 : Fin 2) := by      fin_cases b      · exact absurd rfl hb      · rfl    subst hb1    simp only [Fin.isValue, expectedUtilityDTD.aux, two_box_deadline_inst]    simp only [Fin.reduceEq, reduceIte]    have hv' : ∀ v ∈ (two_box_risky_value_dist M hM).support,        IsValidPolicyAux (two_box_deadline_inst M hM) rfl [(1 : Fin 2), 0] (cont v) := by      simpa using hv    have hbound : ∀ x ∈ (two_box_risky_value_dist M hM).support,        expectedUtilityDTD.aux (two_box_deadline_inst M hM) [((1 : Fin 2), x), (0, 1)] (cont x) ≤ x := by      intro x hx      have hcont := two_box_valid_stop_of_mem_one M hM [(1 : Fin 2), 0] (cont x) (hv' x hx) (by simp) (by simp)      have hx0 : 0 ≤ x := (two_box_risky_value_dist M hM).val_nonneg x hx      rw [hcont]      simp only [expectedUtilityDTD.aux, two_box_deadline_inst, List.length_cons, List.length_nil,        Fin.isValue]      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), (0, 1)] (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