AFTD Auto-Formalizing Theoretical Domains

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