AFTD Auto-Formalizing Theoretical Domains

optimal_online_matching_policy_achieves_value

theoremverified

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.

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

    lines 1–6

    uses Finset.card_insert_of_notMem

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

    lines 8–15

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

    lines 16–19

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

    lines 20–22

    uses if_pos

        by_cases he : e ∉ H ∧ 0 < compatible_labelings G (insert e H)
        · rw [if_pos he, if_pos he]
          congr 1
  5. 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.

    lines 23–35

    uses optimal_online_matching_policy_achieves_value_card_sub_insert

          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]
  6. 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}}$.

    lines 36–43

    uses true_and, le_of_lt, not_le.mp, false_and, if_false

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

    line 44

    uses if_neg

        · rw [if_neg he, if_neg he]
  8. 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.

    lines 47–53

    uses optimal_online_matching_policy_achieves_value_aux

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

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

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