optimal_online_matching_policy
For every simple graph G on vertex set Fin n with decidable adjacency, the optimal online matching policy achieves policy_value G (optimal_online_policy G) ∅ Finset.univ = bellman_value G ∅ Finset.univ, and every online matching policy pol : OnlineMatchingPolicy n satisfies policy_value G pol ∅ Finset.univ ≤ bellman_value G ∅ Finset.univ.
Statement
theorem optimal_online_matching_policy {n : ℕ}
(G : SimpleGraph (Fin n)) [DecidableRel G.Adj] :
policy_value G (optimal_online_policy G) ∅ Finset.univ = bellman_value G ∅ Finset.univ ∧
∀ (pol : OnlineMatchingPolicy n),
policy_value G pol ∅ Finset.univ ≤ bellman_value G ∅ Finset.univ- Formalizes
- arXiv:2611.13571: Improved Bounds for Online Matching with Random Edge Arrivals, Lemma 5.1
- Verified
- 13 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 6
- 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…
- 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…
- 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…
- 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…
- 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,…
Read back from the Lean
For any natural number $n$, and for any simple graph $G$ on the vertex set $\mathrm{Fin}(n)$ with decidable adjacency:
1. The expected matching value achieved by the policy optimal_online_policy G, starting with the empty set of observed edges $\emptyset$ and all vertices unmatched ($\mathrm{Finset.univ}$), equals the Bellman value bellman_value G ∅ Finset.univ.
2. For every deterministic online matching policy pol : OnlineMatchingPolicy n, the expected matching value achieved by pol starting from $\emptyset$ and $\mathrm{Finset.univ}$ is less than or equal to bellman_value G ∅ Finset.univ.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
The theorem asserts that the online matching policy optimal_online_policy is optimal: its expected value equals the Bellman value, and every online policy achieves at most this value. The proof splits the conjunction into these two statements and dispatches each as a direct application of a general lemma specialized to the initial state (empty edge history and all vertices available).
The policy value achieved by the optimal online policy from the initial state equals the Bellman value.
Splitting the conjunction into its two components, the first goal asks to show that policy_value G (optimal_online_policy G) ∅ Finset.univ = bellman_value G ∅ Finset.univ. This is an immediate specialization of optimal_online_matching_policy_achieves_value to the initial state where no edges have arrived (the history H is ∅) and all vertices remain unmatched (U is Finset.univ).
uses
optimal_online_matching_policy_achieves_valueconstructor · exact optimal_online_matching_policy_achieves_value G ∅ Finset.univ
Every online matching policy achieves at most the Bellman value from the initial state.
For the second conjunct, let pol be an arbitrary online matching policy. Specializing online_matching_policy_value_le_bellman to pol and the initial state (∅, Finset.univ) directly gives the required upper bound.
uses
online_matching_policy_value_le_bellman· intro pol exact online_matching_policy_value_le_bellman G pol ∅ Finset.univ
optimal_online_matching_policy_achieves_value- For any graph G, edge history H, and remaining vertex set U, the value achieved by optimal_online_policy G equals the Bellman value at (H, U).
online_matching_policy_value_le_bellman- For any graph G, online matching policy pol, edge history H, and remaining vertex set U, the policy value of pol at (H, U) is at most the Bellman value at (H, U).
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
/-- Optimal online matching policy on graphs known up to isomorphism (Lemma 5.1). -/theorem optimal_online_matching_policy {n : ℕ} (G : SimpleGraph (Fin n)) [DecidableRel G.Adj] : policy_value G (optimal_online_policy G) ∅ Finset.univ = bellman_value G ∅ Finset.univ ∧ ∀ (pol : OnlineMatchingPolicy n), policy_value G pol ∅ Finset.univ ≤ bellman_value G ∅ Finset.univ := by constructor · exact optimal_online_matching_policy_achieves_value G ∅ Finset.univ · intro pol exact online_matching_policy_value_le_bellman G pol ∅ Finset.univ