Proposition 3.7, p. 420 — the auction algorithm maintains ε-complementary slackness at each iteration
ProvedCompOT.Auction.proposition_3_7assignment-problemauction-algorithmcomplementary-slacknessoptimal-transportp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-bookp2o-v1
Let and , and let be the first iterations of the auction algorithm started from , . Then every state satisfies ε-complementary slackness: for all ,
Together with termination, this invariant is what makes the final assignment -suboptimal (Proposition 3.9).
Formalization Note is Fin n; the iterations are any sequence of admissible updates (3.9), ties in the argmins being resolved arbitrarily.
Preamble
import Mathlib import Definitions.Def_CompOT_Auction_Defs
Formal statement
namespace CompOT.Auction
/-- Proposition 3.7, p. 420: the auction algorithm maintains ε-complementary slackness at each
iteration. -/
theorem proposition_3_7 {n : ℕ} (C : Matrix (Fin n) (Fin n) ℝ) {ε : ℝ} (hε : 0 < ε)
(s : ℕ → AuctionState n) (T : ℕ) (hs : IsAuctionPrefix C ε s T) :
∀ t ≤ T, EpsCS C ε (s t) := by sorry
end CompOT.Auction
Source
Peyré & Cuturi, Computational Optimal Transport (FnT ML 2019), Proposition 3.7, p. 420
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.