AFTD Auto-Formalizing Theoretical Domains

pandora_exists_balancing_threshold

theoremverified

There is a threshold t >= 0 at which the maximum total capped surplus over deadline-feasible sets equals t, attained by some feasible set.

Statement

theorem pandora_exists_balancing_threshold (inst : PandoraDeadlineInstance)
    (r : Fin inst.n → ℝ) :
    ∃ t : ℝ, 0 ≤ t ∧ ∃ S : Finset (Fin inst.n), pandora_deadline_feasible inst S ∧
      ∑ i ∈ S, pandora_capped_surplus inst r i t = t ∧
      ∀ S' : Finset (Fin inst.n), pandora_deadline_feasible inst S' →
        ∑ i ∈ S', pandora_capped_surplus inst r i t ≤ t
Source
Helper for op184_partially_adaptive_half_approximation: arXiv:2610.13775 Section 3, Theorem 1 proof (choice of the balancing threshold t*)
Verified
26 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 11
  • 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…
  • 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.
  • IsPartiallyAdaptiveA search policy π : AdaptivePolicy n for Pandora's problem is partially adaptive if there exists a predetermined ordered list of boxes…
  • expectedUtilityDUSThe expected net utility of an adaptive policy π : AdaptivePolicy inst.n under deferred-until-stopping commitment on a Pandora's problem…
  • pandora_capped_surplusThe reservation-capped threshold surplus of box i at threshold t: w_i(t) = E[(min(v_i, r_i) - t)^+].
  • pandora_deadline_feasibleA set S of boxes is deadline-feasible if for every j at most j of its boxes have deadline at most j (equivalently, by Lemma 2, its boxes…
  • LinearOrder.toTotalPreorderEvery LinearOrder is a TotalPreorder.
  • TotalPreorderA total preorder: a preorder where ≤ is total (complete). This is weaker than LinearOrder — it does NOT require antisymmetry or…
  • pandora_deadline_feasible_emptySanity: the empty set of boxes is deadline-feasible.
Used by 1

The proof, explained

The theorem establishes the existence of a balancing threshold t ≥ 0 at which the maximum total capped surplus over all deadline-feasible sets equals t, attained by some feasible set. Defining W(t) as the maximum total capped surplus over the finite, nonempty family of deadline-feasible sets, helper lemmas show that W is continuous and antitone because individual capped surpluses have these properties and finite sums and suprema preserve them. The difference function g(t) = W(t) - t is continuous with g(0) ≥ 0 and g(b) ≤ 0 at b = W(0) + 1, so the Intermediate Value Theorem provides a root t ≥ 0 where W(t) = t. Finally, since the family of feasible sets is finite, this supremum is attained by an actual feasible set, while bounding all other feasible sets by t.

  1. The pointwise supremum of a nonempty finite family of continuous functions is continuous.

    We proceed by induction on the nonempty finite set s using Finset.Nonempty.cons_induction. For a singleton {a}, the supremum reduces to f(a, ·) by Finset.sup'_singleton, which is continuous by hypothesis. For cons a t ha, the supremum splits into max(f(a, ·), sup_{i ∈ t} f(i, ·)) by Finset.sup'_cons; this is continuous as the binary maximum of two continuous functions via Continuous.sup and the induction hypothesis.

    lines 6–16

    uses Finset.Nonempty.cons_induction, Finset.sup'_singleton, Finset.mem_singleton_self, Finset.sup'_cons, Continuous.sup, Finset.mem_cons_self, Finset.mem_cons_of_mem

      induction hs using Finset.Nonempty.cons_induction with
      | singleton a =>
        simp only [Finset.sup'_singleton]
        apply hf a (Finset.mem_singleton_self a)
      | cons a t ha ht ih =>
        simp only [Finset.sup'_cons ht]
        apply Continuous.sup
        · apply hf a (Finset.mem_cons_self a t)
        · apply ih
          intro i hi
          apply hf i (Finset.mem_cons_of_mem hi)
  2. The pointwise supremum of a nonempty finite family of antitone functions is antitone.

    Let t₁ ≤ t₂. By Finset.sup'_le, it suffices to show that f(i, t₂) ≤ sup_{j ∈ s} f(j, t₁) for each i ∈ s. Since each f(i, ·) is antitone, f(i, t₂) ≤ f(i, t₁), and f(i, t₁) is bounded by the supremum over s by Finset.le_sup'. The result follows by transitivity (le_trans).

    lines 23–28

    uses Finset.sup'_le, Finset.le_sup', le_trans

      intro t1 t2 hle
      apply Finset.sup'_le
      intro i hi
      have hle' := hf i hi hle
      have hsup := Finset.le_sup' (fun j => f j t1) hi
      exact le_trans hle' hsup
  3. For each box i, the capped surplus function is continuous in the threshold t. automation

    Unfolding the definition shows the capped surplus is a finite linear combination of terms of the form p_i(v) * max(min(v, r_i) - t, 0). The continuity tactic establishes continuity by combining the continuity of the identity, constants, subtraction, minimum, and maximum.

    lines 33–34

      unfold pandora_capped_surplus
      continuity
  4. For any finite set of boxes S, the total capped surplus is continuous in t.

    A finite sum of continuous functions is continuous by continuous_finsetSum, using the continuity of each individual box's capped surplus proved in the previous lemma.

    lines 39–41

    uses continuous_finsetSum, pandora_exists_balancing_threshold_capped_surplus_continuous

      apply continuous_finsetSum
      intro i _
      exact pandora_exists_balancing_threshold_capped_surplus_continuous inst r i
  5. For each box i, the capped surplus function is antitone in the threshold t.

    For t₁ ≤ t₂, comparing the sum term by term via Finset.sum_le_sum reduces to checking each value v. Since t₁ ≤ t₂, linear arithmetic gives min(v, r_i) - t₂ ≤ min(v, r_i) - t₁, so max(min(v, r_i) - t₂, 0) ≤ max(min(v, r_i) - t₁, 0) by max_le_max. Multiplying by the non-negative probability preserves the inequality by mul_le_mul_of_nonneg_left.

    lines 46–54

    uses Finset.sum_le_sum, mul_le_mul_of_nonneg_left, max_le_max

      intro t1 t2 hle
      dsimp [pandora_capped_surplus]
      apply Finset.sum_le_sum
      intro v hv
      apply mul_le_mul_of_nonneg_left
      · apply max_le_max
        · linarith
        · rfl
      · exact (inst.dist i).prob_nonneg v hv
  6. For any finite set of boxes S, the total capped surplus is antitone in t.

    For t₁ ≤ t₂, the sum at t₂ is bounded by the sum at t₁ by applying Finset.sum_le_sum and the antitone property of each individual box's capped surplus.

    lines 59–62

    uses Finset.sum_le_sum, pandora_exists_balancing_threshold_capped_surplus_antitone

      intro t1 t2 hle
      apply Finset.sum_le_sum
      intro i _
      exact pandora_exists_balancing_threshold_capped_surplus_antitone inst r i hle
  7. The family F of deadline-feasible sets is nonempty, and the supremum function W(t) = max_{S ∈ F} ∑_{i ∈ S} capped_surplus(i, t) is continuous and antitone.

    We define F by filtering the power set of boxes by deadline feasibility. The empty set is feasible by pandora_deadline_feasible_empty, so F is nonempty. For each S ∈ F, the sum of capped surpluses is continuous and antitone by the earlier sum lemmas. Therefore, by the finite supremum lemmas pandora_exists_balancing_threshold_continuous_finset_sup' and pandora_exists_balancing_threshold_antitone_finset_sup', the supremum W(t) is both continuous and antitone.

    lines 70–81

    uses Finset.mem_filter.mpr, Finset.mem_univ, pandora_deadline_feasible_empty, pandora_exists_balancing_threshold_continuous_finset_sup', pandora_exists_balancing_threshold_capped_surplus_sum_continuous, pandora_exists_balancing_threshold_antitone_finset_sup', pandora_exists_balancing_threshold_capped_surplus_sum_antitone

      classical
      let F : Finset (Finset (Fin inst.n)) := Finset.filter (pandora_deadline_feasible inst) Finset.univ
      have hF_mem_empty : ∅ ∈ F := Finset.mem_filter.mpr ⟨Finset.mem_univ ∅, pandora_deadline_feasible_empty inst⟩
      have hF : F.Nonempty := ⟨∅, hF_mem_empty⟩
      let term (S : Finset (Fin inst.n)) (t : ℝ) : ℝ := ∑ i ∈ S, pandora_capped_surplus inst r i t
      let W (t : ℝ) : ℝ := F.sup' hF (fun S => term S t)
      have hW_cont : Continuous W :=
        pandora_exists_balancing_threshold_continuous_finset_sup' F hF term
          (fun S _ => pandora_exists_balancing_threshold_capped_surplus_sum_continuous inst r S)
      have hW_anti : Antitone W :=
        pandora_exists_balancing_threshold_antitone_finset_sup' F hF term
          (fun S _ => pandora_exists_balancing_threshold_capped_surplus_sum_antitone inst r S)
  8. The difference function g(t) = W(t) - t is continuous, with g(0) ≥ 0 and g(b) ≤ 0 for b = W(0) + 1.

    The function g is continuous as the difference of W and the identity function (continuous_id). Since ∅ ∈ F and its surplus sum is 0 (Finset.sum_empty), Finset.le_sup' implies 0 ≤ W(0), so g(0) = W(0) - 0 ≥ 0. At b = W(0) + 1, since 0 ≤ b and W is antitone, W(b) ≤ W(0), which gives g(b) = W(b) - b ≤ W(0) - (W(0) + 1) = -1 ≤ 0.

    lines 82–96

    uses continuous_id, Finset.sum_empty, Finset.le_sup'

      let g (t : ℝ) : ℝ := W t - t
      have hg_cont : Continuous g := hW_cont.sub continuous_id
      let b := W 0 + 1
      have hW0_nonneg : 0 ≤ W 0 := by
        have hzero : term ∅ 0 = 0 := Finset.sum_empty
        have := Finset.le_sup' (fun S => term S 0) hF_mem_empty
        linarith
      have hab : 0 ≤ b := by linarith
      have hga : 0 ≤ g 0 := by
        dsimp [g]
        linarith
      have hgb : g b ≤ 0 := by
        dsimp [g, b]
        have := hW_anti hab
        linarith
  9. There exists a threshold t ≥ 0 such that W(t) = t.

    Because g(b) ≤ 0 ≤ g(0) and g is continuous on [0, b], the Intermediate Value Theorem (intermediate_value_Icc') guarantees a root t ∈ [0, b] where g(t) = 0. Hence t ≥ 0 and W(t) - t = 0, giving W(t) = t.

    lines 97–103

    uses intermediate_value_Icc'

      have h_mem : (0 : ℝ) ∈ Set.Icc (g b) (g 0) := ⟨hgb, hga⟩
      have hivt := intermediate_value_Icc' hab hg_cont.continuousOn h_mem
      rcases hivt with ⟨t, ht_icc, ht_eq⟩
      have ht_nonneg : 0 ≤ t := ht_icc.1
      have hWt : W t = t := by
        dsimp [g] at ht_eq
        linarith
  10. The supremum W(t) = t is attained by a feasible set S, and every feasible set S' has total surplus at most t.

    Since F is finite and nonempty, Finset.exists_mem_eq_sup' yields a set S ∈ F attaining the supremum: its total capped surplus equals W(t) = t. Unfolding membership in F shows S is deadline-feasible. For any other feasible set S', S' ∈ F, so its total surplus is bounded by W(t) = t using Finset.le_sup' and le_trans.

    lines 104–113

    uses Finset.exists_mem_eq_sup', Finset.mem_filter, Finset.mem_filter.mpr, Finset.mem_univ, Finset.le_sup', le_trans, le_of_eq

      obtain ⟨S, hS_mem, hS_eq⟩ := Finset.exists_mem_eq_sup' hF (fun S' => term S' t)
      rw [Finset.mem_filter] at hS_mem
      refine ⟨t, ht_nonneg, S, hS_mem.2, ?_, ?_⟩
      · change term S t = t
        rw [← hS_eq]
        exact hWt
      · intro S' hS'
        have hS'_mem : S' ∈ F := Finset.mem_filter.mpr ⟨Finset.mem_univ S', hS'⟩
        have hle := Finset.le_sup' (fun S'' => term S'' t) hS'_mem
        exact le_trans hle (le_of_eq hWt)
Finset.Nonempty.cons_induction
Induction principle for nonempty finite sets: a property holds for all nonempty finite sets if it holds for singletons and is preserved under adjoining a new element.
Finset.sup'_singleton
The supremum of a function over a singleton set {b} equals the function's value at b.
Finset.mem_singleton_self
Any element a belongs to the singleton set {a}.
Finset.sup'_cons
The supremum over a set cons b s hb equals the binary maximum of f(b) and the supremum over s.
Continuous.sup
The pointwise maximum of two continuous functions into a space with continuous binary supremum is continuous.
Finset.mem_cons_self
The newly adjoined element a belongs to cons a s h.
Finset.mem_cons_of_mem
If an element belongs to s, it also belongs to cons b s hb.
Finset.sup'_le
The supremum of f over a nonempty finite set s is bounded by a if and only if f(b) ≤ a for all b in s.
Finset.le_sup'
For any element b in a finite set s, f(b) is at most the supremum of f over s.
le_trans
If a ≤ b and b ≤ c, then a ≤ c (transitivity of preorder).
continuous_finsetSum
A finite sum of continuous functions into a topological additive monoid with continuous addition is continuous.
pandora_exists_balancing_threshold_capped_surplus_continuous
For each box i in a Pandora deadline instance, the capped surplus function is continuous in the threshold t.
Finset.sum_le_sum
If f(i) ≤ g(i) for all elements i in a finite set s, then the sum of f over s is at most the sum of g over s.
mul_le_mul_of_nonneg_left
Multiplication on the left by a non-negative element preserves inequality: if b ≤ c and 0 ≤ a, then a * b ≤ a * c.
max_le_max
The binary maximum operation is monotone: if a ≤ c and b ≤ d, then max(a, b) ≤ max(c, d).
pandora_exists_balancing_threshold_capped_surplus_antitone
For each box i in a Pandora deadline instance, the capped surplus function is antitone (monotonically non-increasing) in the threshold t.
Finset.mem_filter.mpr
If x ∈ s and p(x) holds, then x belongs to the filtered set s.filter p.
Finset.mem_univ
Every element of a finite type belongs to the universal finset Finset.univ.
pandora_deadline_feasible_empty
The empty set of boxes is deadline-feasible.
pandora_exists_balancing_threshold_continuous_finset_sup'
The pointwise supremum over a nonempty finite set of continuous functions is continuous.
pandora_exists_balancing_threshold_capped_surplus_sum_continuous
The sum of capped surpluses over any finite set of boxes is continuous in the threshold t.
pandora_exists_balancing_threshold_antitone_finset_sup'
The pointwise supremum over a nonempty finite set of antitone functions is antitone.
pandora_exists_balancing_threshold_capped_surplus_sum_antitone
The sum of capped surpluses over any finite set of boxes is antitone in the threshold t.
continuous_id
The identity function on a topological space is continuous.
Finset.sum_empty
The sum of any function over the empty finset is 0.
intermediate_value_Icc'
Intermediate Value Theorem: for a continuous function on [a, b], the interval between f(b) and f(a) is contained in the image of [a, b].
Finset.exists_mem_eq_sup'
The supremum of a function over a nonempty finite set is attained at some element of the set.
Finset.mem_filter
An element a belongs to s.filter p if and only if a ∈ s and p(a) holds.
le_of_eq
If a = b, 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

lemma pandora_exists_balancing_threshold_continuous_finset_sup' {α β γ : Type*}    [TopologicalSpace α] [LinearOrder β] [TopologicalSpace β] [ContinuousSup β]    (s : Finset γ) (hs : s.Nonempty) (f : γ → α → β)    (hf : ∀ i ∈ s, Continuous (f i)) :    Continuous (fun a => s.sup' hs (fun i => f i a)) := by  induction hs using Finset.Nonempty.cons_induction with  | singleton a =>    simp only [Finset.sup'_singleton]    apply hf a (Finset.mem_singleton_self a)  | cons a t ha ht ih =>    simp only [Finset.sup'_cons ht]    apply Continuous.sup    · apply hf a (Finset.mem_cons_self a t)    · apply ih      intro i hi      apply hf i (Finset.mem_cons_of_mem hi)lemma pandora_exists_balancing_threshold_antitone_finset_sup' {α β γ : Type*}    [LinearOrder β] [Preorder α]    (s : Finset γ) (hs : s.Nonempty) (f : γ → α → β)    (hf : ∀ i ∈ s, Antitone (f i)) :    Antitone (fun a => s.sup' hs (fun i => f i a)) := by  intro t1 t2 hle  apply Finset.sup'_le  intro i hi  have hle' := hf i hi hle  have hsup := Finset.le_sup' (fun j => f j t1) hi  exact le_trans hle' hsuplemma pandora_exists_balancing_threshold_capped_surplus_continuous (inst : PandoraDeadlineInstance)    (r : Fin inst.n → ℝ) (i : Fin inst.n) :    Continuous (pandora_capped_surplus inst r i) := by  unfold pandora_capped_surplus  continuitylemma pandora_exists_balancing_threshold_capped_surplus_sum_continuous (inst : PandoraDeadlineInstance)    (r : Fin inst.n → ℝ) (S : Finset (Fin inst.n)) :    Continuous (fun t => ∑ i ∈ S, pandora_capped_surplus inst r i t) := by  apply continuous_finsetSum  intro i _  exact pandora_exists_balancing_threshold_capped_surplus_continuous inst r ilemma pandora_exists_balancing_threshold_capped_surplus_antitone (inst : PandoraDeadlineInstance)    (r : Fin inst.n → ℝ) (i : Fin inst.n) :    Antitone (pandora_capped_surplus inst r i) := by  intro t1 t2 hle  dsimp [pandora_capped_surplus]  apply Finset.sum_le_sum  intro v hv  apply mul_le_mul_of_nonneg_left  · apply max_le_max    · linarith    · rfl  · exact (inst.dist i).prob_nonneg v hvlemma pandora_exists_balancing_threshold_capped_surplus_sum_antitone (inst : PandoraDeadlineInstance)    (r : Fin inst.n → ℝ) (S : Finset (Fin inst.n)) :    Antitone (fun t => ∑ i ∈ S, pandora_capped_surplus inst r i t) := by  intro t1 t2 hle  apply Finset.sum_le_sum  intro i _  exact pandora_exists_balancing_threshold_capped_surplus_antitone inst r i hletheorem pandora_exists_balancing_threshold (inst : PandoraDeadlineInstance)    (r : Fin inst.n → ℝ) :    ∃ t : ℝ, 0 ≤ t ∧ ∃ S : Finset (Fin inst.n), pandora_deadline_feasible inst S ∧      ∑ i ∈ S, pandora_capped_surplus inst r i t = t ∧      ∀ S' : Finset (Fin inst.n), pandora_deadline_feasible inst S' →        ∑ i ∈ S', pandora_capped_surplus inst r i t ≤ t := by  classical  let F : Finset (Finset (Fin inst.n)) := Finset.filter (pandora_deadline_feasible inst) Finset.univ  have hF_mem_empty : ∅ ∈ F := Finset.mem_filter.mpr ⟨Finset.mem_univ ∅, pandora_deadline_feasible_empty inst⟩  have hF : F.Nonempty := ⟨∅, hF_mem_empty⟩  let term (S : Finset (Fin inst.n)) (t : ℝ) : ℝ := ∑ i ∈ S, pandora_capped_surplus inst r i t  let W (t : ℝ) : ℝ := F.sup' hF (fun S => term S t)  have hW_cont : Continuous W :=    pandora_exists_balancing_threshold_continuous_finset_sup' F hF term      (fun S _ => pandora_exists_balancing_threshold_capped_surplus_sum_continuous inst r S)  have hW_anti : Antitone W :=    pandora_exists_balancing_threshold_antitone_finset_sup' F hF term      (fun S _ => pandora_exists_balancing_threshold_capped_surplus_sum_antitone inst r S)  let g (t : ℝ) : ℝ := W t - t  have hg_cont : Continuous g := hW_cont.sub continuous_id  let b := W 0 + 1  have hW0_nonneg : 0 ≤ W 0 := by    have hzero : term ∅ 0 = 0 := Finset.sum_empty    have := Finset.le_sup' (fun S => term S 0) hF_mem_empty    linarith  have hab : 0 ≤ b := by linarith  have hga : 0 ≤ g 0 := by    dsimp [g]    linarith  have hgb : g b ≤ 0 := by    dsimp [g, b]    have := hW_anti hab    linarith  have h_mem : (0 : ℝ) ∈ Set.Icc (g b) (g 0) := ⟨hgb, hga⟩  have hivt := intermediate_value_Icc' hab hg_cont.continuousOn h_mem  rcases hivt with ⟨t, ht_icc, ht_eq⟩  have ht_nonneg : 0 ≤ t := ht_icc.1  have hWt : W t = t := by    dsimp [g] at ht_eq    linarith  obtain ⟨S, hS_mem, hS_eq⟩ := Finset.exists_mem_eq_sup' hF (fun S' => term S' t)  rw [Finset.mem_filter] at hS_mem  refine ⟨t, ht_nonneg, S, hS_mem.2, ?_, ?_⟩  · change term S t = t    rw [← hS_eq]    exact hWt  · intro S' hS'    have hS'_mem : S' ∈ F := Finset.mem_filter.mpr ⟨Finset.mem_univ S', hS'⟩    have hle := Finset.le_sup' (fun S'' => term S'' t) hS'_mem    exact le_trans hle (le_of_eq hWt)
See it in the graphDiscuss this resultChallenge it