AFTD Auto-Formalizing Theoretical Domains

online_matching_policy_value_le_bellman

theoremverified

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.

  1. 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₁.

    lines 6–10

    uses Finset.card_le_card, Finset.mem_filter, Finset.mem_univ, true_and, subset_trans

      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π
  2. 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)|.

    lines 16–24

    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.injective

      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)
  3. 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.

    lines 31–36

    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_anti

      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))
  4. 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.

    lines 37–46

    uses le_refl, div_nonneg, Nat.cast_nonneg, le_of_lt, lt_of_le_of_ne, Ne.symm, mul_nonneg, sub_nonneg.mpr

      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 _
  5. 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.

    lines 54–57

    uses policy_value.aux.eq_1, bellman_value.aux.eq_1

      induction k with
      | zero =>
        intro H U
        rw [policy_value.aux.eq_1, bellman_value.aux.eq_1]
  6. 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.

    lines 58–77

    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]
  7. 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.

    lines 85–87

    uses policy_value.eq_1, bellman_value.eq_1, online_matching_policy_value_le_bellman_aux

      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
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

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
See it in the graphDiscuss this resultChallenge it