policy_value
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
- online_matching_policy_value_le_bellmanFor a simple graph G on vertex set Fin n with decidable adjacency, every online matching policy pol : OnlineMatchingPolicy n satisfies…
- 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…
- optimal_online_matching_policy_achieves_valueFor a simple graph G on vertex set Fin n with decidable adjacency, the optimal online matching policy optimal_online_policy G achieves…
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