pandora_exists_balancing_threshold
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 nfor 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.nunder 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
LinearOrderis aTotalPreorder. - TotalPreorderA total preorder: a preorder where
≤is total (complete). This is weaker thanLinearOrder— it does NOT require antisymmetry or… - pandora_deadline_feasible_emptySanity: the empty set of boxes is deadline-feasible.
- Used by 1
- op184_partially_adaptive_half_approximationFor every Pandora's problem instance with deadlines
inst : PandoraDeadlineInstance, there exists a valid partially adaptive policy…
- op184_partially_adaptive_half_approximationFor every Pandora's problem instance with deadlines
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.
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.
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_meminduction 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)
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).
uses
Finset.sup'_le,Finset.le_sup',le_transintro 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
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.
unfold pandora_capped_surplus continuityFor 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.
uses
continuous_finsetSum,pandora_exists_balancing_threshold_capped_surplus_continuousapply continuous_finsetSum intro i _ exact pandora_exists_balancing_threshold_capped_surplus_continuous inst r i
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.
uses
Finset.sum_le_sum,mul_le_mul_of_nonneg_left,max_le_maxintro 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
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.
uses
Finset.sum_le_sum,pandora_exists_balancing_threshold_capped_surplus_antitoneintro t1 t2 hle apply Finset.sum_le_sum intro i _ exact pandora_exists_balancing_threshold_capped_surplus_antitone inst r i hle
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.
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_antitoneclassical 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)
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.
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
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.
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
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.
uses
Finset.exists_mem_eq_sup',Finset.mem_filter,Finset.mem_filter.mpr,Finset.mem_univ,Finset.le_sup',le_trans,le_of_eqobtain ⟨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.
- The continuity of the single-box capped surplus (Step 3) is discharged entirely by Lean's continuity automation, which verifies that the finite linear combination of basic continuous operations (subtraction, minimum, maximum) is continuous.
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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
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)