Proof of Proposition 4, pp.18–19 — every CCWE has for all
ProvedCorrWardrop.ccwe_integral_lealgorithmic-game-theorycorrelated-equilibriump2o-gran-per-chapterp2o-plan-paperp2o-v1potential-games
Let be a nonatomic game with a convex potential (as in Lemma 3), and let be a coarse correlated Wardrop equilibrium of . Then for every flow profile ,
The paper argues by contradiction: if for some , integrating the gradient inequality produces a population and an action violating (4.3). Together with (4.11) this shows that every CCWE is a distribution over minimizers of , i.e. over WE.
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: if Φ(z) < ∫Φ dμ for some z ∈ Y, then μ cannot be a CCWE → μ ∈ CCWE Γ → ∀ z ∈ Y, ∫Φ dμ ≤ Φ z; reason: contrapositive of the paragraph's claim; logically equivalent
Preamble
import Mathlib import Definitions.Def_CorrWardrop_Model open MeasureTheory
Formal statement
namespace CorrWardrop
/-- Proof of Proposition 4, first part: with a convex potential `Φ`, every CCWE `μ` satisfies
`∫ Φ(y) dμ(y) ≤ Φ(z)` for every `z ∈ Y` (the page shows that `Φ(z) < ∫ Φ(y) dμ(y)` for some
`z ∈ Y` contradicts (4.3), "so `μ` cannot be a CCWE").
Koessler–Scarsini–Tomala, arXiv:2107.06312v4, proof of Proposition 4, pp.18–19. -/
theorem ccwe_integral_le {K : Type*} [Fintype K] {A : K → Type*} [∀ k, Fintype (A k)]
[DecidableEq K] [∀ k, DecidableEq (A k)]
(Γ : NonatomicGame K A) (Φ : Flow A → ℝ) (hΦ : HasConvexPotential Γ Φ)
(μ : ProbabilityMeasure Γ.Y) (hμ : μ ∈ CCWE Γ) (z : Γ.Y) :
∫ y : Γ.Y, Φ (y : Flow A) ∂(μ : Measure Γ.Y) ≤ Φ z := by sorry
end CorrWardrop
Source
Koessler–Scarsini–Tomala, Correlated Equilibria in Large Anonymous Bayesian Games, arXiv:2107.06312v4, proof of Proposition 4, paragraph "Conversely, take a CCWE µ …", pp.18–19
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.