AFTD Auto-Formalizing Theoretical Domains

line_min_matching_cost

def

OPT: the minimum, over all permutations sigma of the n items, of the matching cost sum_i |a_i - b_{sigma(i)}|.

Statement

noncomputable def line_min_matching_cost {n : ℕ} (a b : Fin n → ℝ) : ℝ
Defined in
arXiv:2611.05777 (Sublinear Metric Distortion for Matching), Sec. 1 and Sec. 6: one-sided matching of n agents to n items with ordinal rankings by distance; the probabilistic serial rule (optimal matching cost)
Verified
05 Nov 2026
Axioms
none listed
Used by 10

Read back from the Lean

For an implicit natural number $n$ and two functions $a, b : \mathrm{Fin}\ n \to \mathbb{R}$, line_min_matching_cost a b is defined as the minimum (infimum over the nonempty finite set of all permutations $\sigma$ of $\mathrm{Fin}\ n$) of the sum $\sum_{i \in \mathrm{Fin}\ n} |a(i) - b(\sigma(i))|$.

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

/-- Minimum cost `min_σ ∑ i, |a i - b (σ i)|` of a perfect matching of agents at `a` to items at `b` on the line. -/
noncomputable def line_min_matching_cost {n : ℕ} (a b : Fin n → ℝ) : ℝ :=
  Finset.univ.inf' Finset.univ_nonempty (fun σ : Equiv.Perm (Fin n) => ∑ i, |a i - b (σ i)|)
See it in the graphDiscuss this resultChallenge it