probeValue
Given arrival arr with success probabilities arr.prob, resource weights w, continuation value function V on subsets of resources, and available resources S, probeValue recursively computes the expected reward of probing sequence L: on empty sequence it yields V S; on probing i :: L, with probability arr.prob i it matches i yielding reward w i + V (S.erase i), and with probability 1 - arr.prob i it continues to probe sequence L.
Statement
def probeValue {n : ℕ} (arr : OMSRArrival n) (w : Fin n → ℝ) (V : Finset (Fin n) → ℝ) (S : Finset (Fin n)) :
List (Fin n) → ℝ- Defined in
- scout/2611-03598-online-matching-with-arbitrary-stochastic-rewards.md:415
- Verified
- 04 Nov 2026
- Axioms
- none listed
- Built on 1
- OMSRArrivalAn arrival in online bipartite matching with stochastic rewards and patience facing n offline resources, consisting of a patience budget…
- Used by 3
- onlinePolicyValueThe expected total reward of a deterministic online policy π on an arrival list arrs starting from available resources S with resource…
- 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…
- 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…
Read back from the Lean
A recursive function probeValue which, given a natural number n, an arrival model arr : OMSRArrival n, a weight function w : Fin n → ℝ, a value function V : Finset (Fin n) → ℝ, and a subset S : Finset (Fin n), computes a real value for a list of items L : List (Fin n) by recursion on L:
- Base case ([]): returns V S.
- Inductive case (i :: L): returns arr.prob i * (w i + V (S.erase i)) + (1 - arr.prob i) * probeValue arr w V S L.
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
/-- Expected reward from probing a list of resources sequentially for an arrival. -/ def probeValue {n : ℕ} (arr : OMSRArrival n) (w : Fin n → ℝ) (V : Finset (Fin n) → ℝ) (S : Finset (Fin n)) : List (Fin n) → ℝ | [] => V S | i :: L => arr.prob i * (w i + V (S.erase i)) + (1 - arr.prob i) * probeValue arr w V S L