omsr_single_arrival_optimal_probeSeq_exists
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.
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.
uses
omsr_single_arrival_optimal_probeSeq_exists_bestVal,dif_pos,le_max_left,dif_neginduction 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]
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.
uses
omsr_single_arrival_optimal_probeSeq_exists_bestVal,dif_pos,le_trans,Finset.le_sup',le_max_rightrw [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 _ _)
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.
uses
probeValueinduction L with | nil => rfl | cons i L ih => simp only [probeValue] rw [ih]
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 [].
uses
List.nodup_nil,omsr_single_arrival_optimal_probeSeq_exists_bestVal,dif_pos,max_eq_leftinduction 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
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.
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]
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 [].
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
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.
uses
optDP,max_eq_left,Real.iSup_le,le_reflintro 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])
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.
uses
optDP,omsr_single_arrival_optimal_probeSeq_exists_bestVal_nonneg,max_le,Real.iSup_leintro 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 _ _)
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.
uses
Finset.mem_sdiff,Subsingleton.elim,if_pos,optDP,omsr_single_arrival_optimal_probeSeq_exists_optDP_all_matched,omsr_single_arrival_optimal_probeSeq_exists_bestValobtain ⟨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)
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|).
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_zerohave 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
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.
uses
omsr_single_arrival_optimal_probeSeq_exists_bestVal_attainedobtain ⟨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]
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.
uses
offlineOptValue,optDP,Subsingleton.elimhave 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]
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].
uses
omsr_single_arrival_optimal_probeSeq_exists_optDP_single_le,Finset.sdiff_empty,Finset.card_empty,Nat.sub_zerohave 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.
- The fuel parameter in optDP provides a well-founded recursion budget for the offline dynamic program; the proof inducts on this fuel rather than directly on arrival states.
- Because the problem involves a single arrival (Fin 1), Subsingleton.elim is used to show that once the single arrival is matched, all arrivals are matched, reducing the offline continuation value to 0.
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.
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