omsr_patience_single_arrival_optimal
For all n and all non-negative weights w, there exists a randomized online policy R for n resources such that on every arrival list arrs with at most one arrival (arrs.length ≤ 1), offlineOptValue w arrs ≤ expectedOnlineValue w R arrs.
Statement
theorem omsr_patience_single_arrival_optimal :
∀ (n : ℕ) (w : Fin n → ℝ), (∀ i, 0 ≤ w i) →
∃ R : RandomizedOMSRPolicy n,
∀ arrs : List (OMSRArrival n), arrs.length ≤ 1 →
offlineOptValue w arrs ≤ expectedOnlineValue w R arrs- Formalizes
- scout/2611-03598-online-matching-with-arbitrary-stochastic-rewards.md:415
- Verified
- 05 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 9
- offlineOptValueThe expected reward of the adaptive offline benchmark OPT on a list of arrivals arrs with resource weights w, defined by running optDP…
- RandomizedOMSRPolicyFor n offline resources, a RandomizedOMSRPolicy packages a sample space Ω, a measurable space structure mΩ, a probability measure μ on Ω…
- expectedOnlineValueThe expected total reward of a randomized online policy R on a list of arrivals arrs with weights w, defined as the integral over Ω of…
- optDPFor resource weights w : Fin n → ℝ, fuel : ℕ, available resources S : Finset (Fin n), and arrival states arrs : Fin m → OfflineArrival n,…
- OfflineArrivalThe state of an arrival in the offline benchmark, tracking its arrival data, the set of resources already probed for it, and whether it…
- onlinePolicyValueThe expected total reward of a deterministic online policy π on an arrival list arrs starting from available resources S with resource…
- OMSRArrivalAn arrival in online bipartite matching with stochastic rewards and patience facing n offline resources, consisting of a patience budget…
- probeValueGiven arrival arr with success probabilities arr.prob, resource weights w, continuation value function V on subsets of resources, and…
- IsValidProbeSeqA list of offline resources is a valid probe sequence for an arrival from available resources if it has no duplicates, all its resources…
Read back from the Lean
For every natural number $n$ and every non-negative weight vector $w : \text{Fin } n \to \mathbb{R}$ (i.e., $w(i) \ge 0$ for all $i$), there exists a randomized OMSR policy $R$ such that for every list of arrivals $\text{arrs}$ with length at most 1, the offline optimal dynamic programming value offlineOptValue w arrs is less than or equal to the expected online policy value expectedOnlineValue w R arrs.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
The proof shows that online matching with stochastic rewards achieves competitive ratio 1 against the offline optimum on instances with at most one arrival. It solves the single-arrival problem by defining the optimal dynamic programming value V(A, k) over available resources A and remaining patience k, and proving that an optimal probing sequence attaining this value exists. The offline dynamic program optDP on a single arrival is shown by induction to be bounded above by V(S, patience). The deterministic online policy attaining V(univ, patience) is packaged as a Dirac randomized policy, matching the offline upper bound on every arrival sequence of length at most 1.
The optimal single-arrival value V(A, k) is non-negative for all resource sets A and patience budgets k.
We proceed by induction on the patience budget k. For k = 0, the value is 0 by definition. In the inductive step k + 1, if A is empty the value is 0, and if A is nonempty the value is defined as the maximum of 0 and the best choice, which is non-negative by le_max_left.
uses
le_max_leftprivate theorem omsr_patience_single_arrival_optimal_bestVal_nonneg {n : ℕ} (arr : OMSRArrival n) (w : Fin n → ℝ) (A : Finset (Fin n)) (k : ℕ) : 0 ≤ omsr_patience_single_arrival_optimal_bestVal arr w A k := by induction k generalizing A with | zero => simp [omsr_patience_single_arrival_optimal_bestVal] | succ k ih => by_cases h : A.Nonempty · rw [omsr_patience_single_arrival_optimal_bestVal, dif_pos h] exact le_max_left _ _ · rw [omsr_patience_single_arrival_optimal_bestVal, dif_neg h]
For any available resource i ∈ A, the expected value of probing i followed by the optimal continuation is bounded by V(A, k + 1).
Unfolding the definition of V(A, k + 1) for nonempty A, the value is the maximum of 0 and the supremum over choices in A. Since i ∈ A, the expected one-step return with resource i is bounded by the supremum over A via Finset.le_sup', and then by the outer maximum via le_max_right.
uses
Finset.le_sup',le_max_rightprivate theorem omsr_patience_single_arrival_optimal_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_patience_single_arrival_optimal_bestVal arr w (A.erase i) k ≤ omsr_patience_single_arrival_optimal_bestVal arr w A (k + 1) := by rw [omsr_patience_single_arrival_optimal_bestVal, dif_pos h] exact le_trans (Finset.le_sup' (fun i => arr.prob i * w i + (1 - arr.prob i) * omsr_patience_single_arrival_optimal_bestVal arr w (A.erase i) k) hi) (le_max_right _ _)
When terminal continuation values are zero, the expected probe value of a sequence L does not depend on the available resource set S.
We induct on the probe list L. For the empty list, the probe value is identically the terminal continuation value 0 regardless of S. In the inductive step i :: L, unfolding probeValue shows that the value is p_i * w_i + (1 - p_i) * probeValue(S, L), where by the induction hypothesis the recursive call on L is independent of S.
private theorem omsr_patience_single_arrival_optimal_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]
For k = 0, or when all one-step probe choices yield non-positive value, the optimal value is achieved by the empty probe list.
We induct on k to construct an optimal probe sequence. For k = 0, the empty list trivially has no duplicates, length 0 ≤ 0, and value 0. For k + 1, if the set of resources A is empty or if the maximum expectation over all choices in A is non-positive, V(A, k + 1) simplifies to 0, which is again attained by the empty list.
uses
List.nodup_nilprivate theorem omsr_patience_single_arrival_optimal_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_patience_single_arrival_optimal_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_patience_single_arrival_optimal_bestVal arr w A (k + 1) = max 0 (A.sup' hA (fun i => arr.prob i * w i + (1 - arr.prob i) * omsr_patience_single_arrival_optimal_bestVal arr w (A.erase i) k)) := by simp only [omsr_patience_single_arrival_optimal_bestVal, dif_pos hA] by_cases hX : A.sup' hA (fun i => arr.prob i * w i + (1 - arr.prob i) * omsr_patience_single_arrival_optimal_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 optimal value is strictly positive, prepending the maximizing resource to an optimal sub-sequence achieves V(A, k + 1).
Since the supremum over the finite nonempty set A is strictly positive, Finset.exists_mem_eq_sup' yields an optimal first resource i ∈ A. By the induction hypothesis on A \ {i}, there is a valid probe sequence L ⊆ A \ {i} of length at most k achieving V(A \ {i}, k). Prepending i yields a duplicate-free list i :: L ⊆ A of length at most k + 1. Using omsr_patience_single_arrival_optimal_probeValue_zero_indep, the probe value of i :: L matches the Bellman step, attaining V(A, k + 1).
uses
Finset.exists_mem_eq_sup',omsr_patience_single_arrival_optimal_probeValue_zero_indep· have hXpos : 0 < A.sup' hA (fun i => arr.prob i * w i + (1 - arr.prob i) * omsr_patience_single_arrival_optimal_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_patience_single_arrival_optimal_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_patience_single_arrival_optimal_probeValue_zero_indep arr w A (A.erase i) L, hLval, hsup] · refine ⟨[], List.nodup_nil, by simp, by simp, ?_⟩ simp only [omsr_patience_single_arrival_optimal_bestVal, dif_neg hA] rfl
When all arrivals have already been matched, the offline dynamic program returns zero.
We induct on the fuel parameter. At fuel 0, optDP is 0 by definition. At fuel + 1, optDP takes the maximum of 0 and a supremum over transitions. Every valid transition requires an unmatched arrival, which contradicts the hypothesis that all arrivals are matched. The supremum over an empty condition is bounded by 0 via Real.iSup_le, so optDP evaluates to 0.
uses
Real.iSup_leprivate theorem omsr_patience_single_arrival_optimal_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) hcond.2.1
For a single arrival instance, any possible probing transition in the offline dynamic program transitions either to a matched state with zero continuation or to an updated probed set.
We induct on fuel to bound optDP on a single arrival against V(S \ P, patience - |P|). At fuel 0, the value is 0 ≤ V by non-negativity. At fuel + 1, we bound each transition (t, i) with i ∈ S \ P. Since m = 1, arrival index t is unique. If the probe succeeds, the arrival is matched and by omsr_patience_single_arrival_optimal_optDP_all_matched the continuation is 0. If the probe fails, the state transitions to probed set P ∪ {i}.
uses
omsr_patience_single_arrival_optimal_optDP_all_matchedprivate theorem omsr_patience_single_arrival_optimal_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_patience_single_arrival_optimal_bestVal arr w (S \ P) (arr.patience - P.card) := by intro fuel induction fuel with | zero => intro S P simp only [optDP] exact omsr_patience_single_arrival_optimal_bestVal_nonneg arr w _ _ | succ fuel ih => intro S P simp only [optDP] refine max_le (omsr_patience_single_arrival_optimal_bestVal_nonneg arr w _ _) ?_ refine Real.iSup_le (fun t => ?_) (omsr_patience_single_arrival_optimal_bestVal_nonneg arr w _ _) refine Real.iSup_le (fun i => ?_) (omsr_patience_single_arrival_optimal_bestVal_nonneg arr w _ _) refine Real.iSup_le (fun hcond => ?_) (omsr_patience_single_arrival_optimal_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 : optDP w fuel (S.erase i) (fun j : Fin 1 => if j = t then (⟨arr, P, true⟩ : OfflineArrival n) else ⟨arr, P, false⟩) = 0 := by refine omsr_patience_single_arrival_optimal_optDP_all_matched w _ (fun j => ?_) fuel (S.erase i) rw [if_pos (Subsingleton.elim j t)] have hfail : (fun j : Fin 1 => if j = t then (⟨arr, insert i P, false⟩ : OfflineArrival n) else ⟨arr, P, false⟩) = fun _ => ⟨arr, insert i P, false⟩ := by funext j rw [if_pos (Subsingleton.elim j t)] rw [hsucc, hfail]
The expected continuation of each offline transition is bounded by the Bellman step inequality, completing the inductive bound for optDP.
Applying the induction hypothesis to the failure continuation with probed set P ∪ {i}, the expected return is at most p_i * w_i + (1 - p_i) * V(S \ (P ∪ {i}), patience - |P ∪ {i}|). Rewriting S \ (P ∪ {i}) = (S \ P) \ {i} and |P ∪ {i}| = |P| + 1, omsr_patience_single_arrival_optimal_bestVal_step_le bounds this by V(S \ P, patience - |P|), bounding the supremum over transitions.
uses
omsr_patience_single_arrival_optimal_bestVal_step_lehave hIH := ih S (insert i P) have hbounded : arr.prob i * w i + (1 - arr.prob i) * omsr_patience_single_arrival_optimal_bestVal arr w (S \ insert i P) (arr.patience - (insert i P).card) ≤ omsr_patience_single_arrival_optimal_bestVal arr w (S \ P) (arr.patience - P.card) := by have hsdiff : S \ insert i P = (S \ P).erase i := by ext x simp only [Finset.mem_sdiff, Finset.mem_insert, Finset.mem_erase] tauto have hcard : (insert i P).card = P.card + 1 := Finset.card_insert_of_notMem hP have hsub : arr.patience - (insert i P).card = (arr.patience - P.card) - 1 := by rw [hcard]; omega rw [hsdiff, hsub] have hstep := omsr_patience_single_arrival_optimal_bestVal_step_le arr w hA hmemA (arr.patience - P.card - 1) have hk : arr.patience - P.card - 1 + 1 = arr.patience - P.card := by omega rwa [hk] at hstep calc arr.prob i * (w i + 0) + (1 - arr.prob i) * optDP w fuel S (fun _ => (⟨arr, insert i P, false⟩ : OfflineArrival n)) ≤ arr.prob i * w i + (1 - arr.prob i) * omsr_patience_single_arrival_optimal_bestVal arr w (S \ insert i P) (arr.patience - (insert i P).card) := by have hp1 : (0:ℝ) ≤ 1 - arr.prob i := by linarith [arr.prob_le_one i] have hmul := mul_le_mul_of_nonneg_left hIH hp1 rw [add_zero] linarith _ ≤ omsr_patience_single_arrival_optimal_bestVal arr w (S \ P) (arr.patience - P.card) := hbounded
The deterministic online probing sequence selected by the policy is valid and attains the optimal single-arrival value.
The deterministic policy selects the sequence attaining V(S, arr.patience) given by bestVal_attained. Lemma omsr_patience_single_arrival_optimal_policy_spec provides its properties, and omsr_patience_single_arrival_optimal_policy_valid packages the nodup, subset, and length conditions into IsValidProbeSeq.
uses
omsr_patience_single_arrival_optimal_policy_specprivate noncomputable def omsr_patience_single_arrival_optimal_policy {n : ℕ} (arr : OMSRArrival n) (w : Fin n → ℝ) (S : Finset (Fin n)) : List (Fin n) := (omsr_patience_single_arrival_optimal_bestVal_attained arr w S arr.patience).choose private theorem omsr_patience_single_arrival_optimal_policy_spec {n : ℕ} (arr : OMSRArrival n) (w : Fin n → ℝ) (S : Finset (Fin n)) : (omsr_patience_single_arrival_optimal_policy arr w S).Nodup ∧ (∀ i ∈ omsr_patience_single_arrival_optimal_policy arr w S, i ∈ S) ∧ (omsr_patience_single_arrival_optimal_policy arr w S).length ≤ arr.patience ∧ probeValue arr w (fun _ => 0) S (omsr_patience_single_arrival_optimal_policy arr w S) = omsr_patience_single_arrival_optimal_bestVal arr w S arr.patience := (omsr_patience_single_arrival_optimal_bestVal_attained arr w S arr.patience).choose_spec private theorem omsr_patience_single_arrival_optimal_policy_valid {n : ℕ} (arr : OMSRArrival n) (w : Fin n → ℝ) (S : Finset (Fin n)) : IsValidProbeSeq arr S (omsr_patience_single_arrival_optimal_policy arr w S) := by obtain ⟨h1, h2, h3, -⟩ := omsr_patience_single_arrival_optimal_policy_spec arr w S exact ⟨h1, h2, h3⟩ private theorem omsr_patience_single_arrival_optimal_policy_value {n : ℕ} (arr : OMSRArrival n) (w : Fin n → ℝ) (S : Finset (Fin n)) : probeValue arr w (fun _ => 0) S (omsr_patience_single_arrival_optimal_policy arr w S) = omsr_patience_single_arrival_optimal_bestVal arr w S arr.patience := (omsr_patience_single_arrival_optimal_policy_spec arr w S).2.2.2
For a singleton arrival list [arr], the offline optimal value is bounded above by V(univ, arr.patience).
By definition, offlineOptValue evaluates optDP initialized with all resources available (S = univ) and no resources probed (P = ∅). Applying omsr_patience_single_arrival_optimal_optDP_single_le with P = ∅ yields the upper bound V(univ, arr.patience).
uses
omsr_patience_single_arrival_optimal_optDP_single_leprivate theorem omsr_patience_single_arrival_optimal_offline_singleton_le {n : ℕ} (arr : OMSRArrival n) (w : Fin n → ℝ) : offlineOptValue w [arr] ≤ omsr_patience_single_arrival_optimal_bestVal arr w Finset.univ arr.patience := by have h : offlineOptValue w [arr] = optDP (m := 1) w n Finset.univ (fun _ => (⟨arr, ∅, false⟩ : OfflineArrival n)) := by simp [offlineOptValue] rw [h] have hb := omsr_patience_single_arrival_optimal_optDP_single_le arr w n Finset.univ (∅ : Finset (Fin n)) simpa using hb
For a singleton arrival list [arr], the online policy value equals V(univ, arr.patience).
Unfolding onlinePolicyValue on a singleton list reduces it directly to the probe value of the policy's chosen sequence with zero terminal continuation, which by omsr_patience_single_arrival_optimal_policy_value is equal to V(univ, arr.patience).
uses
omsr_patience_single_arrival_optimal_policy_valueprivate theorem omsr_patience_single_arrival_optimal_online_singleton {n : ℕ} (arr : OMSRArrival n) (w : Fin n → ℝ) : onlinePolicyValue w (fun arr S => omsr_patience_single_arrival_optimal_policy arr w S) [arr] Finset.univ = omsr_patience_single_arrival_optimal_bestVal arr w Finset.univ arr.patience := by have h : onlinePolicyValue w (fun arr S => omsr_patience_single_arrival_optimal_policy arr w S) [arr] Finset.univ = probeValue arr w (fun _ => 0) Finset.univ (omsr_patience_single_arrival_optimal_policy arr w Finset.univ) := rfl rw [h] exact omsr_patience_single_arrival_optimal_policy_value arr w Finset.univ
The randomized policy supported on a Dirac measure has expected online value equal to the deterministic online policy value.
We define the randomized policy by placing a Dirac measure on the unique element of PUnit. By MeasureTheory.integral_dirac, the expected online value under this measure evaluates to the online policy value of the deterministic policy.
uses
MeasureTheory.integral_diracprivate noncomputable def omsr_patience_single_arrival_optimal_randomized {n : ℕ} (w : Fin n → ℝ) : RandomizedOMSRPolicy n where Ω := PUnit mΩ := inferInstance μ := MeasureTheory.Measure.dirac PUnit.unit hμ := inferInstance policy := fun _ arr S => omsr_patience_single_arrival_optimal_policy arr w S valid := fun _ arr S => omsr_patience_single_arrival_optimal_policy_valid arr w S private theorem omsr_patience_single_arrival_optimal_expected_eq {n : ℕ} (w : Fin n → ℝ) (arrs : List (OMSRArrival n)) : expectedOnlineValue w (omsr_patience_single_arrival_optimal_randomized w) arrs = onlinePolicyValue w (fun arr S => omsr_patience_single_arrival_optimal_policy arr w S) arrs Finset.univ := by unfold expectedOnlineValue omsr_patience_single_arrival_optimal_randomized simp only exact MeasureTheory.integral_dirac _ _
Fix the weights and arrival sequence of length at most 1, and case split on whether the arrival list is empty, a singleton, or longer.
We provide the Dirac randomized policy as the witness and assume an arrival list arrs with length at most 1. Using omsr_patience_single_arrival_optimal_expected_eq, we rewrite the expected online value to the deterministic online policy value, then case split on the list structure of arrs.
uses
omsr_patience_single_arrival_optimal_expected_eq/-- Single-arrival instances achieve competitive ratio 1 against OPT. -/ theorem omsr_patience_single_arrival_optimal : ∀ (n : ℕ) (w : Fin n → ℝ), (∀ i, 0 ≤ w i) → ∃ R : RandomizedOMSRPolicy n, ∀ arrs : List (OMSRArrival n), arrs.length ≤ 1 → offlineOptValue w arrs ≤ expectedOnlineValue w R arrs := by intro n w hw refine ⟨omsr_patience_single_arrival_optimal_randomized w, ?_⟩ intro arrs hlen rw [omsr_patience_single_arrival_optimal_expected_eq w arrs] rcases arrs with _ | ⟨a, _ | ⟨b, rest⟩⟩
When the arrival list is empty, both offline and online values are zero. automation
Both offlineOptValue and onlinePolicyValue evaluate to 0 by definition on the empty list, closing the inequality 0 ≤ 0.
· simp [offlineOptValue, onlinePolicyValue, optDP]When the arrival list is a singleton [a], the offline optimum is bounded above by the online value.
By omsr_patience_single_arrival_optimal_online_singleton, the online policy achieves the optimal value V(univ, a.patience). By omsr_patience_single_arrival_optimal_offline_singleton_le, the offline optimum is at most V(univ, a.patience), completing the bound offlineOptValue ≤ expectedOnlineValue.
uses
omsr_patience_single_arrival_optimal_online_singleton,omsr_patience_single_arrival_optimal_offline_singleton_le· rw [omsr_patience_single_arrival_optimal_online_singleton a w] exact omsr_patience_single_arrival_optimal_offline_singleton_le a w
The case of an arrival list of length at least two is impossible. automation
An arrival list with two or more elements contradicts the assumption that arrs.length ≤ 1, which Lean simplifies to false.
· simp at hlen
le_max_left- For any elements a, b in a linear order, a ≤ max a b.
Finset.le_sup'- An element's value is bounded above by the supremum over any nonempty finite set containing it.
le_max_right- For any elements a, b in a linear order, b ≤ max a b.
List.nodup_nil- The empty list has no duplicate elements.
Finset.exists_mem_eq_sup'- On a nonempty finite set, the supremum of a real-valued function is attained at some element of the set.
omsr_patience_single_arrival_optimal_probeValue_zero_indep- When the terminal continuation value is identically zero, the probe value does not depend on the set of available resources.
Real.iSup_le- The supremum of an indexed family of real numbers is bounded by a non-negative constant if every term is bounded by that constant.
omsr_patience_single_arrival_optimal_optDP_all_matched- When all arrivals are already matched, the offline dynamic programming value is zero.
omsr_patience_single_arrival_optimal_bestVal_step_le- The expected value of probing resource i followed by the optimal k-step continuation is bounded by the (k+1)-step optimal value.
omsr_patience_single_arrival_optimal_policy_spec- The sequence selected by the policy is duplicate-free, contains only available resources, has length at most patience, and attains the optimal single-arrival value.
omsr_patience_single_arrival_optimal_optDP_single_le- The offline dynamic program for a single arrival is bounded by the single-arrival dynamic programming value.
omsr_patience_single_arrival_optimal_policy_value- The expected probe value of the single-arrival policy equals the optimal single-arrival value.
MeasureTheory.integral_dirac- The integral of a function with respect to the Dirac delta measure evaluates to the function value at the support point.
omsr_patience_single_arrival_optimal_expected_eq- The expected online value under the Dirac randomized policy equals the value of the underlying deterministic online policy.
omsr_patience_single_arrival_optimal_online_singleton- On a singleton arrival sequence, the online policy value equals the optimal single-arrival value.
omsr_patience_single_arrival_optimal_offline_singleton_le- On a singleton arrival sequence, the offline optimal value is bounded above by the optimal single-arrival value.
- The online policy is deterministic; it is formalized as a randomized policy by placing a Dirac probability measure on the singleton space PUnit.
- The offline dynamic program optDP carries an auxiliary fuel parameter to ensure well-founded recursion in Lean, which is initialized to m * n.
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.
open Classicalprivate noncomputable def omsr_patience_single_arrival_optimal_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_patience_single_arrival_optimal_bestVal arr w (A.erase i) k)) else 0private theorem omsr_patience_single_arrival_optimal_bestVal_nonneg {n : ℕ} (arr : OMSRArrival n) (w : Fin n → ℝ) (A : Finset (Fin n)) (k : ℕ) : 0 ≤ omsr_patience_single_arrival_optimal_bestVal arr w A k := by induction k generalizing A with | zero => simp [omsr_patience_single_arrival_optimal_bestVal] | succ k ih => by_cases h : A.Nonempty · rw [omsr_patience_single_arrival_optimal_bestVal, dif_pos h] exact le_max_left _ _ · rw [omsr_patience_single_arrival_optimal_bestVal, dif_neg h]private theorem omsr_patience_single_arrival_optimal_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_patience_single_arrival_optimal_bestVal arr w (A.erase i) k ≤ omsr_patience_single_arrival_optimal_bestVal arr w A (k + 1) := by rw [omsr_patience_single_arrival_optimal_bestVal, dif_pos h] exact le_trans (Finset.le_sup' (fun i => arr.prob i * w i + (1 - arr.prob i) * omsr_patience_single_arrival_optimal_bestVal arr w (A.erase i) k) hi) (le_max_right _ _)private theorem omsr_patience_single_arrival_optimal_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]private theorem omsr_patience_single_arrival_optimal_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_patience_single_arrival_optimal_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_patience_single_arrival_optimal_bestVal arr w A (k + 1) = max 0 (A.sup' hA (fun i => arr.prob i * w i + (1 - arr.prob i) * omsr_patience_single_arrival_optimal_bestVal arr w (A.erase i) k)) := by simp only [omsr_patience_single_arrival_optimal_bestVal, dif_pos hA] by_cases hX : A.sup' hA (fun i => arr.prob i * w i + (1 - arr.prob i) * omsr_patience_single_arrival_optimal_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_patience_single_arrival_optimal_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_patience_single_arrival_optimal_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_patience_single_arrival_optimal_probeValue_zero_indep arr w A (A.erase i) L, hLval, hsup] · refine ⟨[], List.nodup_nil, by simp, by simp, ?_⟩ simp only [omsr_patience_single_arrival_optimal_bestVal, dif_neg hA] rflprivate theorem omsr_patience_single_arrival_optimal_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) hcond.2.1private theorem omsr_patience_single_arrival_optimal_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_patience_single_arrival_optimal_bestVal arr w (S \ P) (arr.patience - P.card) := by intro fuel induction fuel with | zero => intro S P simp only [optDP] exact omsr_patience_single_arrival_optimal_bestVal_nonneg arr w _ _ | succ fuel ih => intro S P simp only [optDP] refine max_le (omsr_patience_single_arrival_optimal_bestVal_nonneg arr w _ _) ?_ refine Real.iSup_le (fun t => ?_) (omsr_patience_single_arrival_optimal_bestVal_nonneg arr w _ _) refine Real.iSup_le (fun i => ?_) (omsr_patience_single_arrival_optimal_bestVal_nonneg arr w _ _) refine Real.iSup_le (fun hcond => ?_) (omsr_patience_single_arrival_optimal_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 : optDP w fuel (S.erase i) (fun j : Fin 1 => if j = t then (⟨arr, P, true⟩ : OfflineArrival n) else ⟨arr, P, false⟩) = 0 := by refine omsr_patience_single_arrival_optimal_optDP_all_matched w _ (fun j => ?_) fuel (S.erase i) rw [if_pos (Subsingleton.elim j t)] have hfail : (fun j : Fin 1 => if j = t then (⟨arr, insert i P, false⟩ : OfflineArrival n) else ⟨arr, P, false⟩) = fun _ => ⟨arr, insert i P, false⟩ := by funext j rw [if_pos (Subsingleton.elim j t)] rw [hsucc, hfail] have hIH := ih S (insert i P) have hbounded : arr.prob i * w i + (1 - arr.prob i) * omsr_patience_single_arrival_optimal_bestVal arr w (S \ insert i P) (arr.patience - (insert i P).card) ≤ omsr_patience_single_arrival_optimal_bestVal arr w (S \ P) (arr.patience - P.card) := by have hsdiff : S \ insert i P = (S \ P).erase i := by ext x simp only [Finset.mem_sdiff, Finset.mem_insert, Finset.mem_erase] tauto have hcard : (insert i P).card = P.card + 1 := Finset.card_insert_of_notMem hP have hsub : arr.patience - (insert i P).card = (arr.patience - P.card) - 1 := by rw [hcard]; omega rw [hsdiff, hsub] have hstep := omsr_patience_single_arrival_optimal_bestVal_step_le arr w hA hmemA (arr.patience - P.card - 1) have hk : arr.patience - P.card - 1 + 1 = arr.patience - P.card := by omega rwa [hk] at hstep calc arr.prob i * (w i + 0) + (1 - arr.prob i) * optDP w fuel S (fun _ => (⟨arr, insert i P, false⟩ : OfflineArrival n)) ≤ arr.prob i * w i + (1 - arr.prob i) * omsr_patience_single_arrival_optimal_bestVal arr w (S \ insert i P) (arr.patience - (insert i P).card) := by have hp1 : (0:ℝ) ≤ 1 - arr.prob i := by linarith [arr.prob_le_one i] have hmul := mul_le_mul_of_nonneg_left hIH hp1 rw [add_zero] linarith _ ≤ omsr_patience_single_arrival_optimal_bestVal arr w (S \ P) (arr.patience - P.card) := hboundedprivate noncomputable def omsr_patience_single_arrival_optimal_policy {n : ℕ} (arr : OMSRArrival n) (w : Fin n → ℝ) (S : Finset (Fin n)) : List (Fin n) := (omsr_patience_single_arrival_optimal_bestVal_attained arr w S arr.patience).chooseprivate theorem omsr_patience_single_arrival_optimal_policy_spec {n : ℕ} (arr : OMSRArrival n) (w : Fin n → ℝ) (S : Finset (Fin n)) : (omsr_patience_single_arrival_optimal_policy arr w S).Nodup ∧ (∀ i ∈ omsr_patience_single_arrival_optimal_policy arr w S, i ∈ S) ∧ (omsr_patience_single_arrival_optimal_policy arr w S).length ≤ arr.patience ∧ probeValue arr w (fun _ => 0) S (omsr_patience_single_arrival_optimal_policy arr w S) = omsr_patience_single_arrival_optimal_bestVal arr w S arr.patience := (omsr_patience_single_arrival_optimal_bestVal_attained arr w S arr.patience).choose_specprivate theorem omsr_patience_single_arrival_optimal_policy_valid {n : ℕ} (arr : OMSRArrival n) (w : Fin n → ℝ) (S : Finset (Fin n)) : IsValidProbeSeq arr S (omsr_patience_single_arrival_optimal_policy arr w S) := by obtain ⟨h1, h2, h3, -⟩ := omsr_patience_single_arrival_optimal_policy_spec arr w S exact ⟨h1, h2, h3⟩private theorem omsr_patience_single_arrival_optimal_policy_value {n : ℕ} (arr : OMSRArrival n) (w : Fin n → ℝ) (S : Finset (Fin n)) : probeValue arr w (fun _ => 0) S (omsr_patience_single_arrival_optimal_policy arr w S) = omsr_patience_single_arrival_optimal_bestVal arr w S arr.patience := (omsr_patience_single_arrival_optimal_policy_spec arr w S).2.2.2private theorem omsr_patience_single_arrival_optimal_offline_singleton_le {n : ℕ} (arr : OMSRArrival n) (w : Fin n → ℝ) : offlineOptValue w [arr] ≤ omsr_patience_single_arrival_optimal_bestVal arr w Finset.univ arr.patience := by have h : offlineOptValue w [arr] = optDP (m := 1) w n Finset.univ (fun _ => (⟨arr, ∅, false⟩ : OfflineArrival n)) := by simp [offlineOptValue] rw [h] have hb := omsr_patience_single_arrival_optimal_optDP_single_le arr w n Finset.univ (∅ : Finset (Fin n)) simpa using hbprivate theorem omsr_patience_single_arrival_optimal_online_singleton {n : ℕ} (arr : OMSRArrival n) (w : Fin n → ℝ) : onlinePolicyValue w (fun arr S => omsr_patience_single_arrival_optimal_policy arr w S) [arr] Finset.univ = omsr_patience_single_arrival_optimal_bestVal arr w Finset.univ arr.patience := by have h : onlinePolicyValue w (fun arr S => omsr_patience_single_arrival_optimal_policy arr w S) [arr] Finset.univ = probeValue arr w (fun _ => 0) Finset.univ (omsr_patience_single_arrival_optimal_policy arr w Finset.univ) := rfl rw [h] exact omsr_patience_single_arrival_optimal_policy_value arr w Finset.univprivate noncomputable def omsr_patience_single_arrival_optimal_randomized {n : ℕ} (w : Fin n → ℝ) : RandomizedOMSRPolicy n where Ω := PUnit mΩ := inferInstance μ := MeasureTheory.Measure.dirac PUnit.unit hμ := inferInstance policy := fun _ arr S => omsr_patience_single_arrival_optimal_policy arr w S valid := fun _ arr S => omsr_patience_single_arrival_optimal_policy_valid arr w Sprivate theorem omsr_patience_single_arrival_optimal_expected_eq {n : ℕ} (w : Fin n → ℝ) (arrs : List (OMSRArrival n)) : expectedOnlineValue w (omsr_patience_single_arrival_optimal_randomized w) arrs = onlinePolicyValue w (fun arr S => omsr_patience_single_arrival_optimal_policy arr w S) arrs Finset.univ := by unfold expectedOnlineValue omsr_patience_single_arrival_optimal_randomized simp only exact MeasureTheory.integral_dirac _ _/-- Single-arrival instances achieve competitive ratio 1 against OPT. -/theorem omsr_patience_single_arrival_optimal : ∀ (n : ℕ) (w : Fin n → ℝ), (∀ i, 0 ≤ w i) → ∃ R : RandomizedOMSRPolicy n, ∀ arrs : List (OMSRArrival n), arrs.length ≤ 1 → offlineOptValue w arrs ≤ expectedOnlineValue w R arrs := by intro n w hw refine ⟨omsr_patience_single_arrival_optimal_randomized w, ?_⟩ intro arrs hlen rw [omsr_patience_single_arrival_optimal_expected_eq w arrs] rcases arrs with _ | ⟨a, _ | ⟨b, rest⟩⟩ · simp [offlineOptValue, onlinePolicyValue, optDP] · rw [omsr_patience_single_arrival_optimal_online_singleton a w] exact omsr_patience_single_arrival_optimal_offline_singleton_le a w · simp at hlen