Lemma 3, p.18 — with a convex potential, the WE are exactly the minimizers of on
ProvedCorrWardrop.lemma_3algorithmic-game-theoryconvex-optimizationp2o-gran-per-chapterp2o-plan-paperp2o-v1potential-gameswardrop-equilibrium
Let be a nonatomic game with flow set , and let be a convex potential of : is continuously differentiable and convex on an open convex set , and for all , and . Then for every ,
That is, the Wardrop equilibria are exactly the minimizers of the potential over the flow set. The paper attributes the result to Sandholm (2001, Proposition 3.1). It turns equilibrium questions into questions about a convex program.
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
- encoding: the set of WE is the set of minimizers of Φ → for every y ∈ Y, IsWE Γ y ↔ ∀ z ∈ Y, Φ y ≤ Φ z; reason: pointwise form of the set equality; minimizers are over Y
Preamble
import Mathlib import Definitions.Def_CorrWardrop_Model open MeasureTheory
Formal statement
namespace CorrWardrop
/-- Lemma 3: if a nonatomic game has a convex potential `Φ`, then the set of WE is the set of
minimizers of `Φ` over `Y`.
Koessler–Scarsini–Tomala, arXiv:2107.06312v4, Lemma 3, p.18. -/
theorem lemma_3 {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) :
IsWE Γ y ↔ ∀ z : Γ.Y, Φ y ≤ Φ z := by sorry
end CorrWardrop
Source
Koessler–Scarsini–Tomala, Correlated Equilibria in Large Anonymous Bayesian Games, arXiv:2107.06312v4, Lemma 3, p.18
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.