AFTD Auto-Formalizing Theoretical Domains

omsr_single_arrival_optimal_probeSeq_exists

theoremverified

For any resource weights w ≥ 0 and single arrival arr, there exists a valid probe sequence L from the full resource set univ whose probe value achieves at least offlineOptValue w [arr].

Statement

theorem omsr_single_arrival_optimal_probeSeq_exists (n : ℕ) (w : Fin n → ℝ) (hw : ∀ i, 0 ≤ w i) (arr : OMSRArrival n) :
    ∃ L : List (Fin n), IsValidProbeSeq arr Finset.univ L ∧ offlineOptValue w [arr] ≤ probeValue arr w (fun _ => 0) Finset.univ L
Source
step towards omsr_patience_single_arrival_optimal
Verified
08 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 6
  • OMSRArrivalAn arrival in online bipartite matching with stochastic rewards and patience facing n offline resources, consisting of a patience budget…
  • OfflineArrivalThe state of an arrival in the offline benchmark, tracking its arrival data, the set of resources already probed for it, and whether it…
  • probeValueGiven arrival arr with success probabilities arr.prob, resource weights w, continuation value function V on subsets of resources, and…
  • optDPFor resource weights w : Fin n → ℝ, fuel : ℕ, available resources S : Finset (Fin n), and arrival states arrs : Fin m → OfflineArrival n,…
  • offlineOptValueThe expected reward of the adaptive offline benchmark OPT on a list of arrivals arrs with resource weights w, defined by running optDP…
  • IsValidProbeSeqA list of offline resources is a valid probe sequence for an arrival from available resources if it has no duplicates, all its resources…

The proof, explained

