AFTD Auto-Formalizing Theoretical Domains

opt_dtd_le_opt_dus

theoremverifiedformalization

For every Pandora's problem instance with deadlines inst : PandoraDeadlineInstance, the optimal expected utility under deferred-to-deadline commitment optDTD inst is at most the optimal expected utility under deferred-until-stopping commitment optDUS inst.

Statement

theorem opt_dtd_le_opt_dus (inst : PandoraDeadlineInstance) :
    optDTD inst ≤ optDUS inst
Formalizes
arXiv:2610.13775 Sec. 2.1
Verified
19 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 10
  • optDTDThe optimal expected net utility optDTD inst under deferred-to-deadline commitment for a Pandora's problem instance with deadlines…
  • optDUSThe optimal expected net utility optDUS inst under deferred-until-stopping commitment for a Pandora's problem instance with deadlines…
  • expected_utility_dtd_le_dusFor every Pandora's problem instance with deadlines inst : PandoraDeadlineInstance and every adaptive policy…
  • 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…
  • DiscreteDistA discrete probability distribution with finite support on non-negative real values, defined by a finite support set, non-negative…
  • PandoraDeadlineInstanceAn instance of Pandora's problem with deadlines consisting of n boxes, each with a non-negative opening cost, a positive integer deadline,…
  • expectedUtilityDTDThe expected net utility of an adaptive policy π : AdaptivePolicy inst.n under deferred-to-deadline commitment on a Pandora's problem…
  • expectedUtilityDUSThe expected net utility of an adaptive policy π : AdaptivePolicy inst.n under deferred-until-stopping 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.
  • supportThe support $\mathrm{supp}(p) \subseteq \mathrm{Fin}\,n$ consists of coordinates where $p(i) \neq I$; the weight is…

Read back from the Lean

For every Pandora deadline instance inst, the optimal expected utility under the deadline-to-decision model (optDTD inst) is less than or equal to the optimal expected utility under the deadline-upon-stopping model (optDUS inst).

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

The proof, explained

