online_matching_policy_value_le_bellman
For a simple graph G on vertex set Fin n with decidable adjacency, every online matching policy pol : OnlineMatchingPolicy n satisfies policy_value G pol H U ≤ bellman_value G H U for all H : Finset (Sym2 (Fin n)) and U : Finset (Fin n).
Statement
theorem online_matching_policy_value_le_bellman {n : ℕ}
(G : SimpleGraph (Fin n)) [DecidableRel G.Adj]
(pol : OnlineMatchingPolicy n)
(H : Finset (Sym2 (Fin n))) (U : Finset (Fin n)) :
policy_value G pol 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…
- 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))),…
- 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 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 every natural number $n$, every simple graph $G$ on vertices $\mathrm{Fin}\; n$ with decidable adjacency, every online matching policy $\mathrm{pol} : \mathrm{Finset}\;(\mathrm{Sym2}\;(\mathrm{Fin}\; n)) \to \mathrm{Finset}\;(\mathrm{Fin}\; n) \to \mathrm{Sym2}\;(\mathrm{Fin}\; n) \to \mathrm{Bool}$, every finset $H$ of unordered pairs of vertices (representing the set of already-revealed edges), and every finset $U$ of vertices (representing the set of currently unmatched vertices): the expected reward obtained by policy $\mathrm{pol}$ starting from state $(H, U)$, denoted $\mathrm{policy\_value}\; G\; \mathrm{pol}\; H\; U$, is less than or equal to the optimal Bellman value starting from state $(H, U)$, denoted $\mathrm{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 remaining time horizon k in the auxiliary functions for the policy value and the Bellman value. At horizon 0 both values are zero, and for the inductive step each value expands into an expectation over edge arrivals with non-negative transition probabilities. On each arriving edge, any decision made by the online matching policy—either accepting the edge (if unmatched) or skipping it—achieves at most the maximum of the two choices, which is precisely the Bellman choice. Instantiating this induction with the total number of unrevealed edges |E(G)| - |H| yields the theorem.
The number of compatible labelings is antitone with respect to edge set inclusion: if H₁ ⊆ H₂, then compatible_labelings G H₂ ≤ compatible_labelings G H₁.
Unfolding compatible_labelings reduces the claim to showing that the set of vertex permutations under which H₂ is contained in the edge set of π(G) is a subset of those for which H₁ is contained in π(G). For any permutation π compatible with H₂, transitivity of subset inclusion yields H₁ ⊆ H₂ ⊆ π(G), so π is also compatible with H₁. By monotonicity of finset cardinality under inclusion, the count for H₂ is at most the count for H₁.
uses
Finset.card_le_card,Finset.mem_filter,Finset.mem_univ,true_and,subset_transunfold compatible_labelings apply Finset.card_le_card intro π hπ simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hπ ⊢ exact subset_trans hsub hπ
If an edge history H has strictly positive compatible labelings, then |H| ≤ |E(G)|.
Since the count of compatible labelings is strictly positive, there exists at least one permutation π such that H ⊆ π(G). Taking cardinalities gives |H| ≤ |E(π(G))|. Because π is a permutation of the vertex set, it induces an injection on unordered pairs of vertices, preserving the edge set cardinality: |E(π(G))| = |E(G)|. Therefore, |H| ≤ |E(G)|.
uses
Finset.card_pos,Finset.mem_filter,Finset.mem_univ,true_and,Finset.card_le_card,SimpleGraph.edgeFinset_card,SimpleGraph.edgeSet_map,Set.card_image_of_injective,Sym2.map.injectiveunfold compatible_labelings at h rw [Finset.card_pos] at h obtain ⟨π, hπ⟩ := h simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hπ calc H.card ≤ (G.map π.toEmbedding).edgeFinset.card := Finset.card_le_card hπ _ = G.edgeFinset.card := by rw [SimpleGraph.edgeFinset_card, SimpleGraph.edgeFinset_card] simp only [SimpleGraph.edgeSet_map] exact Set.card_image_of_injective _ (Sym2.map.injective π.toEmbedding.injective)
If H ∪ {e} admits at least one compatible labeling, then |H| ≤ |E(G)| and H also admits at least one compatible labeling.
Since H ⊆ H ∪ {e} and H ∪ {e} has positive compatible labelings, the previous lemma ensures |H ∪ {e}| ≤ |E(G)|, which implies |H| ≤ |E(G)| by transitivity. Furthermore, antitonicity of compatible labelings gives 0 < compatible_labelings G (H ∪ {e}) ≤ compatible_labelings G H.
uses
le_trans,Finset.card_le_card,Finset.subset_insert,online_matching_policy_value_le_bellman_card_le_of_compat_pos,lt_of_lt_of_le,online_matching_policy_value_le_bellman_compatible_labelings_antihave hcard : H.card ≤ G.edgeFinset.card := le_trans (Finset.card_le_card (Finset.subset_insert e H)) (online_matching_policy_value_le_bellman_card_le_of_compat_pos G h) have hcompH : 0 < compatible_labelings G H := lt_of_lt_of_le h (online_matching_policy_value_le_bellman_compatible_labelings_anti G (Finset.subset_insert e H))
For any edge e such that H ∪ {e} has at least one compatible labeling, the edge arrival probability edge_arrival_prob G H e is non-negative.
Unfolding the definition of edge_arrival_prob, if the denominator is zero, the probability is defined to be 0, which is non-negative. Otherwise, the probability is given by a fraction whose numerator is a cast natural number (hence non-negative) and whose denominator is the product of (|E(G)| - |H|) ≥ 0 and compatible_labelings G H ≥ 0. Since the denominator is non-negative and non-zero, it is strictly positive, making the quotient non-negative.
uses
le_refl,div_nonneg,Nat.cast_nonneg,le_of_lt,lt_of_le_of_ne,Ne.symm,mul_nonneg,sub_nonneg.mprunfold edge_arrival_prob split_ifs with hden · exact le_refl 0 · apply div_nonneg · exact Nat.cast_nonneg _ · apply le_of_lt apply lt_of_le_of_ne _ (Ne.symm hden) apply mul_nonneg · exact sub_nonneg.mpr (by exact_mod_cast hcard) · exact Nat.cast_nonneg _
Base case k = 0: for all states (H, U), policy_value.aux G pol 0 H U ≤ bellman_value.aux G 0 H U.
By definition of the auxiliary functions, both policy_value.aux and bellman_value.aux evaluate to 0 when the remaining horizon k is 0, so the inequality 0 ≤ 0 holds reflexively.
uses
policy_value.aux.eq_1,bellman_value.aux.eq_1induction k with | zero => intro H U rw [policy_value.aux.eq_1, bellman_value.aux.eq_1]
Inductive step: if policy_value.aux G pol k H' U' ≤ bellman_value.aux G k H' U' holds for all states, then it also holds for horizon k + 1.
Unfolding the recursive definitions at k + 1 expresses both values as sums over all possible edges e of the edge arrival probability times the post-arrival continuation value. By monotonicity of summation, it suffices to compare the summands term by term. If the edge has already arrived or has zero compatible labelings, both summands are 0. When the edge can arrive, its arrival probability is non-negative, so we compare the continuation values. If e has an endpoint already matched (not in U), neither policy can match e and both transition to (H ∪ {e}, U), satisfying the inequality by the induction hypothesis. If both endpoints are in U, the policy either accepts e (getting 1 + policy_value.aux) or rejects it (getting policy_value.aux). In either case, the policy's outcome is bounded by the corresponding Bellman continuation value via the induction hypothesis, which is in turn at most the maximum of the two choices taken by the Bellman equation.
uses
policy_value.aux.eq_2,bellman_value.aux.eq_2,Finset.sum_le_sum,if_pos,mul_le_mul_of_nonneg_left,online_matching_policy_value_le_bellman_edge_arrival_prob_nonneg,le_trans,le_max_right,if_neg,le_max_left| succ k ih => intro H U rw [policy_value.aux.eq_2, bellman_value.aux.eq_2] apply Finset.sum_le_sum intro e _ by_cases hguard : e ∉ H ∧ 0 < compatible_labelings G (insert e H) · rw [if_pos hguard, if_pos hguard] apply mul_le_mul_of_nonneg_left _ (online_matching_policy_value_le_bellman_edge_arrival_prob_nonneg G H e hguard.2) by_cases hsub : e.toFinset ⊆ U · rw [if_pos hsub] by_cases hpol : pol H U e = true · rw [if_pos ⟨hsub, hpol⟩] apply le_trans _ (le_max_right _ _) linarith [ih (insert e H) (U \ e.toFinset)] · rw [if_neg (fun hc => hpol hc.2)] exact le_trans (ih (insert e H) U) (le_max_left _ _) · rw [if_neg hsub, if_neg (fun hc => hsub hc.1)] exact ih (insert e H) U · rw [if_neg hguard, if_neg hguard]Every online policy achieves at most the Bellman value: policy_value G pol H U ≤ bellman_value G H U.
By definition, policy_value and bellman_value are their auxiliary functions evaluated at horizon k = |E(G)| - |H|, the number of unseen edges. Rewriting by these definitions and applying the auxiliary lemma with this horizon completes the proof.
uses
policy_value.eq_1,bellman_value.eq_1,online_matching_policy_value_le_bellman_auxrw [policy_value.eq_1, bellman_value.eq_1] exact online_matching_policy_value_le_bellman_aux G pol (G.edgeFinset.card - H.card) H U
Finset.card_le_card- The cardinality of a subset of a finite set is at most the cardinality of the superset.
Finset.mem_filter- An element is in a filtered finset if and only if it belongs to the set and satisfies the predicate.
Finset.mem_univ- Every element of a finite type belongs to the universal finset.
true_and- The conjunction of True with any proposition p is equivalent to p.
subset_trans- The subset relation is transitive.
Finset.card_pos- A finset has strictly positive cardinality if and only if it is nonempty.
SimpleGraph.edgeFinset_card- The cardinality of the edge finset of a simple graph equals the cardinality of its edge set.
SimpleGraph.edgeSet_map- The edge set of a graph mapped by a vertex embedding is the image of the original edge set under the induced map on unordered pairs.
Set.card_image_of_injective- The image of a finite set under an injective function has the same cardinality as the original set.
Sym2.map.injective- If a vertex map is injective, its induced map on unordered pairs of vertices is also injective.
le_trans- The less-than-or-equal relation is transitive.
Finset.subset_insert- Any finset is a subset of the finset obtained by inserting an element into it.
online_matching_policy_value_le_bellman_card_le_of_compat_pos- If an edge history H has at least one compatible labeling in G, its cardinality cannot exceed the total number of edges in G.
lt_of_lt_of_le- If a < b and b ≤ c, then a < c.
online_matching_policy_value_le_bellman_compatible_labelings_anti- The number of compatible labelings is antitone with respect to inclusion of edge histories.
le_refl- Every element in a preorder is less than or equal to itself.
div_nonneg- The quotient of two non-negative numbers is non-negative.
Nat.cast_nonneg- The coercion of any natural number into an ordered semiring is non-negative.
le_of_lt- A strict inequality implies a non-strict inequality.
lt_of_le_of_ne- If a ≤ b and a ≠ b, then a < b.
Ne.symm- The inequality relation is symmetric (a ≠ b implies b ≠ a).
mul_nonneg- The product of two non-negative numbers is non-negative.
sub_nonneg.mpr- If b ≤ a, then 0 ≤ a - b.
policy_value.aux.eq_1- With horizon 0, the auxiliary policy value is 0.
bellman_value.aux.eq_1- With horizon 0, the auxiliary Bellman value is 0.
policy_value.aux.eq_2- The auxiliary policy value with horizon k + 1 equals the expected value over the next edge arrival.
bellman_value.aux.eq_2- The auxiliary Bellman value with horizon k + 1 equals the expected maximum value over the next edge arrival.
Finset.sum_le_sum- If f(i) ≤ g(i) for every element i in a finset, then the sum of f over the finset is at most the sum of g.
if_pos- An if-then-else expression evaluates to its 'then' branch when the condition holds.
mul_le_mul_of_nonneg_left- Multiplying both sides of an inequality by a non-negative number preserves the inequality.
online_matching_policy_value_le_bellman_edge_arrival_prob_nonneg- The edge arrival probability is non-negative whenever adding the edge preserves at least one compatible labeling.
le_max_right- For any elements a and b in a linear order, b ≤ max a b.
if_neg- An if-then-else expression evaluates to its 'else' branch when the condition is false.
le_max_left- For any elements a and b in a linear order, a ≤ max a b.
policy_value.eq_1- The policy value from state (H, U) is defined as the auxiliary policy value with horizon |E(G)| - |H|.
bellman_value.eq_1- The Bellman value from state (H, U) is defined as the auxiliary Bellman value with horizon |E(G)| - |H|.
online_matching_policy_value_le_bellman_aux- For every remaining horizon k and state (H, U), the auxiliary policy value is bounded by the auxiliary Bellman value.
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.
set_option maxHeartbeats 800000 inlemma online_matching_policy_value_le_bellman_compatible_labelings_anti {n : ℕ} (G : SimpleGraph (Fin n)) [DecidableRel G.Adj] {H1 H2 : Finset (Sym2 (Fin n))} (hsub : H1 ⊆ H2) : compatible_labelings G H2 ≤ compatible_labelings G H1 := by unfold compatible_labelings apply Finset.card_le_card intro π hπ simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hπ ⊢ exact subset_trans hsub hπlemma online_matching_policy_value_le_bellman_card_le_of_compat_pos {n : ℕ} (G : SimpleGraph (Fin n)) [DecidableRel G.Adj] {H : Finset (Sym2 (Fin n))} (h : 0 < compatible_labelings G H) : H.card ≤ G.edgeFinset.card := by unfold compatible_labelings at h rw [Finset.card_pos] at h obtain ⟨π, hπ⟩ := h simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hπ calc H.card ≤ (G.map π.toEmbedding).edgeFinset.card := Finset.card_le_card hπ _ = G.edgeFinset.card := by rw [SimpleGraph.edgeFinset_card, SimpleGraph.edgeFinset_card] simp only [SimpleGraph.edgeSet_map] exact Set.card_image_of_injective _ (Sym2.map.injective π.toEmbedding.injective)lemma online_matching_policy_value_le_bellman_edge_arrival_prob_nonneg {n : ℕ} (G : SimpleGraph (Fin n)) [DecidableRel G.Adj] (H : Finset (Sym2 (Fin n))) (e : Sym2 (Fin n)) (h : 0 < compatible_labelings G (insert e H)) : 0 ≤ edge_arrival_prob G H e := by have hcard : H.card ≤ G.edgeFinset.card := le_trans (Finset.card_le_card (Finset.subset_insert e H)) (online_matching_policy_value_le_bellman_card_le_of_compat_pos G h) have hcompH : 0 < compatible_labelings G H := lt_of_lt_of_le h (online_matching_policy_value_le_bellman_compatible_labelings_anti G (Finset.subset_insert e H)) unfold edge_arrival_prob split_ifs with hden · exact le_refl 0 · apply div_nonneg · exact Nat.cast_nonneg _ · apply le_of_lt apply lt_of_le_of_ne _ (Ne.symm hden) apply mul_nonneg · exact sub_nonneg.mpr (by exact_mod_cast hcard) · exact Nat.cast_nonneg _set_option maxHeartbeats 800000 inlemma online_matching_policy_value_le_bellman_aux {n : ℕ} (G : SimpleGraph (Fin n)) [DecidableRel G.Adj] (pol : OnlineMatchingPolicy n) (k : ℕ) : ∀ (H : Finset (Sym2 (Fin n))) (U : Finset (Fin n)), policy_value.aux G pol k H U ≤ bellman_value.aux G k H U := by induction k with | zero => intro H U rw [policy_value.aux.eq_1, bellman_value.aux.eq_1] | succ k ih => intro H U rw [policy_value.aux.eq_2, bellman_value.aux.eq_2] apply Finset.sum_le_sum intro e _ by_cases hguard : e ∉ H ∧ 0 < compatible_labelings G (insert e H) · rw [if_pos hguard, if_pos hguard] apply mul_le_mul_of_nonneg_left _ (online_matching_policy_value_le_bellman_edge_arrival_prob_nonneg G H e hguard.2) by_cases hsub : e.toFinset ⊆ U · rw [if_pos hsub] by_cases hpol : pol H U e = true · rw [if_pos ⟨hsub, hpol⟩] apply le_trans _ (le_max_right _ _) linarith [ih (insert e H) (U \ e.toFinset)] · rw [if_neg (fun hc => hpol hc.2)] exact le_trans (ih (insert e H) U) (le_max_left _ _) · rw [if_neg hsub, if_neg (fun hc => hsub hc.1)] exact ih (insert e H) U · rw [if_neg hguard, if_neg hguard]/-- Every online policy achieves at most the Bellman value from every state. -/theorem online_matching_policy_value_le_bellman {n : ℕ} (G : SimpleGraph (Fin n)) [DecidableRel G.Adj] (pol : OnlineMatchingPolicy n) (H : Finset (Sym2 (Fin n))) (U : Finset (Fin n)) : policy_value G pol H U ≤ bellman_value G H U := by rw [policy_value.eq_1, bellman_value.eq_1] exact online_matching_policy_value_le_bellman_aux G pol (G.edgeFinset.card - H.card) H U