Proposition 3.9, p. 422 — on termination the auction algorithm returns an assignment whose cost is nε suboptimal
ProvedCompOT.Auction.proposition_3_9Let , and . Run the auction algorithm from , until it terminates, i.e. until , and let be the final assignment vector. Then is a permutation of , and its cost is within of the optimum:
This is the accuracy guarantee of the auction algorithm. In particular, if has integer entries and , the returned assignment is optimal.
Formalization Note The statement concerns every terminated run: any number of admissible iterations (3.9), with ties resolved arbitrarily, that ends with ; it does not assert that the algorithm terminates (that is Proposition 3.8). The cost is the unnormalized sum , as in the book's proof (); with the normalization of (2.2) the gap would read . The hypothesis is the range where the update (3.9) is defined: it needs a second-best index (for no iteration exists and the algorithm never terminates). That the final is a permutation is part of the conclusion, as the book asserts (" grows to cover as describes a permutation").
import Mathlib import Definitions.Def_CompOT_Auction_Defs
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
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.