The proof shows that the optimal expected utility under deferred-to-deadline commitment (optDTD) is at most that under deferred-until-stopping commitment (optDUS) by comparing policies pointwise. Because DTD allows claiming a box only if stopping occurs before that box's deadline while DUS allows claiming any opened box upon stopping, every policy achieves at least as much expected utility under DUS as under DTD (`expected_utility_dtd_le_dus`). To lift this pointwise inequality to the supremum over all valid policies via `ciSup_mono`, the proof establishes that DUS utilities are bounded above by the sum of all possible prize values (`opt_dtd_le_opt_dus_bddAbove`), using structural induction on policies and an auxiliary bound on list fold-max operations.

  1. Folding `max` over the empty list starting at x is at most max(x, M). automation

    For an empty list `[]`, `List.foldl` returns the initial accumulator x. Since x ≤ max(x, M) holds for any M, the base case is closed immediately by simplification.

    lines 1–6

    open Finset in
    /-- A `List.foldl` of `max` starting at `x` is at most `max x M` when every entry is at most `M`. -/
    lemma opt_dtd_le_opt_dus_foldl_max_le {α : Type*} :
        ∀ (l : List (α × ℝ)) (x M : ℝ), (∀ bv ∈ l, bv.2 ≤ M) →
          List.foldl (fun acc bv => max acc bv.2) x l ≤ max x M
      | [], x, M, _ => by simp
  2. If every element in hd :: tl has its second component bounded by M, folding `max` over hd :: tl starting at x is at most max(x, M).

    The head satisfies hd.2 ≤ M. Unfolding `List.foldl` on a cons list updates the accumulator to max(x, hd.2). By the induction hypothesis on the tail tl, folding over tl is at most max(max(x, hd.2), M). By associativity of `max` and the fact that max(hd.2, M) = M since hd.2 ≤ M, this bound simplifies to max(x, M).

    lines 7–12

    uses List.foldl_cons, le_trans, opt_dtd_le_opt_dus_foldl_max_le, List.mem_cons_of_mem, max_assoc, max_eq_right

      | hd :: tl, x, M, h => by
          have h1 : hd.2 ≤ M := h hd (by simp)
          simp only [List.foldl_cons]
          refine le_trans (opt_dtd_le_opt_dus_foldl_max_le tl (max x hd.2) M
            (fun bv hbv => h bv (List.mem_cons_of_mem _ hbv))) ?_
          rw [max_assoc, max_eq_right h1]
  3. For the stopping policy `AdaptivePolicy.stop`, the deferred-until-stopping expected utility from any history bounded by M ≥ 0 is at most M.

    We proceed by structural induction on the adaptive policy. When the policy stops, its utility is defined as folding `max` over the history starting at 0. Applying our list-folding lemma (`opt_dtd_le_opt_dus_foldl_max_le`) shows the result is at most max(0, M), which equals M because 0 ≤ M.

    lines 13–26

    uses le_trans, opt_dtd_le_opt_dus_foldl_max_le, max_eq_right

    /-- If every value that can be revealed lies below `M ≥ 0`, then the deferred-until-stopping
    expected utility of any policy is at most `M`. -/
    lemma opt_dtd_le_opt_dus_aux_bound (inst : PandoraDeadlineInstance) (M : ℝ)
        (hM0 : 0 ≤ M) (hMv : ∀ (i : Fin inst.n) (v : ℝ), v ∈ (inst.dist i).support → v ≤ M) :
        ∀ (a : AdaptivePolicy inst.n) (hist : List (Fin inst.n × ℝ)),
          (∀ bv ∈ hist, bv.2 ≤ M) → expectedUtilityDUS.aux inst hist a ≤ M := by
      intro a
      induction a using AdaptivePolicy.rec with
      | stop =>
          intro hist hh
          rw [show expectedUtilityDUS.aux inst hist (AdaptivePolicy.stop : AdaptivePolicy inst.n)
              = List.foldl (fun acc bv => max acc bv.2) 0 hist from rfl]
          exact le_trans (opt_dtd_le_opt_dus_foldl_max_le hist 0 M hh) (by rw [max_eq_right hM0])
  4. For an open-box policy `AdaptivePolicy.openBox b cont`, the deferred-until-stopping expected utility from any history bounded by M is at most M.

    Opening box b yields the expected utility of the continuation policies minus the box opening cost cost(b). For each revealed prize value v in the support of box b, the extended history (b, v) :: hist remains bounded by M because v ≤ M by assumption and the previous history is bounded by hypothesis. By the induction hypothesis, each continuation utility is at most M. Because probabilities are non-negative and sum to 1, the expected continuation utility is at most ∑ v, prob(v) * M = M. Finally, since the opening cost is non-negative, subtracting it leaves a quantity at most M.

    lines 27–50

    uses Finset.sum_le_sum, mul_le_mul_of_nonneg_left, List.mem_cons.mp, Finset.sum_mul, one_mul

      | openBox b cont ih =>
          intro hist hh
          rw [show expectedUtilityDUS.aux inst hist (AdaptivePolicy.openBox b cont) =
            ∑ v ∈ (inst.dist b).support, (inst.dist b).prob v *
              expectedUtilityDUS.aux inst ((b, v) :: hist) (cont v) - inst.cost b from rfl]
          have hsum : ∑ v ∈ (inst.dist b).support, (inst.dist b).prob v *
                expectedUtilityDUS.aux inst ((b, v) :: hist) (cont v) ≤ M := by
            have h1 : ∑ v ∈ (inst.dist b).support, (inst.dist b).prob v *
                expectedUtilityDUS.aux inst ((b, v) :: hist) (cont v)
                ≤ ∑ v ∈ (inst.dist b).support, (inst.dist b).prob v * M := by
              apply Finset.sum_le_sum
              intro v hv
              apply mul_le_mul_of_nonneg_left _ ((inst.dist b).prob_nonneg v hv)
              exact ih v ((b, v) :: hist) (fun bv hbv => by
                rcases List.mem_cons.mp hbv with hmem | hmem
                · rw [hmem]; exact hMv b v hv
                · exact hh bv hmem)
            calc ∑ v ∈ (inst.dist b).support, (inst.dist b).prob v *
                  expectedUtilityDUS.aux inst ((b, v) :: hist) (cont v)
                ≤ ∑ v ∈ (inst.dist b).support, (inst.dist b).prob v * M := h1
              _ = (∑ v ∈ (inst.dist b).support, (inst.dist b).prob v) * M := by
                    rw [Finset.sum_mul]
              _ = M := by rw [(inst.dist b).sum_prob_one, one_mul]
          linarith [inst.cost_nonneg b]
  5. The set of deferred-until-stopping expected utilities across all adaptive policies is bounded above.

    We choose the candidate bound B = ∑ i, ∑ v ∈ (inst.dist i).support, v. Since all prize values are non-negative, B ≥ 0, and every possible revealed prize value v is a single term in this finite sum and therefore satisfies v ≤ B. Applying `opt_dtd_le_opt_dus_aux_bound` with empty history, the expected utility of every policy π is bounded above by B.

    lines 51–66

    uses opt_dtd_le_opt_dus_aux_bound, Finset.sum_nonneg, le_trans, Finset.single_le_sum, Finset.mem_univ

    /-- The family of deferred-until-stopping expected utilities over all policies is bounded above
    by the total mass of the value distributions. -/
    lemma opt_dtd_le_opt_dus_bddAbove (inst : PandoraDeadlineInstance) :
        BddAbove (Set.range fun π : AdaptivePolicy inst.n => expectedUtilityDUS inst π) := by
      refine ⟨∑ i : Fin inst.n, ∑ v ∈ (inst.dist i).support, v, ?_⟩
      rintro _ ⟨π, rfl⟩
      apply opt_dtd_le_opt_dus_aux_bound inst _ ?_ ?_ π [] (by simp)
      · exact Finset.sum_nonneg fun i _ => Finset.sum_nonneg fun v hv => (inst.dist i).val_nonneg v hv
      · intro i v hv
        refine le_trans (Finset.single_le_sum (f := fun v => v)
          (fun v hv => (inst.dist i).val_nonneg v hv) hv) ?_
        exact Finset.single_le_sum (f := fun i => ∑ v ∈ (inst.dist i).support, v)
          (fun i _ => Finset.sum_nonneg fun v hv => (inst.dist i).val_nonneg v hv) (Finset.mem_univ i)
    
    /-- The deferred-to-deadline optimum is at most the deferred-until-stopping optimum. -/
  6. The policy-indexed family of suprema ⨆ (_ : IsValidPolicy inst π), expectedUtilityDUS inst π is bounded above.

    By `BddAbove.range_iSup_of_iUnion_range`, it suffices to bound the union of ranges over all valid policies. Every element of this union is the expected utility of some policy under deferred-until-stopping commitment, so the global bound from `opt_dtd_le_opt_dus_bddAbove` bounds the entire union.

    lines 67–77

    uses BddAbove.range_iSup_of_iUnion_range, opt_dtd_le_opt_dus_bddAbove, Set.mem_iUnion, Set.mem_range, Set.mem_range_self

    theorem opt_dtd_le_opt_dus (inst : PandoraDeadlineInstance) :
        optDTD inst ≤ optDUS inst := by
      have hbdd : BddAbove (Set.range fun π : AdaptivePolicy inst.n =>
          ⨆ (_ : IsValidPolicy inst π), expectedUtilityDUS inst π) := by
        refine BddAbove.range_iSup_of_iUnion_range ?_
        obtain ⟨B, hB⟩ := opt_dtd_le_opt_dus_bddAbove inst
        refine ⟨B, ?_⟩
        intro x hx
        simp only [Set.mem_iUnion, Set.mem_range] at hx
        obtain ⟨π, -, rfl⟩ := hx
        exact hB (Set.mem_range_self π)
  7. The optimal expected utility under deferred-to-deadline commitment is at most that under deferred-until-stopping commitment: optDTD inst ≤ optDUS inst.

    Unfolding `optDTD` and `optDUS`, we apply monotonicity of the supremum (`ciSup_mono`) using the boundedness established in the previous step. For each policy π, we split into cases on whether π is valid: if π is valid, the inner supremum simplifies via `ciSup_const` to `expectedUtilityDTD inst π`, which by `expected_utility_dtd_le_dus` is at most `expectedUtilityDUS inst π`, and this in turn is at most the supremum over valid policies by `le_ciSup`. If π is invalid, both inner suprema are over an empty type and both evaluate to sSup ∅ by `iSup_of_empty'`.

    lines 78–89

    uses ciSup_mono, ciSup_const, expected_utility_dtd_le_dus, le_ciSup, le_rfl, iSup_of_empty'

      unfold optDTD optDUS
      refine ciSup_mono hbdd (fun π => ?_)
      by_cases hv : IsValidPolicy inst π
      · have hn : Nonempty (IsValidPolicy inst π) := ⟨hv⟩
        calc (⨆ (_ : IsValidPolicy inst π), expectedUtilityDTD inst π) = expectedUtilityDTD inst π :=
              ciSup_const
          _ ≤ expectedUtilityDUS inst π := expected_utility_dtd_le_dus inst π
          _ ≤ ⨆ (_ : IsValidPolicy inst π), expectedUtilityDUS inst π :=
              le_ciSup ⟨expectedUtilityDUS inst π, by rintro _ ⟨_, rfl⟩; exact le_rfl⟩ hv
      · have he : IsEmpty (IsValidPolicy inst π) := ⟨fun h => hv h⟩
        rw [iSup_of_empty' (fun _ : IsValidPolicy inst π => expectedUtilityDTD inst π),
          iSup_of_empty' (fun _ : IsValidPolicy inst π => expectedUtilityDUS inst π)]
List.foldl_cons
Folding an operation over a list `a :: l` starting from accumulator `b` equals folding over `l` starting from `f b a`.
le_trans
Inequality is transitive: if a ≤ b and b ≤ c, then a ≤ c.
opt_dtd_le_opt_dus_foldl_max_le
Folding `max` over a list whose second components are all bounded by M, starting from x, is at most max(x, M).
List.mem_cons_of_mem
An element of a list l is also an element of y :: l.
max_assoc
The maximum operation on a linear order is associative: max(max(a, b), c) = max(a, max(b, c)).
max_eq_right
If a ≤ b, then max(a, b) = b.
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 an inequality b ≤ c on the left by a non-negative number a preserves the inequality: a * b ≤ a * c.
List.mem_cons.mp
An element of a cons list a :: l is either equal to a or belongs to l.
Finset.sum_mul
Multiplication by a constant distributes over finite summation on the right: (∑ i ∈ s, f i) * a = ∑ i ∈ s, f i * a.
one_mul
Multiplying any element by 1 on the left leaves it unchanged: 1 * a = a.
opt_dtd_le_opt_dus_aux_bound
If all values in the support of every box distribution are bounded by M ≥ 0, then the deferred-until-stopping expected utility of any policy from any history bounded by M is at most M.
Finset.sum_nonneg
A finite sum of non-negative elements is non-negative.
Finset.single_le_sum
Any single term in a finite sum of non-negative elements is at most the total sum.
Finset.mem_univ
Every element of a finite type belongs to its universal finset Finset.univ.
BddAbove.range_iSup_of_iUnion_range
If the union of the ranges of a family of functions is bounded above, then the range of their pointwise suprema is also bounded above.
opt_dtd_le_opt_dus_bddAbove
The set of expected utilities under deferred-until-stopping commitment across all adaptive policies is bounded above.
Set.mem_iUnion
An element belongs to an indexed union if and only if it belongs to at least one set in the family.
Set.mem_range
An element belongs to the range of a function if and only if it is the image of some input.
Set.mem_range_self
Every value in the image of a function belongs to the range of that function.
ciSup_mono
If g has a range that is bounded above and f(x) ≤ g(x) pointwise, then ⨆ x, f x ≤ ⨆ x, g x.
ciSup_const
The supremum of a constant function over a nonempty index type equals the constant itself.
expected_utility_dtd_le_dus
For every adaptive policy π, its expected utility under deferred-to-deadline commitment is at most its expected utility under deferred-until-stopping commitment.
le_ciSup
Any value in the range of a function that is bounded above is at most the supremum of that function.
le_rfl
The order relation ≤ is reflexive: a ≤ a.
iSup_of_empty'
The supremum of a function indexed by an empty type equals the supremum of the empty set.

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

open Finset in/-- A `List.foldl` of `max` starting at `x` is at most `max x M` when every entry is at most `M`. -/lemma opt_dtd_le_opt_dus_foldl_max_le {α : Type*} :    ∀ (l : List (α × ℝ)) (x M : ℝ), (∀ bv ∈ l, bv.2 ≤ M) →      List.foldl (fun acc bv => max acc bv.2) x l ≤ max x M  | [], x, M, _ => by simp  | hd :: tl, x, M, h => by      have h1 : hd.2 ≤ M := h hd (by simp)      simp only [List.foldl_cons]      refine le_trans (opt_dtd_le_opt_dus_foldl_max_le tl (max x hd.2) M        (fun bv hbv => h bv (List.mem_cons_of_mem _ hbv))) ?_      rw [max_assoc, max_eq_right h1]/-- If every value that can be revealed lies below `M ≥ 0`, then the deferred-until-stoppingexpected utility of any policy is at most `M`. -/lemma opt_dtd_le_opt_dus_aux_bound (inst : PandoraDeadlineInstance) (M : ℝ)    (hM0 : 0 ≤ M) (hMv : ∀ (i : Fin inst.n) (v : ℝ), v ∈ (inst.dist i).support → v ≤ M) :    ∀ (a : AdaptivePolicy inst.n) (hist : List (Fin inst.n × ℝ)),      (∀ bv ∈ hist, bv.2 ≤ M) → expectedUtilityDUS.aux inst hist a ≤ M := by  intro a  induction a using AdaptivePolicy.rec with  | stop =>      intro hist hh      rw [show expectedUtilityDUS.aux inst hist (AdaptivePolicy.stop : AdaptivePolicy inst.n)          = List.foldl (fun acc bv => max acc bv.2) 0 hist from rfl]      exact le_trans (opt_dtd_le_opt_dus_foldl_max_le hist 0 M hh) (by rw [max_eq_right hM0])  | openBox b cont ih =>      intro hist hh      rw [show expectedUtilityDUS.aux inst hist (AdaptivePolicy.openBox b cont) =        ∑ v ∈ (inst.dist b).support, (inst.dist b).prob v *          expectedUtilityDUS.aux inst ((b, v) :: hist) (cont v) - inst.cost b from rfl]      have hsum : ∑ v ∈ (inst.dist b).support, (inst.dist b).prob v *            expectedUtilityDUS.aux inst ((b, v) :: hist) (cont v) ≤ M := by        have h1 : ∑ v ∈ (inst.dist b).support, (inst.dist b).prob v *            expectedUtilityDUS.aux inst ((b, v) :: hist) (cont v)            ≤ ∑ v ∈ (inst.dist b).support, (inst.dist b).prob v * M := by          apply Finset.sum_le_sum          intro v hv          apply mul_le_mul_of_nonneg_left _ ((inst.dist b).prob_nonneg v hv)          exact ih v ((b, v) :: hist) (fun bv hbv => by            rcases List.mem_cons.mp hbv with hmem | hmem            · rw [hmem]; exact hMv b v hv            · exact hh bv hmem)        calc ∑ v ∈ (inst.dist b).support, (inst.dist b).prob v *              expectedUtilityDUS.aux inst ((b, v) :: hist) (cont v)            ≤ ∑ v ∈ (inst.dist b).support, (inst.dist b).prob v * M := h1          _ = (∑ v ∈ (inst.dist b).support, (inst.dist b).prob v) * M := by                rw [Finset.sum_mul]          _ = M := by rw [(inst.dist b).sum_prob_one, one_mul]      linarith [inst.cost_nonneg b]/-- The family of deferred-until-stopping expected utilities over all policies is bounded aboveby the total mass of the value distributions. -/lemma opt_dtd_le_opt_dus_bddAbove (inst : PandoraDeadlineInstance) :    BddAbove (Set.range fun π : AdaptivePolicy inst.n => expectedUtilityDUS inst π) := by  refine ⟨∑ i : Fin inst.n, ∑ v ∈ (inst.dist i).support, v, ?_⟩  rintro _ ⟨π, rfl⟩  apply opt_dtd_le_opt_dus_aux_bound inst _ ?_ ?_ π [] (by simp)  · exact Finset.sum_nonneg fun i _ => Finset.sum_nonneg fun v hv => (inst.dist i).val_nonneg v hv  · intro i v hv    refine le_trans (Finset.single_le_sum (f := fun v => v)      (fun v hv => (inst.dist i).val_nonneg v hv) hv) ?_    exact Finset.single_le_sum (f := fun i => ∑ v ∈ (inst.dist i).support, v)      (fun i _ => Finset.sum_nonneg fun v hv => (inst.dist i).val_nonneg v hv) (Finset.mem_univ i)/-- The deferred-to-deadline optimum is at most the deferred-until-stopping optimum. -/theorem opt_dtd_le_opt_dus (inst : PandoraDeadlineInstance) :    optDTD inst ≤ optDUS inst := by  have hbdd : BddAbove (Set.range fun π : AdaptivePolicy inst.n =>      ⨆ (_ : IsValidPolicy inst π), expectedUtilityDUS inst π) := by    refine BddAbove.range_iSup_of_iUnion_range ?_    obtain ⟨B, hB⟩ := opt_dtd_le_opt_dus_bddAbove inst    refine ⟨B, ?_⟩    intro x hx    simp only [Set.mem_iUnion, Set.mem_range] at hx    obtain ⟨π, -, rfl⟩ := hx    exact hB (Set.mem_range_self π)  unfold optDTD optDUS  refine ciSup_mono hbdd (fun π => ?_)  by_cases hv : IsValidPolicy inst π  · have hn : Nonempty (IsValidPolicy inst π) := ⟨hv⟩    calc (⨆ (_ : IsValidPolicy inst π), expectedUtilityDTD inst π) = expectedUtilityDTD inst π :=          ciSup_const      _ ≤ expectedUtilityDUS inst π := expected_utility_dtd_le_dus inst π      _ ≤ ⨆ (_ : IsValidPolicy inst π), expectedUtilityDUS inst π :=          le_ciSup ⟨expectedUtilityDUS inst π, by rintro _ ⟨_, rfl⟩; exact le_rfl⟩ hv  · have he : IsEmpty (IsValidPolicy inst π) := ⟨fun h => hv h⟩    rw [iSup_of_empty' (fun _ : IsValidPolicy inst π => expectedUtilityDTD inst π),      iSup_of_empty' (fun _ : IsValidPolicy inst π => expectedUtilityDUS inst π)]
See it in the graphDiscuss this resultChallenge it