Proof of Proposition 4, p.19 — minimizes iff KKT multipliers exist
ProvedCorrWardrop.kkt_iffalgorithmic-game-theoryconvex-optimizationkkt-conditionsp2o-gran-per-chapterp2o-plan-paperp2o-v1potential-games
Let be a nonatomic game with a convex potential (as in Lemma 3). For a flow profile , the following are equivalent:
- is a solution of ;
- there exist multipliers such that for all and
This is the KKT theorem for the convex program whose solutions are, by Lemma 3, the Wardrop equilibria. Through condition 2, the gradient of at a WE is pinned down by the multipliers, which is how the proof shows that all WE have the same costs.
Differences from the source:
- reading: "has a convex potential" (Definition 5: Φ C¹ on an open neighbourhood Ŷ of Y) → HasConvexPotential Γ Φ, i.e. Φ C¹ and convex on some open convex U ⊇ Y with ∂Φ/∂y^k_a = c^k_a on Y; reason: literal reading of "Φ convex" on its domain; any open neighbourhood of the compact convex Y contains an open convex one
- reading: ŷ is a solution iff there exists λ̂ with (ŷ, λ̂) satisfying the KKT conditions (the printed list omits ŷ ≥ 0) → for ŷ ∈ Y (so ŷ ≥ 0), (∀ z ∈ Y, Φ ŷ ≤ Φ z) ↔ ∃ λ̂, KKT Γ Φ ŷ λ̂; reason: "ŷ is a solution" presupposes feasibility; without ŷ ≥ 0 the "if" direction is false (one population, A = {a, b}, γ = 1, Φ(y) = (y_a + y_b)², ŷ = (2, −1), λ̂^k = 2, λ̂_a = λ̂_b = 0 satisfies the printed list)
Preamble
import Mathlib import Definitions.Def_CorrWardrop_Model import Definitions.Def_CorrWardrop_Lagrangian open MeasureTheory
Formal statement
namespace CorrWardrop
/-- Proof of Proposition 4, KKT theorem: with a convex potential `Φ`, a flow profile `ŷ ∈ Y` is a
solution of `min {Φ(y) : y ∈ Y}` if and only if there exist multipliers `λ̂` such that
`(ŷ, λ̂)` satisfies the KKT conditions.
Koessler–Scarsini–Tomala, arXiv:2107.06312v4, proof of Proposition 4, KKT conditions, p.19.
Formalization Note: `ŷ` ranges over `Y`, so primal feasibility `ŷ ≥ 0` is assumed ("`ŷ` is a
solution" presupposes it); the printed KKT list does not contain it. -/
theorem kkt_iff {K : Type*} [Fintype K] {A : K → Type*} [∀ k, Fintype (A k)]
[DecidableEq K] [∀ k, DecidableEq (A k)]
(Γ : NonatomicGame K A) (Φ : Flow A → ℝ) (hΦ : HasConvexPotential Γ Φ) (y : Γ.Y) :
(∀ z : Γ.Y, Φ y ≤ Φ z) ↔ ∃ l : Multipliers A, KKT Γ Φ y l := by sorry
end CorrWardrop
Source
Koessler–Scarsini–Tomala, Correlated Equilibria in Large Anonymous Bayesian Games, arXiv:2107.06312v4, proof of Proposition 4, KKT conditions, p.19
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.