AFTD Auto-Formalizing Theoretical Domains

OnlineMatchingPolicy

def

An online matching policy on n vertices is a decision rule that, given the observed edges H, unmatched vertices U, and an arriving edge e, outputs a boolean decision indicating whether to accept e.

Statement

def OnlineMatchingPolicy (n : ℕ) : Type
Defined in
arXiv:2611.13571, Section 5.1
Verified
12 Nov 2026
Axioms
none listed
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…
  • policy_valueFor a simple graph G on vertex set Fin n with decidable adjacency, an online matching policy pol : OnlineMatchingPolicy n, an observed…

Read back from the Lean

For a natural number n, OnlineMatchingPolicy n is defined as the type of functions taking: 1. a finite set of unordered pairs of elements of Fin n (Finset (Sym2 (Fin n))), 2. a finite set of elements of Fin n (Finset (Fin n)), and 3. an unordered pair of elements of Fin n (Sym2 (Fin n)), and producing a boolean (Bool).

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

/-- An online matching policy deciding whether to accept an arriving edge given observed edges and unmatched vertices. -/
def OnlineMatchingPolicy (n : ℕ) : Type :=
  Finset (Sym2 (Fin n)) → Finset (Fin n) → Sym2 (Fin n) → Bool
See it in the graphDiscuss this resultChallenge it