AFTD Auto-Formalizing Theoretical Domains

optimal_online_policy

def

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

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