AFTD Auto-Formalizing Theoretical Domains

policy_value

def

For a simple graph G on vertex set Fin n with decidable adjacency, an online matching policy pol : OnlineMatchingPolicy n, an observed edge set H : Finset (Sym2 (Fin n)), and an unmatched vertex set U : Finset (Fin n), policy_value G pol H U is the expected matching size achieved by pol from state (H, U), defined by recursion on G.edgeFinset.card - H.card: 0 when G.edgeFinset.card - H.card = 0, and otherwise the sum over e : Sym2 (Fin n) with e ∉ H and 0 < compatible_labelings G (insert e H) of edge_arrival_prob G H e multiplied by (if e.toFinset ⊆ U ∧ pol H U e then 1 + policy_value G pol (insert e H) (U \ e.toFinset) else policy_value G pol (insert e H) U).

Statement

noncomputable def policy_value {n : ℕ} (G : SimpleGraph (Fin n)) [DecidableRel G.Adj]
    (pol : OnlineMatchingPolicy n)
    (H : Finset (Sym2 (Fin n))) (U : Finset (Fin n)) : ℝ
Defined in
arXiv:2611.13571, Section 5.1
Verified
12 Nov 2026
Axioms
none listed
Built on 3
  • 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))),…
  • 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…
  • 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 3

Read back from the Lean

policy_value is a noncomputable definition that computes a real number representing the expected value (matching size) of an online matching policy on a graph under a random arrival model. Given: - an implicit natural number n, - a simple graph G on vertex set Fin n with decidable adjacency, - an online matching policy pol : OnlineMatchingPolicy n, - a set H : Finset (Sym2 (Fin n)) of edges revealed so far, and - a set U : Finset (Fin n) of currently unmatched vertices, policy_value G pol H U is defined as aux (G.edgeFinset.card - H.card) H U, where aux is defined by recursion on a step counter $k \in \mathbb{N}$: - aux 0 _ _ = 0 - aux (k + 1) H' U' is the sum over all unordered pairs of vertices $e \in \text{Sym2}(\text{Fin } n)$ of: - if $e \notin H'$ and $0 < \text{compatible\_labelings } G (\text{insert } e\ H')$: $\text{edge\_arrival\_prob } G\ H'\ e$ multiplied by: - $(1 + \text{aux } k (\text{insert } e\ H') (U' \setminus e.\text{toFinset}))$ if both endpoints of $e$ are in $U'$ (i.e., $e.\text{toFinset} \subseteq U'$) and pol H' U' e = true, - $(\text{aux } k (\text{insert } e\ H') U')$ otherwise; - else: $0$.

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

Lean source view module on GitHub

/-- The expected matching size achieved by an online policy from state (H, U). -/
noncomputable def policy_value {n : ℕ} (G : SimpleGraph (Fin n)) [DecidableRel G.Adj]
    (pol : OnlineMatchingPolicy n)
    (H : Finset (Sym2 (Fin n))) (U : Finset (Fin n)) : ℝ :=
  aux (G.edgeFinset.card - H.card) H U
where
  aux : ℕ → Finset (Sym2 (Fin n)) → Finset (Fin n) → ℝ
    | 0, _, _ => 0
    | k + 1, H', U' =>
      ∑ e ∈ (Finset.univ : Finset (Sym2 (Fin n))),
        if e ∉ H' ∧ 0 < compatible_labelings G (insert e H') then
          edge_arrival_prob G H' e *
            (if e.toFinset ⊆ U' ∧ pol H' U' e then
              1 + aux k (insert e H') (U' \ e.toFinset)
            else
              aux k (insert e H') U')
        else 0
See it in the graphDiscuss this resultChallenge it