AFTD Auto-Formalizing Theoretical Domains

RandomizedOMSRPolicy

structure

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