Proof of Proposition 4, pp.18–19 — on
ProvedCorrWardrop.grad_ineqalgorithmic-game-theoryconvex-analysisp2o-gran-per-chapterp2o-plan-paperp2o-v1potential-games
Let be a nonatomic game with a convex potential (as in Lemma 3). For all flow profiles ,
The inequality is the first-order characterization of convexity; the equality expresses the gradient of the potential through the costs. Integrated against a coarse correlated equilibrium, this inequality is what links (4.3) to the expected potential.
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: Φ(z) − Φ(y) ≥ ∇Φ(y)(z − y) (p.18) and ∇Φ(y)(z − y) = Σ_k Σ_a (z^k_a − y^k_a) c^k_a(y) (p.19) → one inequality Σ_k Σ_a (z k a − y k a) · c k a y ≤ Φ z − Φ y for y, z ∈ Y; reason: the two displays are used together in the proof, with y and z in Y, where ∂Φ = c
Preamble
import Mathlib import Definitions.Def_CorrWardrop_Model open MeasureTheory
Formal statement
namespace CorrWardrop
/-- Proof of Proposition 4, the gradient inequality: with a convex potential `Φ`, for all flow
profiles `y, z ∈ Y`,
`Φ(z) − Φ(y) ≥ ∇Φ(y)(z − y) = ∑_{k ∈ K} ∑_{a ∈ A^k} (z^k_a − y^k_a) c^k_a(y)`.
Koessler–Scarsini–Tomala, arXiv:2107.06312v4, proof of Proposition 4, pp.18–19.
Formalization Note: the identity `∇Φ(y)(z − y) = ∑ (z^k_a − y^k_a) c^k_a(y)` (p.19) and the
first-order convexity inequality (p.18) are combined into one inequality, stated for
`y, z ∈ Y`, where the partial derivatives of `Φ` are the costs. -/
theorem grad_ineq {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 z : Γ.Y) :
∑ k, ∑ a, ((z : Flow A) k a - (y : Flow A) k a) * Γ.c k a y ≤ Φ z - Φ y := by sorry
end CorrWardrop
Source
Koessler–Scarsini–Tomala, Correlated Equilibria in Large Anonymous Bayesian Games, arXiv:2107.06312v4, proof of Proposition 4, "Φ(z) − Φ(y) ≥ ∇Φ(y)(z − y)", p.18, and the display "∇Φ(y)(z − y) = Σ_k Σ_a (z^k_a − y^k_a) c^k_a(y)", p.19
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.