optimal_online_policy
For a simple graph G on vertex set Fin n with decidable adjacency, optimal_online_policy G is the online matching policy that accepts an arriving edge e given observed edges H and unmatched vertices U if and only if e.toFinset ⊆ U and bellman_value G (insert e H) U ≤ 1 + bellman_value G (insert e H) (U \ e.toFinset).
Statement
noncomputable def optimal_online_policy {n : ℕ} (G : SimpleGraph (Fin n)) [DecidableRel G.Adj] : OnlineMatchingPolicy n
- Defined in
- arXiv:2611.13571, Lemma 5.1
- Verified
- 12 Nov 2026
- Axioms
- none listed
- Built on 2
- bellman_valueFor 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…
- OnlineMatchingPolicyAn online matching policy on n vertices is a decision rule that, given the observed edges H, unmatched vertices U, and an arriving edge e,…
- Used by 2
- 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_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
Given a natural number n, a simple graph G on vertices Fin n, and a decidability instance for adjacency in G, optimal_online_policy G defines an OnlineMatchingPolicy n.
This policy is a function that takes:
1. H : Finset (Sym2 (Fin n)) (a set of observed edges),
2. U : Finset (Fin n) (a set of currently available/unmatched vertices),
3. e : Sym2 (Fin n) (a candidate/arriving edge),
and returns true if and only if both of the following conditions hold:
- e.toFinset ⊆ U (both endpoints of e belong to U), and
- bellman_value G (insert e H) U ≤ 1 + bellman_value G (insert e H) (U \ e.toFinset) (the expected value of rejecting e is at most 1 plus the expected value of accepting/matching e).
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 online matching policy accepting edge e iff e is feasible and 1 + V(H+e, U \ e) ≥ V(H+e, U). -/ noncomputable def optimal_online_policy {n : ℕ} (G : SimpleGraph (Fin n)) [DecidableRel G.Adj] : OnlineMatchingPolicy n := fun H U e => decide (e.toFinset ⊆ U ∧ bellman_value G (insert e H) U ≤ 1 + bellman_value G (insert e H) (U \ e.toFinset))