AFTD Auto-Formalizing Theoretical Domains

optDP

def

For resource weights w : Fin n → ℝ, fuel : ℕ, available resources S : Finset (Fin n), and arrival states arrs : Fin m → OfflineArrival n, optDP is the dynamic programming value function: 0 when fuel is 0, and otherwise the maximum of 0 and the supremum over valid probes of arrival t and available resource i of p * (w i + optDP w fuel (S.erase i) arrs_succ) + (1 - p) * optDP w fuel S arrs_fail.

Statement

noncomputable def optDP {n m : ℕ} (w : Fin n → ℝ) :
    ℕ → Finset (Fin n) → (Fin m → OfflineArrival n) → ℝ
Defined in
scout/2611-03598-online-matching-with-arbitrary-stochastic-rewards.md:420
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…
  • OfflineArrivalThe state of an arrival in the offline benchmark, tracking its arrival data, the set of resources already probed for it, and whether it…
Used by 3
  • 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…
  • 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

optDP is a noncomputable function that defines the optimal dynamic programming value for a stochastic matching / probing problem with n items and m arrivals. Given: - (implicit) natural numbers n and m, - a weight function w : Fin n → ℝ on items, - a recursion bound fuel : ℕ, - a set of available items S : Finset (Fin n), - an arrival state function arrs : Fin m → OfflineArrival n, optDP w fuel S arrs returns a real number defined recursively on fuel: 1. Base case (fuel = 0): returns 0. 2. Recursive step (fuel + 1, S, arrs): Returns max 0 continue_val, where continue_val is the supremum (⨆) over all arrivals t : Fin m and items i : Fin n satisfying: - i ∈ S (item i is currently available), - ¬ (arrs t).matched (arrival t is not yet matched), - i ∉ (arrs t).probed (item i has not already been probed by arrival t), and - (arrs t).probed.card < (arrs t).arrival.patience (the number of items arrival t has probed is strictly less than its patience parameter), of the expected reward of probing item i for arrival t: p * (w i + optDP w fuel (S.erase i) arrs_succ) + (1 - p) * optDP w fuel S arrs_fail where: - p = (arrs t).arrival.prob i, - arrs_succ : Fin m → OfflineArrival n is the function identical to arrs except at t, where (arrs t).matched is set to true, - arrs_fail : Fin m → OfflineArrival n is the function identical to arrs except at t, where i is inserted into (arrs t).probed.

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

/-- Dynamic programming value of the adaptive offline benchmark. -/
noncomputable def optDP {n m : ℕ} (w : Fin n → ℝ) :
    ℕ → Finset (Fin n) → (Fin m → OfflineArrival n) → ℝ
  | 0, _, _ => 0
  | fuel + 1, S, arrs =>
    let continue_val := ⨆ (t : Fin m) (i : Fin n)
      (_ : i ∈ S ∧ ¬ (arrs t).matched ∧ i ∉ (arrs t).probed ∧ (arrs t).probed.card < (arrs t).arrival.patience),
      let p := (arrs t).arrival.prob i
      let arrs_succ : Fin m → OfflineArrival n :=
        fun j => if j = t then { (arrs t) with matched := true } else arrs j
      let arrs_fail : Fin m → OfflineArrival n :=
        fun j => if j = t then { (arrs t) with probed := insert i (arrs t).probed } else arrs j
      p * (w i + optDP w fuel (S.erase i) arrs_succ) + (1 - p) * optDP w fuel S arrs_fail
    max 0 continue_val
See it in the graphDiscuss this resultChallenge it