§3.7, properties (b)–(c), pp. 419–420 — each iteration keeps |S|, lowers one price by ≥ ε and raises none
ProvedCompOT.Auction.properties_b_cassignment-problemauction-algorithmoptimal-transportp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-bookp2o-v1
Let , , and let be the first iterations of the auction algorithm started from , . Then for every iteration :
- (b) the size of does not decrease: ;
- (c) some entry of the dual vector decreases by at least : there is an object with ;
- no entry of the dual vector increases: entrywise.
These are the bookkeeping properties the book reads off the update (3.9); the monotonicity of is the fact "" used in the proof of Proposition 3.7.
Formalization Note The book says the size of "can only increase"; it stays the same when the bidder displaces a previously assigned point, so (b) is stated as non-decrease. The book's (c) speaks of "an index such that decreases"; is indexed by objects, so the index is written . Item 3 is from the proof of Proposition 3.7, p. 421.
Preamble
import Mathlib import Definitions.Def_CompOT_Auction_Defs
Formal statement
namespace CompOT.Auction
/-- Properties (b) and (c), p. 419, "valid after each iteration" (p. 420): along the auction
algorithm, the size of `S` never decreases, some entry of `g` decreases by at least `ε`, and no
entry of `g` increases (`g^n ≤ g`, proof of Proposition 3.7, p. 421). -/
theorem properties_b_c {n : ℕ} (C : Matrix (Fin n) (Fin n) ℝ) {ε : ℝ} (hε : 0 < ε)
(s : ℕ → AuctionState n) (T : ℕ) (hs : IsAuctionPrefix C ε s T) :
∀ t < T, (s t).S.card ≤ (s (t + 1)).S.card ∧
(∃ j, (s (t + 1)).g j ≤ (s t).g j - ε) ∧
∀ j, (s (t + 1)).g j ≤ (s t).g j := by sorry
end CompOT.Auction
Source
Peyré & Cuturi, Computational Optimal Transport (FnT ML 2019), §3.7, properties (b), (c), p. 419, and Algorithmic properties, p. 420; proof of Proposition 3.7, p. 421
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.