(B.6) —
ProvedMondererShapley.Congestion.eq_B_6congestion-gamesgame-theoryp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1potential-games
Let be a finite game with players , finite strategy sets , payoffs , and let be a potential for . On the facility set of the proof of Theorem 3.2, let , , (B.5) and the vector be as defined on pp. 140–141, with of (B.4). Then for every , with , and ,
where and .
Together with (B.2) and Lemma B.1, (B.6) shows that the congestion game built in the proof reproduces the payoffs of .
Formalization Note. Two misprints of the page are corrected: the printed is , the set of the term of Lemma B.1 (the facility lies in and in no , ), and the printed is . is identified with .
Preamble
import Mathlib import Definitions.Def_MondererShapley_ClosedPath_IsPotential import Definitions.Def_MondererShapley_Congestion_FacilityConstruction
Formal statement
namespace MondererShapley.Congestion
/-- Monderer and Shapley (1996), p. 141, (B.6): let `P` be a potential for the finite game `Γ`. For every
`m = (m₁, …, mₙ) ∈ K`, with `A = (A¹_{m₁}, …, Aⁿ_{mₙ})` and `a = (a¹_{m₁}, …, aⁿ_{mₙ})`,
`x¹(Aⁱ_{m_i} ∩ A(−i)^c) = x¹(ε(mⁱ)) = uⁱ(a) − P(a)` for every player `i`, where `mⁱ = (m_k)_{k≠i}` and
`A(−i) = ∪_{k≠i} Aᵏ_{m_k}`.
**Formalization Note.** Two misprints are corrected: the printed `A(−i)` is `A(−i)^c` (the set of
Lemma B.1's `x¹` term; `ε(mⁱ)` lies in `Aⁱ_{m_i}` and in no `Aᵏ_{m_k}`, `k ≠ i`), and the printed
`Pⁱ(a)` is `P(a)`. `K(i)` is identified with `Yⁱ`. -/
theorem eq_B_6 {ι : Type*} [Fintype ι] [DecidableEq ι] {Y : ι → Type*} [∀ i, Fintype (Y i)]
[∀ i, DecidableEq (Y i)] (u : ι → (∀ i, Y i) → ℝ) (P : (∀ i, Y i) → ℝ)
(hP : MondererShapley.ClosedPath.IsPotential u P) (m : ∀ i, Y i) (i : ι) :
vecSum (x1 u P) (stratFac i (m i) ∩ (⋃ k ∈ {k | k ≠ i}, stratFac k (m k))ᶜ) =
x1 u P (epsMinus i m) ∧
x1 u P (epsMinus i m) = u i m - P m := by sorry
end MondererShapley.Congestion
Source
Monderer and Shapley, Potential Games, Games Econ. Behav. 14 (1996), p. 141 (PDF p. 18), (B.6)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.