AFTD Auto-Formalizing Theoretical Domains

probeValue

def

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