Proof of Proposition 4, p.20 — all flows in the relative interior of have the common support
ProvedCorrWardrop.relint_common_supportalgorithmic-game-theoryconvex-analysisp2o-gran-per-chapterp2o-plan-paperp2o-v1wardrop-equilibrium
Let be a nonatomic game with a convex potential (as in Lemma 3), and let be the relative interior of the set of Wardrop equilibria in . Then for each population there is a set of actions such that
- every has support for every , i.e. is the support of all flows in the relative interior;
- : whenever for some WE, this holds at every point of the relative interior.
This common support is where the KKT multipliers force equal partial derivatives of at all points of the relative interior.
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: relative interior of WE(Γ); ×_k B^k is the support → intrinsicInterior ℝ of the image of WE(Γ) in the flow space; for every k, {a | 0 < y k a} = B k; reason: Mathlib's relative interior; the support of a flow profile as one set per population
Preamble
import Mathlib import Definitions.Def_CorrWardrop_Model import Definitions.Def_CorrWardrop_Lagrangian open MeasureTheory
Formal statement
namespace CorrWardrop
/-- Proof of Proposition 4, common support of the relative interior: if `Γ` has a convex
potential, then for each `k ∈ K` there is a subset of actions `B^k ⊆ A^k` such that `×_k B^k`
is the support of every flow in the relative interior of `WE(Γ)`; moreover `a ∈ B^k` exactly
when `y^k_a > 0` for some WE `y` ("whenever `y^k_a > 0` for some WE, this must be true for all
points in the relative interior of WE").
Koessler–Scarsini–Tomala, arXiv:2107.06312v4, proof of Proposition 4, p.20. -/
theorem relint_common_support {K : Type*} [Fintype K] {A : K → Type*} [∀ k, Fintype (A k)]
[DecidableEq K] [∀ k, DecidableEq (A k)]
(Γ : NonatomicGame K A) (Φ : Flow A → ℝ) (hΦ : HasConvexPotential Γ Φ) :
∃ B : (k : K) → Set (A k),
(∀ y ∈ relintWE Γ, ∀ k, support y k = B k) ∧
∀ k, B k = {a | ∃ w ∈ WE Γ, 0 < (w : Flow A) k a} := by sorry
end CorrWardrop
Source
Koessler–Scarsini–Tomala, Correlated Equilibria in Large Anonymous Bayesian Games, arXiv:2107.06312v4, proof of Proposition 4, first paragraph of p.20
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.