OMSRArrival
structure
An arrival in online bipartite matching with stochastic rewards and patience facing n offline resources, consisting of a patience budget of at least 1 and probe success probabilities in [0, 1].
Statement
structure OMSRArrival (n : ℕ)- Defined in
- scout/2611-03598-online-matching-with-arbitrary-stochastic-rewards.md:405
- Verified
- 04 Nov 2026
- Axioms
- none listed
- Used by 10
- onlinePolicyValueThe expected total reward of a deterministic online policy π on an arrival list arrs starting from available resources S with resource…
- optDPFor resource weights w : Fin n → ℝ, fuel : ℕ, available resources S : Finset (Fin n), and arrival states arrs : Fin m → OfflineArrival n,…
- omsr_patience_single_arrival_optimalFor 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…
- 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…
- probeValueGiven arrival arr with success probabilities arr.prob, resource weights w, continuation value function V on subsets of resources, and…
- OfflineArrivalThe state of an arrival in the offline benchmark, tracking its arrival data, the set of resources already probed for it, and whether it…
- omsr_single_arrival_optimal_probeSeq_existsFor any resource weights w ≥ 0 and single arrival arr, there exists a valid probe sequence L from the full resource set univ whose probe…
- IsValidProbeSeqA list of offline resources is a valid probe sequence for an arrival from available resources if it has no duplicates, all its resources…
- offlineOptValueThe expected reward of the adaptive offline benchmark OPT on a list of arrivals arrs with resource weights w, defined by running optDP…
Read back from the Lean
The structure OMSRArrival, parameterized by a natural number n : ℕ, consists of:
1. patience : ℕ, a natural number;
2. patience_pos : 1 ≤ patience, an assertion that patience is at least 1;
3. prob : Fin n → ℝ, a function assigning a real number to each element of Fin n;
4. prob_nonneg : ∀ i : Fin n, 0 ≤ prob i, asserting that each prob i is non-negative;
5. prob_le_one : ∀ i : Fin n, prob i ≤ 1, asserting that each prob i is at most 1.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
Lean source view module on GitHub
/-- An arrival in online matching with stochastic rewards and patience facing n offline resources. -/ structure OMSRArrival (n : ℕ) where patience : ℕ patience_pos : 1 ≤ patience prob : Fin n → ℝ prob_nonneg : ∀ i, 0 ≤ prob i prob_le_one : ∀ i, prob i ≤ 1