bellman_value
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