line_min_matching_cost_le
OPT is at most the cost of any perfect matching.
Statement
theorem line_min_matching_cost_le {n : ℕ} (a b : Fin n → ℝ) (σ : Equiv.Perm (Fin n)) :
line_min_matching_cost a b ≤ ∑ i, |a i - b (σ i)|- Source
- sanity lemma for line_min_matching_cost (OP-1158)
- Verified
- 05 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- line_min_matching_costOPT: the minimum, over all permutations sigma of the n items, of the matching cost sum_i |a_i - b_{sigma(i)}|.
- Used by 3
- probabilistic_serial_line_distortion_ge_sharpSharpness half of OP-1158: for every n >= 2 and every real c < n there are n agents and n items at real positions with positive minimum…
- probabilistic_serial_equispaced_distortion_two_agents_attainedFor n = 2 with equispaced items at 0 and 1, agents at 0 and 1/2 with ties broken toward the smaller-index item attain the harmonic…
- probabilistic_serial_line_distortion_le_two_agentsCase n = 2 of OP-1158: for two agents at real positions a_0, a_1 and two items at real positions b_0, b_1, with each agent ranking the…
The proof, explained
The optimal matching cost is defined as the infimum of the matching cost over all permutations of Fin n in the finite universe Finset.univ. Since any particular permutation σ belongs to this universal set, the infimum is at most the cost evaluated at σ.
The minimum matching cost line_min_matching_cost a b is bounded above by the cost of the permutation σ.
By definition, line_min_matching_cost a b is the infimum of the matching cost function over all permutations in the universal finite set Finset.univ. Since the permutation σ trivially belongs to Finset.univ by Finset.mem_univ, Finset.inf'_le implies that the infimum over Finset.univ is at most the value of the cost function evaluated at σ.
uses
Finset.inf'_le,Finset.mem_univFinset.inf'_le _ (Finset.mem_univ σ)
Finset.inf'_le- For any element b in a finite set s, the infimum of a function f over s is at most f(b).
Finset.mem_univ- Every element of a finite type belongs to the universal finite set univ.
Written by a model (gemini-3.8-flash) from the Lean source alone (no goal states were available). Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
theorem line_min_matching_cost_le {n : ℕ} (a b : Fin n → ℝ) (σ : Equiv.Perm (Fin n)) : line_min_matching_cost a b ≤ ∑ i, |a i - b (σ i)| := Finset.inf'_le _ (Finset.mem_univ σ)