Proof of Proposition 4, p.19 — exchange property of saddle points of the Lagrangian (corrected: Lagrangian includes the −γ^k term)
ProvedCorrWardrop.saddle_exchangeconvex-optimizationp2o-correctedp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1saddle-point
Let be a nonatomic game, a real function on the flow space, a set of flow vectors, and the Lagrangian
If and are saddle points of on , then and are also saddle points.
In the proof of Proposition 4 this is applied to two Wardrop equilibria: the multipliers of one serve for the other, so the partial derivatives , i.e. the costs, coincide wherever the multipliers determine them.
Differences from the source:
- correction: saddle points of the printed L(y, λ) = Φ(y) − Σ_k λ^k (Σ_a y^k_a) − Σ_k Σ_a λ_{a,k} y^k_a → saddle points of the corrected L(y, λ) = Φ(y) − Σ_k λ^k (Σ_a y^k_a − γ^k) − Σ_k Σ_a λ^k_a y^k_a; reason: the printed L has no saddle points (see CorrWardrop.kkt_iff_saddle), which would make the statement vacuous
- generalization: Φ the convex potential of Γ and U its open convex domain → arbitrary Φ and arbitrary set U; reason: the exchange property of saddle points holds for every function on a product of sets; it specializes to the page's case
Preamble
import Mathlib import Definitions.Def_CorrWardrop_Model import Definitions.Def_CorrWardrop_Lagrangian open MeasureTheory
Formal statement
namespace CorrWardrop
/-- Proof of Proposition 4, exchange property of saddle points: if `(ŷ, λ̂)` and `(ȳ, λ̄)` are
saddle points of the Lagrangian on `U × (ℝ^K × ℝ_{≥0}^{⊔A^k})`, then `(ŷ, λ̄)` and `(ȳ, λ̂)`
are also saddle points.
Koessler–Scarsini–Tomala, arXiv:2107.06312v4, proof of Proposition 4, p.19.
Formalization Note: `L` is the corrected Lagrangian `lagrangian` (see `IsSaddle`). The exchange
property holds for any `Φ` and any `U`; no hypothesis on `Φ` is needed. -/
theorem saddle_exchange {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))
(y₁ y₂ : Flow A) (l₁ l₂ : Multipliers A)
(h₁ : IsSaddle Γ Φ U y₁ l₁) (h₂ : IsSaddle Γ Φ U y₂ l₂) :
IsSaddle Γ Φ U 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, "From the exchange property …", p.19
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.