AFTD Auto-Formalizing Theoretical Domains

pandora_threshold_policy_lower_bound

theoremverified

Lemma 3: for reservation values r, t >= 0 and a duplicate-free list of boxes each with positive capped surplus at t, the threshold policy has expected DUS utility at least min(t, total capped surplus of the list).

Statement

theorem pandora_threshold_policy_lower_bound (inst : PandoraDeadlineInstance)
    (r : Fin inst.n → ℝ) (hr : pandora_is_reservation inst r) (t : ℝ) (ht : 0 ≤ t)
    (order : List (Fin inst.n)) (hnd : order.Nodup)
    (hpos : ∀ i ∈ order, 0 < pandora_capped_surplus inst r i t) :
    min t (∑ i ∈ order.toFinset, pandora_capped_surplus inst r i t) ≤
      expectedUtilityDUS inst (pandora_threshold_policy order t)
Source
Helper for op184_partially_adaptive_half_approximation: arXiv:2610.13775 Section 3, Lemma 3 (threshold-surplus lower bound), with deferred-until-stopping commitment, which only helps
Verified
26 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 10
  • 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_is_reservationr is a vector of reservation values: for every box i, the expected excess E[(v_i - r_i)^+] of its value over r_i equals its opening cost…
  • pandora_capped_surplusThe reservation-capped threshold surplus of box i at threshold t: w_i(t) = E[(min(v_i, r_i) - t)^+].
  • pandora_threshold_policyThe threshold policy on a list of boxes: open them in the given order and stop as soon as an opened value exceeds t (stop after the last…
  • supportThe support $\mathrm{supp}(p) \subseteq \mathrm{Fin}\,n$ consists of coordinates where $p(i) \neq I$; the weight is…
Used by 1

The proof, explained

The theorem proves that for any reservation prices, threshold t ≥ 0, and duplicate-free list of boxes with positive capped surplus at t, the expected utility of the threshold policy is at least min(t, total capped surplus). The proof proceeds by list induction on the order of boxes, using a pointwise algebraic surplus decomposition at each box followed by a convex combination inequality for the minimum function. In the inductive step, if the opened box yields a value exceeding t the policy stops, and otherwise it continues with the remaining boxes where the induction hypothesis applies.

  1. Foldl of max over history commutes with max of the accumulator

    By induction on the history list, using associativity and commutativity of max.

    lines 4–11

    uses max_assoc, max_comm

      induction history generalizing acc with
      | nil => rfl
      | cons head tail ih =>
        show List.foldl (fun a bv => max a bv.2) (max (max acc v) head.2) tail =
          max (List.foldl (fun a bv => max a bv.2) (max acc head.2) tail) v
        have : max (max acc v) head.2 = max (max acc head.2) v := by
          rw [max_assoc, max_comm v, ← max_assoc]
        rw [this, ih]
  2. Prepending an element to history updates the history maximum

    Unfolding the history maximum definition and applying the foldl max lemma with initial accumulator 0.

    lines 19–20

    uses pandora_threshold_policy_lower_bound_foldl_max

      show List.foldl (fun a bv => max a bv.2) (max 0 v) history = _
      exact pandora_threshold_policy_lower_bound_foldl_max history 0 v
  3. The folded max is nonnegative if the accumulator is nonnegative

    By induction on history, since each step takes the max with an element.

    lines 24–28

    uses le_trans, le_max_left

      induction history generalizing acc with
      | nil => exact hacc
      | cons head tail ih =>
        apply ih
        exact le_trans hacc (le_max_left acc head.2)
  4. Pointwise surplus decomposition identity

    Case analysis on whether v exceeds t and whether v exceeds r.

    lines 37–57

    uses le_total, max_eq_right, min_eq_left, max_eq_left, min_eq_right, min_le_left

      have hid : (if t < v then v else U) = (if t < v then v else 0) + (if t < v then 0 else U) := by
        split_ifs <;> ring
      rw [hid]
      have h1 : (if t < v then v else 0) - max (v - r) 0 =
          (if t < v then t else 0) + max (min v r - t) 0 := by
        split_ifs with h
        · rcases le_total v r with hvr | hrv
          · have h2 : v - r ≤ 0 := by linarith
            rw [max_eq_right h2, min_eq_left hvr]
            have h3 : 0 ≤ v - t := by linarith
            rw [max_eq_left h3]; ring
          · have h2 : (0 : ℝ) ≤ v - r := by linarith
            rw [max_eq_left h2, min_eq_right hrv]
            have h3 : (0 : ℝ) ≤ r - t := by linarith
            rw [max_eq_left h3]; ring
        · have hle : v ≤ t := not_lt.mp h
          have hvr : v ≤ r := hle.trans htr
          have h2 : v - r ≤ 0 := by linarith
          have h3 : min v r - t ≤ 0 := by linarith [min_le_left v r]
          rw [max_eq_right h2, max_eq_right h3]; ring
      linarith
  5. Expectation of indicator and truncated values

    Distributing the probability sum over the indicator functions and using total probability 1.

    lines 64–84

    uses Finset.sum_nonneg, mul_nonneg, Finset.sum_congr, Finset.sum_mul, Finset.sum_sub_distrib

      intro p
      have hp_nonneg : 0 ≤ p := by
        apply Finset.sum_nonneg
        intro v hv
        have : 0 ≤ (if t < v then (1 : ℝ) else 0) := by split_ifs <;> linarith
        exact mul_nonneg (dist.prob_nonneg v hv) this
      have h1 : (∑ v ∈ dist.support, dist.prob v * (if t < v then t else 0)) = p * t := by
        dsimp [p]
        have hid : ∀ v ∈ dist.support, dist.prob v * (if t < v then t else 0) =
            (dist.prob v * (if t < v then 1 else 0)) * t := by
          intro v _
          split_ifs <;> ring
        rw [Finset.sum_congr rfl hid, ← Finset.sum_mul]
      have h2 : (∑ v ∈ dist.support, dist.prob v * (if t < v then 0 else U)) = (1 - p) * U := by
        dsimp [p]
        have hid : ∀ v ∈ dist.support, dist.prob v * (if t < v then 0 else U) =
            (dist.prob v - dist.prob v * (if t < v then 1 else 0)) * U := by
          intro v _
          split_ifs <;> ring
        rw [Finset.sum_congr rfl hid, ← Finset.sum_mul, Finset.sum_sub_distrib, dist.sum_prob_one]
      exact ⟨h1, h2, hp_nonneg⟩
  6. Decomposition of expected net surplus of opening a box

    Applying the pointwise identity to each value in the distribution and rewriting the reservation price equation.

    lines 91–120

    uses pandora_threshold_policy_lower_bound_pointwise_comb, Finset.sum_sub_distrib, Finset.sum_congr, Finset.sum_add_distrib, pandora_threshold_policy_lower_bound_sum_indicator_prop

      intro p
      have h_id : ∀ v ∈ dist.support,
          dist.prob v * (if t < v then v else U) - dist.prob v * max (v - r) 0 =
            dist.prob v * (if t < v then t else 0) +
            dist.prob v * max (min v r - t) 0 +
            dist.prob v * (if t < v then 0 else U) := by
        intro v _
        have h := pandora_threshold_policy_lower_bound_pointwise_comb v r t U htr
        calc dist.prob v * (if t < v then v else U) - dist.prob v * max (v - r) 0
          _ = dist.prob v * ((if t < v then v else U) - max (v - r) 0) := by ring
          _ = dist.prob v * ((if t < v then t else 0) + max (min v r - t) 0 + (if t < v then 0 else U)) := by rw [h]
          _ = dist.prob v * (if t < v then t else 0) +
              dist.prob v * max (min v r - t) 0 +
              dist.prob v * (if t < v then 0 else U) := by ring
      have h_sub : (∑ v ∈ dist.support, dist.prob v * (if t < v then v else U)) - c =
          ∑ v ∈ dist.support, (dist.prob v * (if t < v then v else U) - dist.prob v * max (v - r) 0) := by
        rw [← hres, Finset.sum_sub_distrib]
      rw [h_sub]
      have h_sum_id : (∑ v ∈ dist.support, (dist.prob v * (if t < v then v else U) - dist.prob v * max (v - r) 0)) =
          (∑ v ∈ dist.support, dist.prob v * (if t < v then t else 0)) +
          (∑ v ∈ dist.support, dist.prob v * max (min v r - t) 0) +
          (∑ v ∈ dist.support, dist.prob v * (if t < v then 0 else U)) := by
        rw [Finset.sum_congr rfl h_id]
        rw [Finset.sum_add_distrib, Finset.sum_add_distrib]
      rw [h_sum_id]
      have hp_eq : (∑ v ∈ dist.support, dist.prob v * (if t < v then t else 0)) = p * t :=
        (pandora_threshold_policy_lower_bound_sum_indicator_prop dist t U).1
      have hp_eq2 : (∑ v ∈ dist.support, dist.prob v * (if t < v then 0 else U)) = (1 - p) * U :=
        (pandora_threshold_policy_lower_bound_sum_indicator_prop dist t U).2.1
      rw [hp_eq, hp_eq2]
  7. Convexity inequality for the minimum

    Case split on whether t ≤ W or W ≤ t.

    lines 124–137

    uses le_total, min_eq_left, min_le_left, min_eq_right, min_le_right, mul_le_mul_of_nonneg_left

      rcases le_total t W with htW | hWt
      · rw [min_eq_left htW]
        have : min t (w + W) ≤ t := min_le_left t (w + W)
        have : t ≤ p * t + w + (1 - p) * t := by
          calc t = p * t + (1 - p) * t := by ring
          _ ≤ p * t + (1 - p) * t + w := by linarith
          _ = p * t + w + (1 - p) * t := by ring
        linarith
      · rw [min_eq_right hWt]
        have : min t (w + W) ≤ w + W := min_le_right t (w + W)
        have : w + W ≤ p * t + w + (1 - p) * W := by
          have : p * W ≤ p * t := mul_le_mul_of_nonneg_left hWt hp
          linarith
        linarith
  8. Positive capped surplus implies t ≤ r

    If r < t then min(v, r) ≤ r < t so the capped surplus integrand is everywhere nonpositive.

    lines 141–149

    uses Finset.sum_nonpos, min_le_right, max_eq_right

      by_contra! h
      have hzero : pandora_capped_surplus inst r i t ≤ 0 := by
        unfold pandora_capped_surplus
        apply Finset.sum_nonpos
        intro v hv
        have h1 : min v (r i) - t ≤ 0 := by linarith [min_le_right v (r i)]
        rw [max_eq_right h1]
        simp
      linarith
  9. Auxiliary induction base case

    When the order list is empty, the policy stops immediately with utility equal to the history maximum, which is at least min(t, 0) = 0.

    lines 158–169

    uses min_le_right, pandora_threshold_policy_lower_bound_history_max_nonneg

      induction order generalizing history with
      | nil =>
        have hnil : pandora_threshold_policy ([] : List (Fin inst.n)) t = AdaptivePolicy.stop := rfl
        rw [hnil]
        have haux : expectedUtilityDUS.aux inst history AdaptivePolicy.stop =
            pandora_threshold_policy_lower_bound_history_max history := rfl
        rw [haux]
        simp only [List.toFinset_nil, Finset.sum_empty]
        have : min t 0 ≤ 0 := min_le_right t 0
        have : 0 ≤ pandora_threshold_policy_lower_bound_history_max history :=
          pandora_threshold_policy_lower_bound_history_max_nonneg history
        linarith
  10. Auxiliary induction step: setup and convex inequality

    Splitting the list into head and rest, applying the reservation equation and the convex min inequality.

    lines 171–197

    uses pandora_threshold_policy_lower_bound_le_r_of_capped_surplus_pos, le_of_lt, Finset.sum_insert, pandora_threshold_policy_lower_bound_sum_indicator_prop, pandora_threshold_policy_lower_bound_convex_min_ineq, pandora_threshold_policy_lower_bound_sum_pointwise_comb

        have hb_notin : b ∉ rest := (List.nodup_cons.mp hnd).1
        have hnd_rest : rest.Nodup := (List.nodup_cons.mp hnd).2
        have hpos_b : 0 < pandora_capped_surplus inst r b t := hpos b (List.Mem.head rest)
        have hpos_rest : ∀ i ∈ rest, 0 < pandora_capped_surplus inst r i t :=
          fun i hi => hpos i (List.Mem.tail b hi)
        have htr : t ≤ r b := pandora_threshold_policy_lower_bound_le_r_of_capped_surplus_pos inst r b t hpos_b
        have hw_nonneg : 0 ≤ pandora_capped_surplus inst r b t := le_of_lt hpos_b
        have hnotin_toFinset : b ∉ rest.toFinset := by
          rw [List.mem_toFinset]
          exact hb_notin
        have h_sum : (∑ i ∈ (b :: rest).toFinset, pandora_capped_surplus inst r i t) =
            pandora_capped_surplus inst r b t + ∑ i ∈ rest.toFinset, pandora_capped_surplus inst r i t := by
          rw [List.toFinset_cons, Finset.sum_insert hnotin_toFinset]
        rw [h_sum]
        set w := pandora_capped_surplus inst r b t
        set W := ∑ i ∈ rest.toFinset, pandora_capped_surplus inst r i t
        set U := min t W
        set p := ∑ v ∈ (inst.dist b).support, (inst.dist b).prob v * (if t < v then (1 : ℝ) else 0)
        have hp_nonneg : 0 ≤ p := (pandora_threshold_policy_lower_bound_sum_indicator_prop (inst.dist b) t U).2.2
        have h_convex : min t (w + W) ≤ p * t + w + (1 - p) * U :=
          pandora_threshold_policy_lower_bound_convex_min_ineq p t w W hp_nonneg hw_nonneg
        have h_res : (∑ v ∈ (inst.dist b).support, (inst.dist b).prob v * max (v - r b) 0) = inst.cost b :=
          hr b
        have h_comb := pandora_threshold_policy_lower_bound_sum_pointwise_comb (inst.dist b) (inst.cost b) (r b) t U htr h_res
        change (∑ v ∈ (inst.dist b).support, (inst.dist b).prob v * (if t < v then v else U)) - inst.cost b =
          p * t + w + (1 - p) * U at h_comb
        rw [← h_comb] at h_convex
  11. Auxiliary induction step: pointwise bound on continuation utility

    For v > t the policy stops and achieves at least v, while for v ≤ t the new history max remains ≤ t so the induction hypothesis applies.

    lines 198–212

    uses pandora_threshold_policy_lower_bound_history_max_cons, le_max_right, max_le

        have h_pointwise : ∀ v ∈ (inst.dist b).support,
            (if t < v then v else U) ≤
              expectedUtilityDUS.aux inst ((b, v) :: history)
                (if t < v then AdaptivePolicy.stop else pandora_threshold_policy rest t) := by
          intro v _
          split_ifs with htv
          · have haux : expectedUtilityDUS.aux inst ((b, v) :: history) AdaptivePolicy.stop =
                pandora_threshold_policy_lower_bound_history_max ((b, v) :: history) := rfl
            rw [haux, pandora_threshold_policy_lower_bound_history_max_cons]
            exact le_max_right (pandora_threshold_policy_lower_bound_history_max history) v
          · have hle : v ≤ t := not_lt.mp htv
            have hH_new : pandora_threshold_policy_lower_bound_history_max ((b, v) :: history) ≤ t := by
              rw [pandora_threshold_policy_lower_bound_history_max_cons]
              exact max_le hH hle
            exact ih hnd_rest hpos_rest ((b, v) :: history) hH_new
  12. Auxiliary induction step: expected utility lower bound

    Summing the pointwise bounds over the distribution and subtracting the cost yields the induction step.

    lines 213–230

    uses Finset.sum_le_sum, mul_le_mul_of_nonneg_left

        have h_sum_le :
            (∑ v ∈ (inst.dist b).support, (inst.dist b).prob v * (if t < v then v else U)) ≤
            (∑ v ∈ (inst.dist b).support, (inst.dist b).prob v *
              expectedUtilityDUS.aux inst ((b, v) :: history)
                (if t < v then AdaptivePolicy.stop else pandora_threshold_policy rest t)) := by
          apply Finset.sum_le_sum
          intro v hv
          exact mul_le_mul_of_nonneg_left (h_pointwise v hv) ((inst.dist b).prob_nonneg v hv)
        have h_pol : pandora_threshold_policy (b :: rest) t =
            AdaptivePolicy.openBox b (fun v => if t < v then AdaptivePolicy.stop else pandora_threshold_policy rest t) := rfl
        rw [h_pol]
        have haux_open : expectedUtilityDUS.aux inst history
            (AdaptivePolicy.openBox b (fun v => if t < v then AdaptivePolicy.stop else pandora_threshold_policy rest t)) =
            (∑ v ∈ (inst.dist b).support, (inst.dist b).prob v *
              expectedUtilityDUS.aux inst ((b, v) :: history)
                (if t < v then AdaptivePolicy.stop else pandora_threshold_policy rest t)) - inst.cost b := rfl
        rw [haux_open]
        linarith
  13. Main theorem from auxiliary lemma

    Specializing the auxiliary induction to an empty history whose maximum is 0 ≤ t.

    lines 238–241

    uses pandora_threshold_policy_lower_bound_aux

      have hH : pandora_threshold_policy_lower_bound_history_max ([] : List (Fin inst.n × ℝ)) ≤ t := by
        change 0 ≤ t
        exact ht
      exact pandora_threshold_policy_lower_bound_aux inst r hr t ht order hnd hpos [] hH

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_threshold_policy_lower_bound_foldl_max {α : Type*} (history : List (α × ℝ)) (acc v : ℝ) :    history.foldl (fun a bv => max a bv.2) (max acc v) =      max (history.foldl (fun a bv => max a bv.2) acc) v := by  induction history generalizing acc with  | nil => rfl  | cons head tail ih =>    show List.foldl (fun a bv => max a bv.2) (max (max acc v) head.2) tail =      max (List.foldl (fun a bv => max a bv.2) (max acc head.2) tail) v    have : max (max acc v) head.2 = max (max acc head.2) v := by      rw [max_assoc, max_comm v, ← max_assoc]    rw [this, ih]def pandora_threshold_policy_lower_bound_history_max {n : ℕ} (history : List (Fin n × ℝ)) : ℝ :=  history.foldl (fun acc bv => max acc bv.2) 0lemma pandora_threshold_policy_lower_bound_history_max_cons {n : ℕ} (b : Fin n) (v : ℝ) (history : List (Fin n × ℝ)) :    pandora_threshold_policy_lower_bound_history_max ((b, v) :: history) =      max (pandora_threshold_policy_lower_bound_history_max history) v := by  show List.foldl (fun a bv => max a bv.2) (max 0 v) history = _  exact pandora_threshold_policy_lower_bound_foldl_max history 0 vlemma pandora_threshold_policy_lower_bound_foldl_max_nonneg {α : Type*} (history : List (α × ℝ)) (acc : ℝ) (hacc : 0 ≤ acc) :    0 ≤ history.foldl (fun a bv => max a bv.2) acc := by  induction history generalizing acc with  | nil => exact hacc  | cons head tail ih =>    apply ih    exact le_trans hacc (le_max_left acc head.2)lemma pandora_threshold_policy_lower_bound_history_max_nonneg {n : ℕ} (history : List (Fin n × ℝ)) :    0 ≤ pandora_threshold_policy_lower_bound_history_max history :=  pandora_threshold_policy_lower_bound_foldl_max_nonneg history 0 le_rfllemma pandora_threshold_policy_lower_bound_pointwise_comb (v r t U : ℝ) (htr : t ≤ r) :    (if t < v then v else U) - max (v - r) 0 =      (if t < v then t else 0) + max (min v r - t) 0 + (if t < v then 0 else U) := by  have hid : (if t < v then v else U) = (if t < v then v else 0) + (if t < v then 0 else U) := by    split_ifs <;> ring  rw [hid]  have h1 : (if t < v then v else 0) - max (v - r) 0 =      (if t < v then t else 0) + max (min v r - t) 0 := by    split_ifs with h    · rcases le_total v r with hvr | hrv      · have h2 : v - r ≤ 0 := by linarith        rw [max_eq_right h2, min_eq_left hvr]        have h3 : 0 ≤ v - t := by linarith        rw [max_eq_left h3]; ring      · have h2 : (0 : ℝ) ≤ v - r := by linarith        rw [max_eq_left h2, min_eq_right hrv]        have h3 : (0 : ℝ) ≤ r - t := by linarith        rw [max_eq_left h3]; ring    · have hle : v ≤ t := not_lt.mp h      have hvr : v ≤ r := hle.trans htr      have h2 : v - r ≤ 0 := by linarith      have h3 : min v r - t ≤ 0 := by linarith [min_le_left v r]      rw [max_eq_right h2, max_eq_right h3]; ring  linarithlemma pandora_threshold_policy_lower_bound_sum_indicator_prop (dist : DiscreteDist) (t U : ℝ) :    let p := ∑ v ∈ dist.support, dist.prob v * (if t < v then (1 : ℝ) else 0)    (∑ v ∈ dist.support, dist.prob v * (if t < v then t else 0)) = p * t ∧    (∑ v ∈ dist.support, dist.prob v * (if t < v then 0 else U)) = (1 - p) * U ∧    0 ≤ p := by  intro p  have hp_nonneg : 0 ≤ p := by    apply Finset.sum_nonneg    intro v hv    have : 0 ≤ (if t < v then (1 : ℝ) else 0) := by split_ifs <;> linarith    exact mul_nonneg (dist.prob_nonneg v hv) this  have h1 : (∑ v ∈ dist.support, dist.prob v * (if t < v then t else 0)) = p * t := by    dsimp [p]    have hid : ∀ v ∈ dist.support, dist.prob v * (if t < v then t else 0) =        (dist.prob v * (if t < v then 1 else 0)) * t := by      intro v _      split_ifs <;> ring    rw [Finset.sum_congr rfl hid, ← Finset.sum_mul]  have h2 : (∑ v ∈ dist.support, dist.prob v * (if t < v then 0 else U)) = (1 - p) * U := by    dsimp [p]    have hid : ∀ v ∈ dist.support, dist.prob v * (if t < v then 0 else U) =        (dist.prob v - dist.prob v * (if t < v then 1 else 0)) * U := by      intro v _      split_ifs <;> ring    rw [Finset.sum_congr rfl hid, ← Finset.sum_mul, Finset.sum_sub_distrib, dist.sum_prob_one]  exact ⟨h1, h2, hp_nonneg⟩lemma pandora_threshold_policy_lower_bound_sum_pointwise_comb (dist : DiscreteDist) (c r t U : ℝ) (htr : t ≤ r)    (hres : ∑ v ∈ dist.support, dist.prob v * max (v - r) 0 = c) :    let p := ∑ v ∈ dist.support, dist.prob v * (if t < v then (1 : ℝ) else 0)    (∑ v ∈ dist.support, dist.prob v * (if t < v then v else U)) - c =      p * t + (∑ v ∈ dist.support, dist.prob v * max (min v r - t) 0) + (1 - p) * U := by  intro p  have h_id : ∀ v ∈ dist.support,      dist.prob v * (if t < v then v else U) - dist.prob v * max (v - r) 0 =        dist.prob v * (if t < v then t else 0) +        dist.prob v * max (min v r - t) 0 +        dist.prob v * (if t < v then 0 else U) := by    intro v _    have h := pandora_threshold_policy_lower_bound_pointwise_comb v r t U htr    calc dist.prob v * (if t < v then v else U) - dist.prob v * max (v - r) 0      _ = dist.prob v * ((if t < v then v else U) - max (v - r) 0) := by ring      _ = dist.prob v * ((if t < v then t else 0) + max (min v r - t) 0 + (if t < v then 0 else U)) := by rw [h]      _ = dist.prob v * (if t < v then t else 0) +          dist.prob v * max (min v r - t) 0 +          dist.prob v * (if t < v then 0 else U) := by ring  have h_sub : (∑ v ∈ dist.support, dist.prob v * (if t < v then v else U)) - c =      ∑ v ∈ dist.support, (dist.prob v * (if t < v then v else U) - dist.prob v * max (v - r) 0) := by    rw [← hres, Finset.sum_sub_distrib]  rw [h_sub]  have h_sum_id : (∑ v ∈ dist.support, (dist.prob v * (if t < v then v else U) - dist.prob v * max (v - r) 0)) =      (∑ v ∈ dist.support, dist.prob v * (if t < v then t else 0)) +      (∑ v ∈ dist.support, dist.prob v * max (min v r - t) 0) +      (∑ v ∈ dist.support, dist.prob v * (if t < v then 0 else U)) := by    rw [Finset.sum_congr rfl h_id]    rw [Finset.sum_add_distrib, Finset.sum_add_distrib]  rw [h_sum_id]  have hp_eq : (∑ v ∈ dist.support, dist.prob v * (if t < v then t else 0)) = p * t :=    (pandora_threshold_policy_lower_bound_sum_indicator_prop dist t U).1  have hp_eq2 : (∑ v ∈ dist.support, dist.prob v * (if t < v then 0 else U)) = (1 - p) * U :=    (pandora_threshold_policy_lower_bound_sum_indicator_prop dist t U).2.1  rw [hp_eq, hp_eq2]lemma pandora_threshold_policy_lower_bound_convex_min_ineq (p t w W : ℝ) (hp : 0 ≤ p) (hw : 0 ≤ w) :    min t (w + W) ≤ p * t + w + (1 - p) * min t W := by  rcases le_total t W with htW | hWt  · rw [min_eq_left htW]    have : min t (w + W) ≤ t := min_le_left t (w + W)    have : t ≤ p * t + w + (1 - p) * t := by      calc t = p * t + (1 - p) * t := by ring      _ ≤ p * t + (1 - p) * t + w := by linarith      _ = p * t + w + (1 - p) * t := by ring    linarith  · rw [min_eq_right hWt]    have : min t (w + W) ≤ w + W := min_le_right t (w + W)    have : w + W ≤ p * t + w + (1 - p) * W := by      have : p * W ≤ p * t := mul_le_mul_of_nonneg_left hWt hp      linarith    linarithlemma pandora_threshold_policy_lower_bound_le_r_of_capped_surplus_pos (inst : PandoraDeadlineInstance) (r : Fin inst.n → ℝ)    (i : Fin inst.n) (t : ℝ) (hpos : 0 < pandora_capped_surplus inst r i t) : t ≤ r i := by  by_contra! h  have hzero : pandora_capped_surplus inst r i t ≤ 0 := by    unfold pandora_capped_surplus    apply Finset.sum_nonpos    intro v hv    have h1 : min v (r i) - t ≤ 0 := by linarith [min_le_right v (r i)]    rw [max_eq_right h1]    simp  linarithlemma pandora_threshold_policy_lower_bound_aux (inst : PandoraDeadlineInstance)    (r : Fin inst.n → ℝ) (hr : pandora_is_reservation inst r) (t : ℝ) (_ht : 0 ≤ t)    (order : List (Fin inst.n)) (hnd : order.Nodup)    (hpos : ∀ i ∈ order, 0 < pandora_capped_surplus inst r i t)    (history : List (Fin inst.n × ℝ)) (hH : pandora_threshold_policy_lower_bound_history_max history ≤ t) :    min t (∑ i ∈ order.toFinset, pandora_capped_surplus inst r i t) ≤      expectedUtilityDUS.aux inst history (pandora_threshold_policy order t) := by  induction order generalizing history with  | nil =>    have hnil : pandora_threshold_policy ([] : List (Fin inst.n)) t = AdaptivePolicy.stop := rfl    rw [hnil]    have haux : expectedUtilityDUS.aux inst history AdaptivePolicy.stop =        pandora_threshold_policy_lower_bound_history_max history := rfl    rw [haux]    simp only [List.toFinset_nil, Finset.sum_empty]    have : min t 0 ≤ 0 := min_le_right t 0    have : 0 ≤ pandora_threshold_policy_lower_bound_history_max history :=      pandora_threshold_policy_lower_bound_history_max_nonneg history    linarith  | cons b rest ih =>    have hb_notin : b ∉ rest := (List.nodup_cons.mp hnd).1    have hnd_rest : rest.Nodup := (List.nodup_cons.mp hnd).2    have hpos_b : 0 < pandora_capped_surplus inst r b t := hpos b (List.Mem.head rest)    have hpos_rest : ∀ i ∈ rest, 0 < pandora_capped_surplus inst r i t :=      fun i hi => hpos i (List.Mem.tail b hi)    have htr : t ≤ r b := pandora_threshold_policy_lower_bound_le_r_of_capped_surplus_pos inst r b t hpos_b    have hw_nonneg : 0 ≤ pandora_capped_surplus inst r b t := le_of_lt hpos_b    have hnotin_toFinset : b ∉ rest.toFinset := by      rw [List.mem_toFinset]      exact hb_notin    have h_sum : (∑ i ∈ (b :: rest).toFinset, pandora_capped_surplus inst r i t) =        pandora_capped_surplus inst r b t + ∑ i ∈ rest.toFinset, pandora_capped_surplus inst r i t := by      rw [List.toFinset_cons, Finset.sum_insert hnotin_toFinset]    rw [h_sum]    set w := pandora_capped_surplus inst r b t    set W := ∑ i ∈ rest.toFinset, pandora_capped_surplus inst r i t    set U := min t W    set p := ∑ v ∈ (inst.dist b).support, (inst.dist b).prob v * (if t < v then (1 : ℝ) else 0)    have hp_nonneg : 0 ≤ p := (pandora_threshold_policy_lower_bound_sum_indicator_prop (inst.dist b) t U).2.2    have h_convex : min t (w + W) ≤ p * t + w + (1 - p) * U :=      pandora_threshold_policy_lower_bound_convex_min_ineq p t w W hp_nonneg hw_nonneg    have h_res : (∑ v ∈ (inst.dist b).support, (inst.dist b).prob v * max (v - r b) 0) = inst.cost b :=      hr b    have h_comb := pandora_threshold_policy_lower_bound_sum_pointwise_comb (inst.dist b) (inst.cost b) (r b) t U htr h_res    change (∑ v ∈ (inst.dist b).support, (inst.dist b).prob v * (if t < v then v else U)) - inst.cost b =      p * t + w + (1 - p) * U at h_comb    rw [← h_comb] at h_convex    have h_pointwise : ∀ v ∈ (inst.dist b).support,        (if t < v then v else U) ≤          expectedUtilityDUS.aux inst ((b, v) :: history)            (if t < v then AdaptivePolicy.stop else pandora_threshold_policy rest t) := by      intro v _      split_ifs with htv      · have haux : expectedUtilityDUS.aux inst ((b, v) :: history) AdaptivePolicy.stop =            pandora_threshold_policy_lower_bound_history_max ((b, v) :: history) := rfl        rw [haux, pandora_threshold_policy_lower_bound_history_max_cons]        exact le_max_right (pandora_threshold_policy_lower_bound_history_max history) v      · have hle : v ≤ t := not_lt.mp htv        have hH_new : pandora_threshold_policy_lower_bound_history_max ((b, v) :: history) ≤ t := by          rw [pandora_threshold_policy_lower_bound_history_max_cons]          exact max_le hH hle        exact ih hnd_rest hpos_rest ((b, v) :: history) hH_new    have h_sum_le :        (∑ v ∈ (inst.dist b).support, (inst.dist b).prob v * (if t < v then v else U)) ≤        (∑ v ∈ (inst.dist b).support, (inst.dist b).prob v *          expectedUtilityDUS.aux inst ((b, v) :: history)            (if t < v then AdaptivePolicy.stop else pandora_threshold_policy rest t)) := by      apply Finset.sum_le_sum      intro v hv      exact mul_le_mul_of_nonneg_left (h_pointwise v hv) ((inst.dist b).prob_nonneg v hv)    have h_pol : pandora_threshold_policy (b :: rest) t =        AdaptivePolicy.openBox b (fun v => if t < v then AdaptivePolicy.stop else pandora_threshold_policy rest t) := rfl    rw [h_pol]    have haux_open : expectedUtilityDUS.aux inst history        (AdaptivePolicy.openBox b (fun v => if t < v then AdaptivePolicy.stop else pandora_threshold_policy rest t)) =        (∑ v ∈ (inst.dist b).support, (inst.dist b).prob v *          expectedUtilityDUS.aux inst ((b, v) :: history)            (if t < v then AdaptivePolicy.stop else pandora_threshold_policy rest t)) - inst.cost b := rfl    rw [haux_open]    linariththeorem pandora_threshold_policy_lower_bound (inst : PandoraDeadlineInstance)    (r : Fin inst.n → ℝ) (hr : pandora_is_reservation inst r) (t : ℝ) (ht : 0 ≤ t)    (order : List (Fin inst.n)) (hnd : order.Nodup)    (hpos : ∀ i ∈ order, 0 < pandora_capped_surplus inst r i t) :    min t (∑ i ∈ order.toFinset, pandora_capped_surplus inst r i t) ≤      expectedUtilityDUS inst (pandora_threshold_policy order t) := by  have hH : pandora_threshold_policy_lower_bound_history_max ([] : List (Fin inst.n × ℝ)) ≤ t := by    change 0 ≤ t    exact ht  exact pandora_threshold_policy_lower_bound_aux inst r hr t ht order hnd hpos [] hH
See it in the graphDiscuss this resultChallenge it