RandomizedOMSRPolicy
For n offline resources, a RandomizedOMSRPolicy packages a sample space Ω, a measurable space structure mΩ, a probability measure μ on Ω satisfying IsProbabilityMeasure μ, and a policy function policy : Ω → OMSRArrival n → Finset (Fin n) → List (Fin n) satisfying IsValidProbeSeq arr S (policy ω arr S) for all ω, arr, and S.
Statement
structure RandomizedOMSRPolicy (n : ℕ)- Defined in
- scout/2611-03598-online-matching-with-arbitrary-stochastic-rewards.md:415
- Verified
- 04 Nov 2026
- Axioms
- none listed
- Built on 2
- OMSRArrivalAn arrival in online bipartite matching with stochastic rewards and patience facing n offline resources, consisting of a patience budget…
- IsValidProbeSeqA list of offline resources is a valid probe sequence for an arrival from available resources if it has no duplicates, all its resources…
- Used by 2
- 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…
- 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…
Read back from the Lean
A RandomizedOMSRPolicy parameterized by $n : \mathbb{N}$ is a structure bundling:
1. A type Ω (the sample space),
2. A measurable space structure on Ω,
3. A measure μ on Ω,
4. A proof hμ that μ is a probability measure (IsProbabilityMeasure μ),
5. A function policy : Ω → OMSRArrival n → Finset (Fin n) → List (Fin n), which takes an outcome ω : Ω, an arrival arr : OMSRArrival n, and a subset of available items S : Finset (Fin n), and returns a list of items List (Fin n),
6. A validity condition asserting that for every outcome ω : Ω, every arrival arr : OMSRArrival n, and every subset S : Finset (Fin n), the sequence policy ω arr S is a valid probe sequence with respect to arr and S (IsValidProbeSeq arr S (policy ω arr S)).
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
/-- A randomized online matching policy with patience. -/ structure RandomizedOMSRPolicy (n : ℕ) where Ω : Type mΩ : MeasurableSpace Ω μ : MeasureTheory.Measure Ω hμ : MeasureTheory.IsProbabilityMeasure μ policy : Ω → OMSRArrival n → Finset (Fin n) → List (Fin n) valid : ∀ ω arr S, IsValidProbeSeq arr S (policy ω arr S)