Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Proposition 3.9, p. 422 — on termination the auction algorithm returns an assignment whose cost is nε suboptimal

Proved
CompOT.Auction.proposition_3_9

by mikedeng1 · Oct 7, 2026 · Mathlib 0df444a (Lean v4.33.1)

assignment-problemauction-algorithmoptimal-transportp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-bookp2o-v1

Let n≥2n\ge2n≥2, C∈Rn×n\mathbf C\in\mathbb R^{n\times n}C∈Rn×n and ε>0\varepsilon>0ε>0. Run the auction algorithm from S=∅S=\emptysetS=∅, g=0n\mathbf g=0_ng=0n​ until it terminates, i.e. until S=[ ⁣[n] ⁣]S=[\![n]\!]S=[[n]], and let ξ\xiξ be the final assignment vector. Then ξ\xiξ is a permutation of [ ⁣[n] ⁣][\![n]\!][[n]], and its cost is within nεn\varepsilonnε of the optimum:

∑iCi,ξi  ≤  ∑iCi,σi+nεfor every permutation σ.\sum_i \mathbf C_{i,\xi_i}\;\le\;\sum_i\mathbf C_{i,\sigma_i}+n\varepsilon\qquad\text{for every permutation }\sigma .i∑​Ci,ξi​​≤i∑​Ci,σi​​+nεfor every permutation σ.

This is the accuracy guarantee of the auction algorithm. In particular, if C\mathbf CC has integer entries and nε<1n\varepsilon<1nε<1, the returned assignment is optimal.

Formalization Note The statement concerns every terminated run: any number TTT of admissible iterations (3.9), with ties resolved arbitrarily, that ends with S=[ ⁣[n] ⁣]S=[\![n]\!]S=[[n]]; it does not assert that the algorithm terminates (that is Proposition 3.8). The cost is the unnormalized sum ∑iCi,σi\sum_i\mathbf C_{i,\sigma_i}∑i​Ci,σi​​, as in the book's proof (t⋆=∑Ci,σit^\star=\sum\mathbf C_{i,\sigma_i}t⋆=∑Ci,σi​​); with the 1n\frac1nn1​ normalization of (2.2) the gap would read ε\varepsilonε. The hypothesis n≥2n\ge2n≥2 is the range where the update (3.9) is defined: it needs a second-best index ji2≠ji1j^2_i\ne j^1_iji2​=ji1​ (for n=1n=1n=1 no iteration exists and the algorithm never terminates). That the final ξ\xiξ is a permutation is part of the conclusion, as the book asserts ("SSS grows to cover [ ⁣[n] ⁣][\![n]\!][[n]] as ξ\xiξ describes a permutation").

Preamble
import Mathlib
import Definitions.Def_CompOT_Auction_Defs
Formal statement
namespace CompOT.Auction

/-- Proposition 3.9, p. 422: the auction algorithm finds an assignment whose cost is `nε`
suboptimal. On termination (`S = ⟦n⟧`) the partial assignment `ξ` is a permutation and
`∑ᵢ C_{i,ξ_i} ≤ ∑ᵢ C_{i,σ_i} + nε` for every permutation `σ`. -/
theorem proposition_3_9 {n : ℕ} (hn : 2 ≤ n) (C : Matrix (Fin n) (Fin n) ℝ) {ε : ℝ}
    (hε : 0 < ε) (s : ℕ → AuctionState n) (T : ℕ) (hs : IsAuctionRun C ε s T) :
    Function.Bijective (s T).ξ ∧
      ∀ σ : Equiv.Perm (Fin n), assignmentCost C (s T).ξ ≤ assignmentCost C σ + n * ε := by sorry

end CompOT.Auction
Source
Peyré & Cuturi, Computational Optimal Transport (FnT ML 2019), Proposition 3.9, p. 422
Human review
  • Endorsed by Shuze Chen · Oct 8, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 8, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me