Proof of Theorem 3.2, p. 141 — , so satisfies (B.2)
ProvedMondererShapley.Congestion.eq_B_2congestion-gamesgame-theoryp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1potential-games
Let be a finite game with players , finite strategy sets and a function . On the facility set of the proof of Theorem 3.2, let , let and be as in (B.3), and let if and otherwise. Then for every :
- satisfies (B.2):
where .
In the congestion game built in the proof, (B.2) makes the facilities used by all players carry exactly the potential.
Formalization Note. is identified with (index ↔ strategy ), so is a strategy profile. No potential property of is needed for this step.
Preamble
import Mathlib import Definitions.Def_MondererShapley_Congestion_FacilityConstruction
Formal statement
namespace MondererShapley.Congestion
/-- Monderer and Shapley (1996), p. 141 (proof of Theorem 3.2): on the facility set
`M = ×_{i} {0,1}^{K(i)}`, for every `m ∈ K`,
`A¹_{m₁} ∩ A²_{m₂} ∩ ⋯ ∩ Aⁿ_{mₙ} ∩ M₁ = {ε(m)}`; therefore the vector `xⁿ` satisfies (B.2):
`xⁿ(A¹_{m₁} ∩ ⋯ ∩ Aⁿ_{mₙ}) = P(a¹_{m₁}, …, aⁿ_{mₙ})`.
**Formalization Note.** `K(i)` is identified with `Yⁱ` (`m_i` ↔ `aⁱ_{m_i}`), so `m` is a profile;
`x(B) = Σ_{j∈B} x(j)` is `vecSum`. -/
theorem eq_B_2 {ι : Type*} [Fintype ι] [DecidableEq ι] {Y : ι → Type*} [∀ i, Fintype (Y i)]
[∀ i, DecidableEq (Y i)] (P : (∀ i, Y i) → ℝ) (m : ∀ i, Y i) :
(⋂ i, stratFac i (m i)) ∩ M1 Y = {epsOf m} ∧
vecSum (xn P) (⋂ i, stratFac i (m i)) = P m := by sorry
end MondererShapley.Congestion
Source
Monderer and Shapley, Potential Games, Games Econ. Behav. 14 (1996), pp. 140–141 (PDF pp. 17–18), proof of Theorem 3.2, (B.2), (B.3) and the display at the top of p. 141
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.