AFTD Auto-Formalizing Theoretical Domains

omsr_patience_single_arrival_optimal

theoremverifiedformalization

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.

  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.

    lines 12–22

    uses le_max_left

    private 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]
    
  2. 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.

    lines 23–31

    uses Finset.le_sup', le_max_right

    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 _ _)
    
  3. 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.

    lines 32–40

    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]
    
  4. 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.

    lines 41–57

    uses List.nodup_nil

    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
  5. 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).

    lines 58–80

    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
    
  6. 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.

    lines 81–95

    uses Real.iSup_le

    private 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
    
  7. 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}.

    lines 96–128

    uses omsr_patience_single_arrival_optimal_optDP_all_matched

    private 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]
  8. 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.

    lines 129–154

    uses omsr_patience_single_arrival_optimal_bestVal_step_le

        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) := hbounded
    
  9. 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.

    lines 155–179

    uses omsr_patience_single_arrival_optimal_policy_spec

    private 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
    
  10. 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).

    lines 180–189

    uses omsr_patience_single_arrival_optimal_optDP_single_le

    private 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
    
  11. 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).

    lines 190–199

    uses omsr_patience_single_arrival_optimal_policy_value

    private 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
    
  12. 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.

    lines 200–216

    uses MeasureTheory.integral_dirac

    private 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 _ _
    
  13. 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.

    lines 217–227

    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⟩⟩
  14. 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.

    line 228

      · simp [offlineOptValue, onlinePolicyValue, optDP]
  15. 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.

    lines 229–230

    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
  16. 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.

    line 231

      · 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.

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

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
See it in the graphDiscuss this resultChallenge it