The theorem proves that for any single arrival in the online matching with stochastic rewards model, there exists a valid probe sequence whose expected reward is at least the offline optimal value. It introduces an auxiliary dynamic program, bestVal, for probing a single arrival with a given patience budget, and proves by induction that its optimal value is attained by an explicit duplicate-free probe sequence. It then shows by induction on the fuel budget that the offline dynamic program optDP for a single arrival is upper-bounded by bestVal. Evaluating at the full resource set with zero previously probed items connects the offline optimum to the probe sequence value.

  1. The dynamic programming value bestVal is non-negative for all resource sets A and budgets k.

    We induct on the probe budget k. For k = 0, bestVal is 0 by definition. For k + 1, if A is nonempty, bestVal is defined as max 0 (sup' ...), which is at least 0 by le_max_left; if A is empty, it is 0.

    lines 13–19

    uses omsr_single_arrival_optimal_probeSeq_exists_bestVal, dif_pos, le_max_left, dif_neg

      induction k generalizing A with
      | zero => simp [omsr_single_arrival_optimal_probeSeq_exists_bestVal]
      | succ k ih =>
        by_cases h : A.Nonempty
        · rw [omsr_single_arrival_optimal_probeSeq_exists_bestVal, dif_pos h]
          exact le_max_left _ _
        · rw [omsr_single_arrival_optimal_probeSeq_exists_bestVal, dif_neg h]
  2. Probing an available resource i ∈ A first and continuing optimally with budget k yields at most bestVal with budget k + 1.

    When A is nonempty, bestVal arr w A (k + 1) is max 0 (sup' ...). The expected reward from probing i first is one of the terms in the supremum over A, so it is at most the supremum by Finset.le_sup', which is in turn at most the maximum with 0 by le_max_right.

    lines 26–28

    uses omsr_single_arrival_optimal_probeSeq_exists_bestVal, dif_pos, le_trans, Finset.le_sup', le_max_right

      rw [omsr_single_arrival_optimal_probeSeq_exists_bestVal, dif_pos h]
      exact le_trans (Finset.le_sup' (fun i => arr.prob i * w i + (1 - arr.prob i) *
          omsr_single_arrival_optimal_probeSeq_exists_bestVal arr w (A.erase i) k) hi) (le_max_right _ _)
  3. When the terminal value function is identically zero, the probe value of a sequence L is independent of the available resource set.

    We induct on the probe sequence L. For the empty list, the probe value is identically 0 regardless of the resource set. For a cons cell i :: L, unfolding probeValue shows that the terminal reward term V(S \ {i}) vanishes, and by induction the continuation value on L is independent of the set.

    lines 33–37

    uses probeValue

      induction L with
      | nil => rfl
      | cons i L ih =>
        simp only [probeValue]
        rw [ih]
  4. When the budget is 0, or when the supremum of expected probe rewards over A is non-positive, the optimal value is 0 and is achieved by the empty probe sequence.

    We prove attainment of bestVal by induction on k. For k = 0, the empty list has length 0 and probe value 0 = bestVal arr w A 0. For k + 1 with A nonempty, bestVal is max 0 (sup' ...). If this supremum is ≤ 0, then max 0 (sup' ...) = 0 by max_eq_left, which is again attained by the empty list [].

    lines 43–55

    uses List.nodup_nil, omsr_single_arrival_optimal_probeSeq_exists_bestVal, dif_pos, max_eq_left

      induction k generalizing A with
      | zero => exact ⟨[], List.nodup_nil, by simp, by simp, rfl⟩
      | succ k ih =>
        by_cases hA : A.Nonempty
        · have hbest : omsr_single_arrival_optimal_probeSeq_exists_bestVal arr w A (k + 1)
              = max 0 (A.sup' hA (fun i => arr.prob i * w i + (1 - arr.prob i) *
                  omsr_single_arrival_optimal_probeSeq_exists_bestVal arr w (A.erase i) k)) := by
            simp only [omsr_single_arrival_optimal_probeSeq_exists_bestVal, dif_pos hA]
          by_cases hX : A.sup' hA (fun i => arr.prob i * w i + (1 - arr.prob i) *
              omsr_single_arrival_optimal_probeSeq_exists_bestVal arr w (A.erase i) k) ≤ 0
          · refine ⟨[], List.nodup_nil, by simp, by simp, ?_⟩
            rw [hbest, max_eq_left hX]
            rfl
  5. When the supremum over A is strictly positive, selecting an optimal first resource i and prepending it to the optimal sequence for A \ {i} achieves bestVal with budget k + 1.

    Since A is finite and nonempty, the supremum is attained at some resource i ∈ A by Finset.exists_mem_eq_sup'. By the induction hypothesis on A \ {i} and budget k, there exists a duplicate-free sequence L ⊆ A \ {i} of length at most k achieving bestVal arr w (A \ {i}) k. Prepending i yields i :: L, which has no duplicates, consists of elements in A, has length at most k + 1, and matches bestVal arr w A (k + 1) because the terminal value is 0.

    lines 56–74

    uses not_le.mp, Finset.exists_mem_eq_sup', omsr_single_arrival_optimal_probeSeq_exists_bestVal, List.nodup_cons, Finset.notMem_erase, List.mem_cons, Finset.mem_of_mem_erase, List.length_cons, max_eq_right, le_of_lt, probeValue, add_zero, omsr_single_arrival_optimal_probeSeq_exists_probeValue_zero_indep

          · have hXpos : 0 < A.sup' hA (fun i => arr.prob i * w i + (1 - arr.prob i) *
                omsr_single_arrival_optimal_probeSeq_exists_bestVal arr w (A.erase i) k) := not_le.mp hX
            obtain ⟨i, hi, hsup⟩ := Finset.exists_mem_eq_sup' hA (fun i => arr.prob i * w i +
              (1 - arr.prob i) * omsr_single_arrival_optimal_probeSeq_exists_bestVal arr w (A.erase i) k)
            obtain ⟨L, hLnd, hLsub, hLlen, hLval⟩ := ih (A.erase i)
            refine ⟨i :: L, ?_, ?_, ?_, ?_⟩
            · rw [List.nodup_cons]
              exact ⟨fun hiL => Finset.notMem_erase i A (hLsub i hiL), hLnd⟩
            · intro j hj
              rw [List.mem_cons] at hj
              rcases hj with rfl | hj
              · exact hi
              · exact Finset.mem_of_mem_erase (hLsub j hj)
            · rw [List.length_cons]
              omega
            · rw [hbest, max_eq_right (le_of_lt hXpos)]
              simp only [probeValue, add_zero]
              rw [omsr_single_arrival_optimal_probeSeq_exists_probeValue_zero_indep arr w A (A.erase i) L,
                hLval, hsup]
  6. When A is empty, bestVal with budget k + 1 is 0, which is attained by the empty sequence.

    If A is empty, bestVal evaluates to 0 by definition (via dif_neg), which is attained by [].

    lines 75–77

    uses List.nodup_nil, omsr_single_arrival_optimal_probeSeq_exists_bestVal, dif_neg

        · refine ⟨[], List.nodup_nil, by simp, by simp, ?_⟩
          simp only [omsr_single_arrival_optimal_probeSeq_exists_bestVal, dif_neg hA]
          rfl
  7. If all arrivals are already matched, the offline dynamic program optDP evaluates to 0.

    We induct on fuel. The base case fuel = 0 is 0 by definition. For fuel + 1, optDP is the maximum of 0 and a supremum over transitions. Every transition requires the arrival to be unmatched, which is false by hypothesis. Hence every term in the supremum is bounded by 0 via Real.iSup_le, and the maximum is 0.

    lines 82–92

    uses optDP, max_eq_left, Real.iSup_le, le_refl

      intro fuel
      induction fuel with
      | zero => intro S; rfl
      | succ fuel ih =>
        intro S
        simp only [optDP]
        rw [max_eq_left]
        refine Real.iSup_le (fun t => ?_) (le_refl 0)
        refine Real.iSup_le (fun i => ?_) (le_refl 0)
        refine Real.iSup_le (fun hcond => ?_) (le_refl 0)
        exact absurd (hm t) (by simp [hcond.2.1])
  8. For a single arrival, optDP is bounded above by bestVal arr w (S \ P) (arr.patience - |P|), and the inductive step reduces to bounding each transition.

    We induct on fuel. For fuel = 0, optDP is 0, which is ≤ bestVal by its non-negativity. For fuel + 1, optDP is max 0 (sup' ...). Since bestVal is non-negative, max_le and Real.iSup_le reduce the goal to showing that each transition term is bounded by bestVal.

    lines 99–114

    uses optDP, omsr_single_arrival_optimal_probeSeq_exists_bestVal_nonneg, max_le, Real.iSup_le

      intro fuel
      induction fuel with
      | zero =>
        intro S P
        simp only [optDP]
        exact omsr_single_arrival_optimal_probeSeq_exists_bestVal_nonneg arr w _ _
      | succ fuel ih =>
        intro S P
        simp only [optDP]
        refine max_le (omsr_single_arrival_optimal_probeSeq_exists_bestVal_nonneg arr w _ _) ?_
        refine Real.iSup_le (fun t => ?_)
          (omsr_single_arrival_optimal_probeSeq_exists_bestVal_nonneg arr w _ _)
        refine Real.iSup_le (fun i => ?_)
          (omsr_single_arrival_optimal_probeSeq_exists_bestVal_nonneg arr w _ _)
        refine Real.iSup_le (fun hcond => ?_)
          (omsr_single_arrival_optimal_probeSeq_exists_bestVal_nonneg arr w _ _)
  9. For any valid transition probing resource i ∈ S \ P, the success continuation value vanishes, while the failure continuation value is bounded by the induction hypothesis on fuel.

    The transition condition ensures i ∈ S \ P. If probing i succeeds, the arrival becomes matched. Since there is only one arrival in Fin 1, all arrivals are matched, so the continuation value is 0 by omsr_single_arrival_optimal_probeSeq_exists_optDP_all_matched. If probing i fails, i is added to the probed set, and the continuation value is bounded by the induction hypothesis on fuel.

    lines 115–138

    uses Finset.mem_sdiff, Subsingleton.elim, if_pos, optDP, omsr_single_arrival_optimal_probeSeq_exists_optDP_all_matched, omsr_single_arrival_optimal_probeSeq_exists_bestVal

        obtain ⟨hS, -, hP, hlt⟩ := hcond
        have hmemA : i ∈ S \ P := Finset.mem_sdiff.mpr ⟨hS, hP⟩
        have hA : (S \ P).Nonempty := ⟨i, hmemA⟩
        have hsucc_fun : (fun j : Fin 1 => if j = t then ({ arrival := arr, probed := P, matched := true } : OfflineArrival n)
            else { arrival := arr, probed := P, matched := false }) =
            fun _ => ({ arrival := arr, probed := P, matched := true } : OfflineArrival n) := by
          ext j; rw [Subsingleton.elim j t, if_pos rfl]
        have hsucc : optDP w fuel (S.erase i)
            (fun j => if j = t then ({ arrival := arr, probed := P, matched := true } : OfflineArrival n)
            else { arrival := arr, probed := P, matched := false }) = 0 := by
          rw [hsucc_fun]
          apply omsr_single_arrival_optimal_probeSeq_exists_optDP_all_matched
          intro j
          rfl
        have hfail_fun : (fun j : Fin 1 => if j = t then ({ arrival := arr, probed := insert i P, matched := false } : OfflineArrival n)
            else { arrival := arr, probed := P, matched := false }) =
            fun _ => ({ arrival := arr, probed := insert i P, matched := false } : OfflineArrival n) := by
          ext j; rw [Subsingleton.elim j t, if_pos rfl]
        have hfail : optDP w fuel S
            (fun j => if j = t then ({ arrival := arr, probed := insert i P, matched := false } : OfflineArrival n)
            else { arrival := arr, probed := P, matched := false })
            ≤ omsr_single_arrival_optimal_probeSeq_exists_bestVal arr w (S \ insert i P) (arr.patience - (insert i P).card) := by
          rw [hfail_fun]
          exact ih S (insert i P)
  10. The expected reward of probing i is bounded by bestVal arr w (S \ P) (arr.patience - |P|), completing the induction on fuel.

    Since i ∉ P, |P ∪ {i}| = |P| + 1 and S \ (P ∪ {i}) = (S \ P) \ {i}. The expected reward is arr.prob i * w i + (1 - arr.prob i) * (failure value). Multiplying the failure bound by 1 - arr.prob i ≥ 0 and applying omsr_single_arrival_optimal_probeSeq_exists_bestVal_step_le shows the expectation is at most bestVal arr w (S \ P) (arr.patience - |P|).

    lines 139–152

    uses Finset.card_insert_of_notMem, Finset.mem_sdiff, Finset.mem_insert, Finset.mem_erase, omsr_single_arrival_optimal_probeSeq_exists_bestVal_step_le, mul_le_mul_of_nonneg_left, add_zero

        have hcard : (insert i P).card = P.card + 1 := Finset.card_insert_of_notMem hP
        have hsdiff : S \ insert i P = (S \ P).erase i := by
          ext x
          simp only [Finset.mem_sdiff, Finset.mem_insert, not_or, Finset.mem_erase]
          tauto
        rw [hsucc]
        rw [hsdiff, hcard] at hfail
        have hbounded := omsr_single_arrival_optimal_probeSeq_exists_bestVal_step_le arr w hA hmemA (arr.patience - (P.card + 1))
        have hp1 : (0:ℝ) ≤ 1 - arr.prob i := by linarith [arr.prob_le_one i]
        have hmul := mul_le_mul_of_nonneg_left hfail hp1
        rw [add_zero]
        have heq : arr.patience - (P.card + 1) + 1 = arr.patience - P.card := by omega
        rw [heq] at hbounded
        linarith
  11. There exists a valid probe sequence L from univ of length at most arr.patience that attains bestVal arr w univ arr.patience.

    We apply omsr_single_arrival_optimal_probeSeq_exists_bestVal_attained with A = univ and k = arr.patience to obtain a duplicate-free list L ⊆ univ of length at most arr.patience whose probe value equals bestVal arr w univ arr.patience.

    lines 156–158

    uses omsr_single_arrival_optimal_probeSeq_exists_bestVal_attained

      obtain ⟨L, hnd, hsub, hlen, hval⟩ := omsr_single_arrival_optimal_probeSeq_exists_bestVal_attained arr w Finset.univ arr.patience
      refine ⟨L, ⟨hnd, hsub, hlen⟩, ?_⟩
      rw [hval]
  12. The offline optimal value for [arr] equals optDP with 1 * n fuel on the single arrival with empty probed set and matched = false.

    By definition, offlineOptValue w [arr] is optDP with fuel 1 * n and arrival list [arr]. Since the arrival list has length 1, Fin 1 has a unique element, so the arrival configuration function matches the single arrival state.

    lines 159–166

    uses offlineOptValue, optDP, Subsingleton.elim

      have hopt : offlineOptValue w [arr] = optDP (m := 1) w (1 * n) Finset.univ (fun _ => ⟨arr, ∅, false⟩) := by
        dsimp [offlineOptValue]
        congr 1
        ext idx
        have : idx = 0 := Subsingleton.elim idx 0
        subst this
        rfl
      rw [hopt]
  13. offlineOptValue w [arr] is bounded above by the probe value of L, establishing the theorem.

    Applying omsr_single_arrival_optimal_probeSeq_exists_optDP_single_le with fuel = 1 * n, S = univ, and P = ∅ gives offlineOptValue w [arr] ≤ bestVal arr w univ arr.patience. Since L achieves this value, the probe value of L is at least offlineOptValue w [arr].

    lines 167–169

    uses omsr_single_arrival_optimal_probeSeq_exists_optDP_single_le, Finset.sdiff_empty, Finset.card_empty, Nat.sub_zero

      have hle := omsr_single_arrival_optimal_probeSeq_exists_optDP_single_le arr w (1 * n) Finset.univ ∅
      simp only [Finset.sdiff_empty, Finset.card_empty, Nat.sub_zero] at hle
      exact hle
omsr_single_arrival_optimal_probeSeq_exists_bestVal
The dynamic programming function defining the maximum expected reward achievable for a single arrival using resources from a set A with a probe budget of k.
omsr_single_arrival_optimal_probeSeq_exists_bestVal_nonneg
The single-arrival optimal dynamic programming value bestVal is always non-negative.
omsr_single_arrival_optimal_probeSeq_exists_bestVal_step_le
The expected value of probing an available resource i first and continuing optimally with budget k is bounded above by bestVal with budget k + 1.
omsr_single_arrival_optimal_probeSeq_exists_probeValue_zero_indep
When the terminal continuation value function is identically zero, the probe value of a list is independent of the available resource set S.
omsr_single_arrival_optimal_probeSeq_exists_bestVal_attained
The value bestVal arr w A k is attained by some valid duplicate-free probe sequence of length at most k consisting of elements from A.
omsr_single_arrival_optimal_probeSeq_exists_optDP_all_matched
If all arrivals are already matched, the offline dynamic program value optDP is 0.
omsr_single_arrival_optimal_probeSeq_exists_optDP_single_le
For a single arrival, the offline value optDP is bounded above by bestVal on the unprobed resources with the remaining patience budget.
dif_pos
If a condition c holds, then the dependent if-then-else `if h : c then t else e` reduces to `t h`.
dif_neg
If a condition c is false (¬c), then `if h : c then t else e` reduces to `e h`.
le_max_left
For any elements a and b in a linear order, a ≤ max a b.
le_max_right
For any elements a and b in a linear order, b ≤ max a b.
le_trans
Transitivity of order: if a ≤ b and b ≤ c, then a ≤ c.
Finset.le_sup'
For any element b in a nonempty finite set s, f b ≤ s.sup' h f.
probeValue
The expected total reward obtained by probing a list of resources L in order, given arrival probabilities, weights, continuation value function V, and available resource set S.
List.nodup_nil
The empty list has no duplicate elements.
max_eq_left
If b ≤ a, then max a b = a.
not_le.mp
If ¬(a ≤ b), then b < a in a linear order.
Finset.exists_mem_eq_sup'
On a nonempty finite set, the supremum of a function is attained at some element of the set.
List.nodup_cons
The list a :: l has no duplicates if and only if a ∉ l and l has no duplicates.
Finset.notMem_erase
An element a is not in s.erase a.
List.mem_cons
An element belongs to a :: l if and only if it equals a or belongs to l.
Finset.mem_of_mem_erase
If an element belongs to s.erase a, it belongs to s.
List.length_cons
The length of a :: as is length as + 1.
max_eq_right
If a ≤ b, then max a b = b.
le_of_lt
If a < b, then a ≤ b.
add_zero
Adding zero to any element leaves it unchanged: a + 0 = a.
optDP
The offline dynamic program computing the optimal expected reward from a given resource set and arrival states with a given fuel limit.
Real.iSup_le
The supremum of a family of real numbers is bounded above by a non-negative constant a if every element in the family is bounded by a.
le_refl
Reflexivity of order: a ≤ a.
max_le
If a ≤ c and b ≤ c, then max a b ≤ c.
Finset.mem_sdiff
An element belongs to s \ t if and only if it belongs to s and does not belong to t.
Subsingleton.elim
Any two elements of a subsingleton type are equal.
if_pos
If condition c is true, then (if c then t else e) = t.
Finset.card_insert_of_notMem
If a ∉ s, the cardinality of insert a s is s.card + 1.
Finset.mem_insert
An element belongs to insert a s if and only if it equals a or belongs to s.
Finset.mem_erase
An element belongs to s.erase a if and only if it is not equal to a and belongs to s.
mul_le_mul_of_nonneg_left
Multiplying an inequality b ≤ c by a non-negative scalar a preserves the inequality: a * b ≤ a * c.
offlineOptValue
The definition of the offline optimal value for a list of arrivals, computed via optDP with initial resources univ and fuel m * n.
Finset.sdiff_empty
Subtracting the empty set from a set leaves it unchanged: s \ ∅ = s.
Finset.card_empty
The cardinality of the empty set is 0.
Nat.sub_zero
Subtracting zero from a natural number leaves it unchanged: a - 0 = a.

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

noncomputable def omsr_single_arrival_optimal_probeSeq_exists_bestVal {n : ℕ} (arr : OMSRArrival n)    (w : Fin n → ℝ) : Finset (Fin n) → ℕ → ℝ  | _, 0 => 0  | A, k + 1 =>      if h : A.Nonempty then        max 0 (A.sup' h (fun i => arr.prob i * w i + (1 - arr.prob i) *          omsr_single_arrival_optimal_probeSeq_exists_bestVal arr w (A.erase i) k))      else 0theorem omsr_single_arrival_optimal_probeSeq_exists_bestVal_nonneg {n : ℕ} (arr : OMSRArrival n)    (w : Fin n → ℝ) (A : Finset (Fin n)) (k : ℕ) :    0 ≤ omsr_single_arrival_optimal_probeSeq_exists_bestVal arr w A k := by  induction k generalizing A with  | zero => simp [omsr_single_arrival_optimal_probeSeq_exists_bestVal]  | succ k ih =>    by_cases h : A.Nonempty    · rw [omsr_single_arrival_optimal_probeSeq_exists_bestVal, dif_pos h]      exact le_max_left _ _    · rw [omsr_single_arrival_optimal_probeSeq_exists_bestVal, dif_neg h]theorem omsr_single_arrival_optimal_probeSeq_exists_bestVal_step_le {n : ℕ} (arr : OMSRArrival n)    (w : Fin n → ℝ) {A : Finset (Fin n)} (h : A.Nonempty) {i : Fin n} (hi : i ∈ A) (k : ℕ) :    arr.prob i * w i + (1 - arr.prob i) *      omsr_single_arrival_optimal_probeSeq_exists_bestVal arr w (A.erase i) k      ≤ omsr_single_arrival_optimal_probeSeq_exists_bestVal arr w A (k + 1) := by  rw [omsr_single_arrival_optimal_probeSeq_exists_bestVal, dif_pos h]  exact le_trans (Finset.le_sup' (fun i => arr.prob i * w i + (1 - arr.prob i) *      omsr_single_arrival_optimal_probeSeq_exists_bestVal arr w (A.erase i) k) hi) (le_max_right _ _)theorem omsr_single_arrival_optimal_probeSeq_exists_probeValue_zero_indep {n : ℕ} (arr : OMSRArrival n)    (w : Fin n → ℝ) (S S' : Finset (Fin n)) (L : List (Fin n)) :    probeValue arr w (fun _ => (0:ℝ)) S L = probeValue arr w (fun _ => (0:ℝ)) S' L := by  induction L with  | nil => rfl  | cons i L ih =>    simp only [probeValue]    rw [ih]theorem omsr_single_arrival_optimal_probeSeq_exists_bestVal_attained {n : ℕ} (arr : OMSRArrival n)    (w : Fin n → ℝ) (A : Finset (Fin n)) (k : ℕ) :    ∃ L : List (Fin n), L.Nodup ∧ (∀ i ∈ L, i ∈ A) ∧ L.length ≤ k ∧      probeValue arr w (fun _ => 0) A L = omsr_single_arrival_optimal_probeSeq_exists_bestVal arr w A k := by  induction k generalizing A with  | zero => exact ⟨[], List.nodup_nil, by simp, by simp, rfl⟩  | succ k ih =>    by_cases hA : A.Nonempty    · have hbest : omsr_single_arrival_optimal_probeSeq_exists_bestVal arr w A (k + 1)          = max 0 (A.sup' hA (fun i => arr.prob i * w i + (1 - arr.prob i) *              omsr_single_arrival_optimal_probeSeq_exists_bestVal arr w (A.erase i) k)) := by        simp only [omsr_single_arrival_optimal_probeSeq_exists_bestVal, dif_pos hA]      by_cases hX : A.sup' hA (fun i => arr.prob i * w i + (1 - arr.prob i) *          omsr_single_arrival_optimal_probeSeq_exists_bestVal arr w (A.erase i) k) ≤ 0      · refine ⟨[], List.nodup_nil, by simp, by simp, ?_⟩        rw [hbest, max_eq_left hX]        rfl      · have hXpos : 0 < A.sup' hA (fun i => arr.prob i * w i + (1 - arr.prob i) *            omsr_single_arrival_optimal_probeSeq_exists_bestVal arr w (A.erase i) k) := not_le.mp hX        obtain ⟨i, hi, hsup⟩ := Finset.exists_mem_eq_sup' hA (fun i => arr.prob i * w i +          (1 - arr.prob i) * omsr_single_arrival_optimal_probeSeq_exists_bestVal arr w (A.erase i) k)        obtain ⟨L, hLnd, hLsub, hLlen, hLval⟩ := ih (A.erase i)        refine ⟨i :: L, ?_, ?_, ?_, ?_⟩        · rw [List.nodup_cons]          exact ⟨fun hiL => Finset.notMem_erase i A (hLsub i hiL), hLnd⟩        · intro j hj          rw [List.mem_cons] at hj          rcases hj with rfl | hj          · exact hi          · exact Finset.mem_of_mem_erase (hLsub j hj)        · rw [List.length_cons]          omega        · rw [hbest, max_eq_right (le_of_lt hXpos)]          simp only [probeValue, add_zero]          rw [omsr_single_arrival_optimal_probeSeq_exists_probeValue_zero_indep arr w A (A.erase i) L,            hLval, hsup]    · refine ⟨[], List.nodup_nil, by simp, by simp, ?_⟩      simp only [omsr_single_arrival_optimal_probeSeq_exists_bestVal, dif_neg hA]      rfltheorem omsr_single_arrival_optimal_probeSeq_exists_optDP_all_matched {n m : ℕ} (w : Fin n → ℝ)    (arrs : Fin m → OfflineArrival n) (hm : ∀ t, (arrs t).matched = true) :    ∀ (fuel : ℕ) (S : Finset (Fin n)), optDP w fuel S arrs = 0 := by  intro fuel  induction fuel with  | zero => intro S; rfl  | succ fuel ih =>    intro S    simp only [optDP]    rw [max_eq_left]    refine Real.iSup_le (fun t => ?_) (le_refl 0)    refine Real.iSup_le (fun i => ?_) (le_refl 0)    refine Real.iSup_le (fun hcond => ?_) (le_refl 0)    exact absurd (hm t) (by simp [hcond.2.1])theorem omsr_single_arrival_optimal_probeSeq_exists_optDP_single_le {n : ℕ} (arr : OMSRArrival n)    (w : Fin n → ℝ) :    ∀ (fuel : ℕ) (S P : Finset (Fin n)),      optDP (m := 1) w fuel S (fun _ => (⟨arr, P, false⟩ : OfflineArrival n))        ≤ omsr_single_arrival_optimal_probeSeq_exists_bestVal arr w (S \ P) (arr.patience - P.card) := by  intro fuel  induction fuel with  | zero =>    intro S P    simp only [optDP]    exact omsr_single_arrival_optimal_probeSeq_exists_bestVal_nonneg arr w _ _  | succ fuel ih =>    intro S P    simp only [optDP]    refine max_le (omsr_single_arrival_optimal_probeSeq_exists_bestVal_nonneg arr w _ _) ?_    refine Real.iSup_le (fun t => ?_)      (omsr_single_arrival_optimal_probeSeq_exists_bestVal_nonneg arr w _ _)    refine Real.iSup_le (fun i => ?_)      (omsr_single_arrival_optimal_probeSeq_exists_bestVal_nonneg arr w _ _)    refine Real.iSup_le (fun hcond => ?_)      (omsr_single_arrival_optimal_probeSeq_exists_bestVal_nonneg arr w _ _)    obtain ⟨hS, -, hP, hlt⟩ := hcond    have hmemA : i ∈ S \ P := Finset.mem_sdiff.mpr ⟨hS, hP⟩    have hA : (S \ P).Nonempty := ⟨i, hmemA⟩    have hsucc_fun : (fun j : Fin 1 => if j = t then ({ arrival := arr, probed := P, matched := true } : OfflineArrival n)        else { arrival := arr, probed := P, matched := false }) =        fun _ => ({ arrival := arr, probed := P, matched := true } : OfflineArrival n) := by      ext j; rw [Subsingleton.elim j t, if_pos rfl]    have hsucc : optDP w fuel (S.erase i)        (fun j => if j = t then ({ arrival := arr, probed := P, matched := true } : OfflineArrival n)        else { arrival := arr, probed := P, matched := false }) = 0 := by      rw [hsucc_fun]      apply omsr_single_arrival_optimal_probeSeq_exists_optDP_all_matched      intro j      rfl    have hfail_fun : (fun j : Fin 1 => if j = t then ({ arrival := arr, probed := insert i P, matched := false } : OfflineArrival n)        else { arrival := arr, probed := P, matched := false }) =        fun _ => ({ arrival := arr, probed := insert i P, matched := false } : OfflineArrival n) := by      ext j; rw [Subsingleton.elim j t, if_pos rfl]    have hfail : optDP w fuel S        (fun j => if j = t then ({ arrival := arr, probed := insert i P, matched := false } : OfflineArrival n)        else { arrival := arr, probed := P, matched := false })        ≤ omsr_single_arrival_optimal_probeSeq_exists_bestVal arr w (S \ insert i P) (arr.patience - (insert i P).card) := by      rw [hfail_fun]      exact ih S (insert i P)    have hcard : (insert i P).card = P.card + 1 := Finset.card_insert_of_notMem hP    have hsdiff : S \ insert i P = (S \ P).erase i := by      ext x      simp only [Finset.mem_sdiff, Finset.mem_insert, not_or, Finset.mem_erase]      tauto    rw [hsucc]    rw [hsdiff, hcard] at hfail    have hbounded := omsr_single_arrival_optimal_probeSeq_exists_bestVal_step_le arr w hA hmemA (arr.patience - (P.card + 1))    have hp1 : (0:ℝ) ≤ 1 - arr.prob i := by linarith [arr.prob_le_one i]    have hmul := mul_le_mul_of_nonneg_left hfail hp1    rw [add_zero]    have heq : arr.patience - (P.card + 1) + 1 = arr.patience - P.card := by omega    rw [heq] at hbounded    linariththeorem omsr_single_arrival_optimal_probeSeq_exists (n : ℕ) (w : Fin n → ℝ) (hw : ∀ i, 0 ≤ w i) (arr : OMSRArrival n) :    ∃ L : List (Fin n), IsValidProbeSeq arr Finset.univ L ∧ offlineOptValue w [arr] ≤ probeValue arr w (fun _ => 0) Finset.univ L := by  obtain ⟨L, hnd, hsub, hlen, hval⟩ := omsr_single_arrival_optimal_probeSeq_exists_bestVal_attained arr w Finset.univ arr.patience  refine ⟨L, ⟨hnd, hsub, hlen⟩, ?_⟩  rw [hval]  have hopt : offlineOptValue w [arr] = optDP (m := 1) w (1 * n) Finset.univ (fun _ => ⟨arr, ∅, false⟩) := by    dsimp [offlineOptValue]    congr 1    ext idx    have : idx = 0 := Subsingleton.elim idx 0    subst this    rfl  rw [hopt]  have hle := omsr_single_arrival_optimal_probeSeq_exists_optDP_single_le arr w (1 * n) Finset.univ ∅  simp only [Finset.sdiff_empty, Finset.card_empty, Nat.sub_zero] at hle  exact hle
See it in the graphDiscuss this resultChallenge it