optimal_online_matching_policy_achieves_value
For a simple graph G on vertex set Fin n with decidable adjacency, the optimal online matching policy optimal_online_policy G achieves policy_value G (optimal_online_policy G) H U = bellman_value G H U for all H : Finset (Sym2 (Fin n)) and U : Finset (Fin n).
Statement
theorem optimal_online_matching_policy_achieves_value {n : ℕ}
(G : SimpleGraph (Fin n)) [DecidableRel G.Adj]
(H : Finset (Sym2 (Fin n))) (U : Finset (Fin n)) :
policy_value G (optimal_online_policy G) H U = bellman_value G H U- Source
- arXiv:2611.13571, Lemma 5.1 proof
- Verified
- 13 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 5
- 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…
- edge_arrival_probFor a simple graph G on vertex set Fin n with decidable adjacency, a finite set H : Finset (Sym2 (Fin n)) of observed edges, and an edge e…
- compatible_labelingsFor a simple graph G on vertex set Fin n with decidable adjacency, and a finite set H of observed edges (H : Finset (Sym2 (Fin n))),…
- Used by 1
- 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…
Read back from the Lean
For any natural number $n$, any simple graph $G$ on vertex set Fin n with decidable adjacency, any finite set $H$ of unordered pairs of vertices (representing the history of edges arrived so far), and any finite set $U$ of vertices (representing currently unmatched vertices): the expected value achieved by the policy optimal_online_policy G starting from state $(H, U)$, denoted policy_value G (optimal_online_policy G) H U, equals the Bellman value bellman_value G H U.
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 is proved by induction on the number of remaining unobserved edges $k = |E(G)| - |H|$. In each step, both the policy value and the Bellman value are written as sums over all possible arriving edges of their arrival probability times the resulting expected reward. When an edge arrives, the induction hypothesis applies to the updated history, equating the policy's future values to the Bellman values. The definition of the optimal online policy then guarantees that accepting the edge is chosen precisely when accepting yields at least as much expected reward as rejecting, which matches the maximum operation in the Bellman equation.
Inserting a new element into a finite set decrements the difference $M - |s|$ by 1.
Since $x \notin s$, rewriting with `Finset.card_insert_of_notMem` shows that $|s \cup \{x\}| = |s| + 1$. Linear integer arithmetic (`omega`) then deduces $M - (|s| + 1) = k$ from $M - |s| = k + 1$.
uses
Finset.card_insert_of_notMemlemma optimal_online_matching_policy_achieves_value_card_sub_insert {α : Type*} [DecidableEq α] (s : Finset α) (M : ℕ) (k : ℕ) (x : α) (h_sub : M - s.card = k + 1) (hx : x ∉ s) : M - (insert x s).card = k := by rw [Finset.card_insert_of_notMem hx] omega
In the base case $k = 0$, the auxiliary policy value equals the auxiliary Bellman value.
We proceed by induction on the remaining edge count $k$. When $k = 0$, both `policy_value.aux` and `bellman_value.aux` evaluate to 0 by definition, so the equality holds by reflexivity.
lemma optimal_online_matching_policy_achieves_value_aux {n : ℕ} (G : SimpleGraph (Fin n)) [DecidableRel G.Adj] (k : ℕ) : ∀ (H : Finset (Sym2 (Fin n))) (U : Finset (Fin n)), G.edgeFinset.card - H.card = k → policy_value.aux G (optimal_online_policy G) k H U = bellman_value.aux G k H U := by induction' k with k ih · intro H U _ rfl
In the inductive step $k + 1$, it suffices to equate the expected payoffs for each potential arriving edge $e$.
By definition, both auxiliary functions are sums over all pairs $e \in \text{Sym2}(\text{Fin } n)$ of edge-arrival probabilities multiplied by the resulting expected rewards. Applying `Finset.sum_congr` reduces equality of the sums to equality of their summands for each $e$.
uses
Finset.sum_congr· intro H U hH show (∑ e ∈ (Finset.univ : Finset (Sym2 (Fin n))), _) = (∑ e ∈ (Finset.univ : Finset (Sym2 (Fin n))), _) apply Finset.sum_congr rfl intro e _
For a newly arriving edge with compatible labelings, the arrival probabilities factor out.
When $e \notin H$ and compatible labelings exist for $H \cup \{e\}$, rewriting with `if_pos` simplifies both conditional expressions to their positive branches. Stripping the identical factor $\text{edge\_arrival\_prob}(G, H, e)$ leaves only the expected future rewards to be verified.
uses
if_posby_cases he : e ∉ H ∧ 0 < compatible_labelings G (insert e H) · rw [if_pos he, if_pos he] congr 1
By the induction hypothesis, the expected reward under the policy is expressed in terms of the Bellman values at step $k$.
Because $e \notin H$, the lemma `optimal_online_matching_policy_achieves_value_card_sub_insert` ensures that the new state satisfies $|E(G)| - |H \cup \{e\}| = k$. Applying the induction hypothesis at step $k$ equates the policy value to the Bellman value both when $e$ is accepted (unmatched vertices $U \setminus e$) and when $e$ is rejected (unmatched vertices $U$). Unfolding the definition of `optimal_online_policy` and substituting these equalities reformulates the policy's decision entirely in terms of Bellman values.
uses
optimal_online_matching_policy_achieves_value_card_sub_inserthave hk : G.edgeFinset.card - (insert e H).card = k := optimal_online_matching_policy_achieves_value_card_sub_insert H _ k e hH he.1 have ih1 := ih (insert e H) U hk have ih2 := ih (insert e H) (U \ e.toFinset) hk have h_bv1 : bellman_value G (insert e H) U = bellman_value.aux G k (insert e H) U := by change bellman_value.aux G (G.edgeFinset.card - (insert e H).card) (insert e H) U = _ rw [hk] have h_bv2 : bellman_value G (insert e H) (U \ e.toFinset) = bellman_value.aux G k (insert e H) (U \ e.toFinset) := by change bellman_value.aux G (G.edgeFinset.card - (insert e H).card) (insert e H) (U \ e.toFinset) = _ rw [hk] rw [ih1, ih2] unfold optimal_online_policy rw [h_bv1, h_bv2]
When a valid edge arrives, the policy's accept/reject choice achieves the Bellman value.
We split into cases depending on whether both endpoints of $e$ are available ($e \subseteq U$). When $e \subseteq U$, simplifying with `true_and` leaves a choice between rejecting with reward $V_{\text{reject}}$ and accepting with reward $V_{\text{accept}} = 1 + \text{bellman\_value.aux}(H \cup \{e\}, U \setminus e)$. If $V_{\text{reject}} \le V_{\text{accept}}$, the policy accepts, matching $\max(V_{\text{reject}}, V_{\text{accept}}) = V_{\text{accept}}$. If $V_{\text{reject}} > V_{\text{accept}}$, then by `not_le.mp` and `le_of_lt` we have $V_{\text{accept}} \le V_{\text{reject}}$, so the policy rejects, matching $\max(V_{\text{reject}}, V_{\text{accept}}) = V_{\text{reject}}$. When $e \not\subseteq U$, the policy condition is false via `false_and` and the matching option is disabled via `if_false`, so both sides evaluate to $V_{\text{reject}}$.
uses
true_and,le_of_lt,not_le.mp,false_and,if_falseby_cases hU : e.toFinset ⊆ U · simp only [hU, true_and] by_cases hle : bellman_value.aux G k (insert e H) U ≤ 1 + bellman_value.aux G k (insert e H) (U \ e.toFinset) · simp [hle] · have hle' : 1 + bellman_value.aux G k (insert e H) (U \ e.toFinset) ≤ bellman_value.aux G k (insert e H) U := le_of_lt (not_le.mp hle) simp [hle, hle'] · simp only [hU, false_and, if_false]
When an edge is already observed or incompatible, both summands vanish.
If $e \in H$ or no compatible labelings exist for $H \cup \{e\}$, rewriting with `if_neg` evaluates both conditional branches to 0.
uses
if_neg· rw [if_neg he, if_neg he]The optimal online matching policy achieves the Bellman value from any initial state.
By definition (`change`), the policy value and Bellman value from state $(H, U)$ are their auxiliary functions evaluated at remaining steps $k = |E(G)| - |H|$. Applying the auxiliary theorem `optimal_online_matching_policy_achieves_value_aux` with this choice of $k$ concludes the proof.
uses
optimal_online_matching_policy_achieves_value_auxtheorem optimal_online_matching_policy_achieves_value {n : ℕ} (G : SimpleGraph (Fin n)) [DecidableRel G.Adj] (H : Finset (Sym2 (Fin n))) (U : Finset (Fin n)) : policy_value G (optimal_online_policy G) H U = bellman_value G H U := by change policy_value.aux G (optimal_online_policy G) (G.edgeFinset.card - H.card) H U = bellman_value.aux G (G.edgeFinset.card - H.card) H U exact optimal_online_matching_policy_achieves_value_aux G (G.edgeFinset.card - H.card) H U rfl
Finset.card_insert_of_notMem- Inserting an element not already in a finite set increases its cardinality by 1.
Finset.sum_congr- Two finite sums are equal if their index sets are identical and their summands agree on every element of the index set.
if_pos- If a condition $c$ is true, the conditional expression `if c then t else e` reduces to $t$.
optimal_online_matching_policy_achieves_value_card_sub_insert- If $M - |s| = k + 1$ and $x \notin s$, then $M - |s \cup \{x\}| = k$.
true_and- The proposition $\text{True} \land p$ is logically equivalent to $p$.
le_of_lt- A strict inequality $a < b$ implies the weak inequality $a \le b$.
not_le.mp- If $a \le b$ is false, then $b < a$.
false_and- The proposition $\text{False} \land p$ is logically equivalent to $\text{False}$.
if_false- A conditional expression `if False then t else e` reduces to the alternative branch $e$.
if_neg- If a condition $c$ is false, the conditional expression `if c then t else e` reduces to $e$.
optimal_online_matching_policy_achieves_value_aux- When $k = |E(G)| - |H|$, the auxiliary policy value under the optimal online policy equals the auxiliary Bellman value.
- The induction is carried out on an explicit counter $k = |E(G)| - |H|$ tracking the number of remaining unrevealed edges, rather than by direct well-founded induction on the history set $H$.
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.
lemma optimal_online_matching_policy_achieves_value_card_sub_insert {α : Type*} [DecidableEq α] (s : Finset α) (M : ℕ) (k : ℕ) (x : α) (h_sub : M - s.card = k + 1) (hx : x ∉ s) : M - (insert x s).card = k := by rw [Finset.card_insert_of_notMem hx] omegalemma optimal_online_matching_policy_achieves_value_aux {n : ℕ} (G : SimpleGraph (Fin n)) [DecidableRel G.Adj] (k : ℕ) : ∀ (H : Finset (Sym2 (Fin n))) (U : Finset (Fin n)), G.edgeFinset.card - H.card = k → policy_value.aux G (optimal_online_policy G) k H U = bellman_value.aux G k H U := by induction' k with k ih · intro H U _ rfl · intro H U hH show (∑ e ∈ (Finset.univ : Finset (Sym2 (Fin n))), _) = (∑ e ∈ (Finset.univ : Finset (Sym2 (Fin n))), _) apply Finset.sum_congr rfl intro e _ by_cases he : e ∉ H ∧ 0 < compatible_labelings G (insert e H) · rw [if_pos he, if_pos he] congr 1 have hk : G.edgeFinset.card - (insert e H).card = k := optimal_online_matching_policy_achieves_value_card_sub_insert H _ k e hH he.1 have ih1 := ih (insert e H) U hk have ih2 := ih (insert e H) (U \ e.toFinset) hk have h_bv1 : bellman_value G (insert e H) U = bellman_value.aux G k (insert e H) U := by change bellman_value.aux G (G.edgeFinset.card - (insert e H).card) (insert e H) U = _ rw [hk] have h_bv2 : bellman_value G (insert e H) (U \ e.toFinset) = bellman_value.aux G k (insert e H) (U \ e.toFinset) := by change bellman_value.aux G (G.edgeFinset.card - (insert e H).card) (insert e H) (U \ e.toFinset) = _ rw [hk] rw [ih1, ih2] unfold optimal_online_policy rw [h_bv1, h_bv2] by_cases hU : e.toFinset ⊆ U · simp only [hU, true_and] by_cases hle : bellman_value.aux G k (insert e H) U ≤ 1 + bellman_value.aux G k (insert e H) (U \ e.toFinset) · simp [hle] · have hle' : 1 + bellman_value.aux G k (insert e H) (U \ e.toFinset) ≤ bellman_value.aux G k (insert e H) U := le_of_lt (not_le.mp hle) simp [hle, hle'] · simp only [hU, false_and, if_false] · rw [if_neg he, if_neg he]/-- The optimal online policy achieves the Bellman value from every state. -/theorem optimal_online_matching_policy_achieves_value {n : ℕ} (G : SimpleGraph (Fin n)) [DecidableRel G.Adj] (H : Finset (Sym2 (Fin n))) (U : Finset (Fin n)) : policy_value G (optimal_online_policy G) H U = bellman_value G H U := by change policy_value.aux G (optimal_online_policy G) (G.edgeFinset.card - H.card) H U = bellman_value.aux G (G.edgeFinset.card - H.card) H U exact optimal_online_matching_policy_achieves_value_aux G (G.edgeFinset.card - H.card) H U rfl