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