AFTD Auto-Formalizing Theoretical Domains

bellman_value

def

For a simple graph G on vertex set Fin n with decidable adjacency, an observed edge set H : Finset (Sym2 (Fin n)), and an unmatched vertex set U : Finset (Fin n), bellman_value G H U is the dynamic programming value function V(H, U) defined backwards by recursion on G.edgeFinset.card - H.card: 0 when G.edgeFinset.card - H.card = 0, and otherwise the sum over e : Sym2 (Fin n) satisfying e ∉ H and 0 < compatible_labelings G (insert e H) of edge_arrival_prob G H e multiplied by (if e.toFinset ⊆ U then max (bellman_value G (insert e H) U) (1 + bellman_value G (insert e H) (U \ e.toFinset)) else bellman_value G (insert e H) U).

Statement

noncomputable def bellman_value {n : ℕ} (G : SimpleGraph (Fin n)) [DecidableRel G.Adj]
    (H : Finset (Sym2 (Fin n))) (U : Finset (Fin n)) : ℝ
Defined in
arXiv:2611.13571, Section 5.1, Equation (14)
Verified
12 Nov 2026
Axioms
none listed
Built on 2
  • compatible_labelingsFor a simple graph G on vertex set Fin n with decidable adjacency, and a finite set H of observed edges (H : Finset (Sym2 (Fin n))),…
  • edge_arrival_probFor a simple graph G on vertex set Fin n with decidable adjacency, a finite set H : Finset (Sym2 (Fin n)) of observed edges, and an edge e…
Used by 4
  • online_matching_policy_value_le_bellmanFor a simple graph G on vertex set Fin n with decidable adjacency, every online matching policy pol : OnlineMatchingPolicy n satisfies…
  • optimal_online_matching_policyFor every simple graph G on vertex set Fin n with decidable adjacency, the optimal online matching policy achieves policy_value G…
  • optimal_online_policyFor a simple graph G on vertex set Fin n with decidable adjacency, optimal_online_policy G is the online matching policy that accepts an…
  • optimal_online_matching_policy_achieves_valueFor a simple graph G on vertex set Fin n with decidable adjacency, the optimal online matching policy optimal_online_policy G achieves…

Read back from the Lean

bellman_value is a noncomputable definition that takes: - a natural number n (implicit), - a simple graph G on vertex set Fin n with decidable adjacency [DecidableRel G.Adj], - a finite set of unordered pairs of vertices H : Finset (Sym2 (Fin n)) (representing currently observed/revealed edges), and - a finite set of vertices U : Finset (Fin n) (representing currently available/unmatched vertices), and returns a real number ℝ. The value is computed by an auxiliary function aux (|E(G)| - |H|) H U (where |E(G)| - |H| is truncated natural subtraction G.edgeFinset.card - H.card). The function aux : ℕ → Finset (Sym2 (Fin n)) → Finset (Fin n) → ℝ is defined recursively by: - aux 0 H' U' = 0 - For k + 1, aux (k + 1) H' U' is the sum over all unordered pairs of vertices e ∈ Sym2 (Fin n) of: - If e ∉ H' and 0 < compatible_labelings G (insert e H'): edge_arrival_prob G H' e * (if e.toFinset ⊆ U' then max (aux k (insert e H') U') (1 + aux k (insert e H') (U' \ e.toFinset)) else aux k (insert e H') U') - Otherwise: 0. Here: - compatible_labelings G H is the number of permutations π : Equiv.Perm (Fin n) such that every edge in H is an edge of the graph G permuted by π (i.e., H ⊆ (G.map π.toEmbedding).edgeFinset). - edge_arrival_prob G H e is 0 if (|E(G)| - |H|) * compatible_labelings G H = 0, and otherwise is compatible_labelings G (insert e H) / ((|E(G)| - |H|) * compatible_labelings G H). - e.toFinset ⊆ U' checks whether all endpoints of e belong to U'. When both endpoints are in U', the Bellman update takes the maximum between skipping e (value aux k (insert e H') U') and matching e (value 1 + aux k (insert e H') (U' \ e.toFinset)).

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

/-- The optimal value function V(H, U) defined backwards from V(H, U) = 0 when |E(H)| = m. -/
noncomputable def bellman_value {n : ℕ} (G : SimpleGraph (Fin n)) [DecidableRel G.Adj]
    (H : Finset (Sym2 (Fin n))) (U : Finset (Fin n)) : ℝ :=
  aux (G.edgeFinset.card - H.card) H U
where
  aux : ℕ → Finset (Sym2 (Fin n)) → Finset (Fin n) → ℝ
    | 0, _, _ => 0
    | k + 1, H', U' =>
      ∑ e ∈ (Finset.univ : Finset (Sym2 (Fin n))),
        if e ∉ H' ∧ 0 < compatible_labelings G (insert e H') then
          edge_arrival_prob G H' e *
            (if e.toFinset ⊆ U' then
              max (aux k (insert e H') U') (1 + aux k (insert e H') (U' \ e.toFinset))
            else
              aux k (insert e H') U')
        else 0
See it in the graphDiscuss this resultChallenge it