Proof of Theorem 3.2, p. 141 — does not depend on the strategy of player
ProvedMondererShapley.Congestion.sub_potential_indepgame-theoryp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1potential-games
Let be a game in strategic form with finitely many players, strategy sets , payoffs , and let be a potential for . Then for every player and every the expression does not depend on :
This invariance makes the function of (B.4) well defined, and it is what lets the proof of Theorem 3.2 split each payoff into the potential plus a term the player cannot influence.
Formalization Note. is Function.update a i x for a full profile .
Preamble
import Mathlib import Definitions.Def_MondererShapley_ClosedPath_IsPotential
Formal statement
namespace MondererShapley.Congestion
/-- Monderer and Shapley (1996), p. 141 (proof of Theorem 3.2): if `P` is a potential for `Γ`, then by
(2.2) the expression `uⁱ(a⁻ⁱ, aⁱ) − P(a⁻ⁱ, aⁱ)` does not depend on `aⁱ ∈ Yⁱ`:
`uⁱ(a⁻ⁱ, aⁱ) − P(a⁻ⁱ, aⁱ) = uⁱ(a⁻ⁱ, bⁱ) − P(a⁻ⁱ, bⁱ)` for every `aⁱ, bⁱ ∈ Yⁱ`. -/
theorem sub_potential_indep {ι : Type*} [Fintype ι] [DecidableEq ι] {Y : ι → Type*}
(u : ι → (∀ i, Y i) → ℝ) (P : (∀ i, Y i) → ℝ) (hP : MondererShapley.ClosedPath.IsPotential u P)
(i : ι) (a : ∀ k, Y k) (x z : Y i) :
u i (Function.update a i x) - P (Function.update a i x) =
u i (Function.update a i z) - P (Function.update a i z) := by sorry
end MondererShapley.Congestion
Source
Monderer and Shapley, Potential Games, Games Econ. Behav. 14 (1996), p. 141 (PDF p. 18), proof of Theorem 3.2, display before (B.4)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.