Proof of Proposition 4, p.19 — KKT conditions iff saddle point of the Lagrangian (corrected: Lagrangian includes the −γ^k term)
ProvedCorrWardrop.kkt_iff_saddlealgorithmic-game-theoryconvex-optimizationkkt-conditionsp2o-correctedp2o-gran-per-chapterp2o-plan-paperp2o-v1saddle-point
Let be a nonatomic game and let be a convex potential of on the open convex set (so is continuously differentiable and convex on , and on ). Let
For and multipliers , the pair satisfies the KKT conditions if and only if it is a saddle point of : for all , and
for every and every with for all .
The saddle-point form is what makes the exchange property available: optimal primal solutions and optimal multipliers can be recombined freely.
Differences from the source:
- correction: L(y, λ) = Φ(y) − Σ_k λ^k (Σ_a y^k_a) − Σ_k Σ_a λ_{a,k} y^k_a → L(y, λ) = Φ(y) − Σ_k λ^k (Σ_a y^k_a − γ^k) − Σ_k Σ_a λ^k_a y^k_a; reason: with the printed L no saddle point exists, so "KKT iff saddle" is false: one population, one action, γ = 1, c ≡ 0, Φ ≡ 0; ŷ = 1 with λ̂ = 0 satisfies KKT but L(ŷ, λ) = −λ^1 has no maximum in λ^1
- reading: for all (y, λ) → for all y ∈ U (the open convex domain on which Φ is a convex potential) and all λ with λ^k_a ≥ 0 (λ^k free); also λ̂^k_a ≥ 0; reason: the domain of the Lagrangian in Rockafellar's Theorem 28.3, which the page cites
Preamble
import Mathlib import Definitions.Def_CorrWardrop_Model import Definitions.Def_CorrWardrop_Lagrangian open MeasureTheory
Formal statement
namespace CorrWardrop
/-- Proof of Proposition 4, KKT conditions and saddle points (corrected Lagrangian): let `Φ` be
a convex potential of `Γ` on the open convex neighbourhood `U` of `Y`. For `ŷ ∈ Y` and
multipliers `λ̂`, `(ŷ, λ̂)` satisfies the KKT conditions if and only if
`L(ŷ, λ) ≤ L(ŷ, λ̂) ≤ L(y, λ̂)` for all `y ∈ U` and all `λ` with `λ^k_a ≥ 0` (and `λ̂^k_a ≥ 0`).
Koessler–Scarsini–Tomala, arXiv:2107.06312v4, proof of Proposition 4, p.19 (Rockafellar 1970,
Theorem 28.3).
Formalization Note: `L` is the corrected Lagrangian `lagrangian`, which contains the `−γ^k` of
the equality constraints; with the printed `L` there is no saddle point. -/
theorem kkt_iff_saddle {K : Type*} [Fintype K] {A : K → Type*} [∀ k, Fintype (A k)]
[DecidableEq K] [∀ k, DecidableEq (A k)]
(Γ : NonatomicGame K A) (Φ : Flow A → ℝ) (U : Set (Flow A))
(hΦ : IsConvexPotentialOn Γ Φ U) (y : Γ.Y) (l : Multipliers A) :
KKT Γ Φ y l ↔ IsSaddle Γ Φ U y l := by sorry
end CorrWardrop
Source
Koessler–Scarsini–Tomala, Correlated Equilibria in Large Anonymous Bayesian Games, arXiv:2107.06312v4, proof of Proposition 4, saddle-point display, p.19 (citing Rockafellar 1970, Theorem 28.3)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.