Theorem 3.2 — every finite potential game is isomorphic to a congestion game
ProvedMondererShapley.Congestion.theorem_3_2Let be a finite potential game: finitely many players , finite strategy sets , payoff functions , and an exact potential for . Then there are a finite facility set and a congestion model in which every strategy is a nonempty set of facilities, such that is isomorphic to the associated congestion game: there are bijections with
where is the congestion payoff (3.1).
Together with Theorem 3.1 (every congestion game is a potential game, a result of Rosenthal), this identifies the finite potential games with the congestion games up to isomorphism.
Formalization Note. The facility set is Fin m for some natural number (the paper's ). The congestion model is the published CongestionPoA.AsymSum.CongestionGame, whose latency j k is the paper's (an arbitrary real number; values at and are never used). The nonemptiness of every strategy, required by the definition of a congestion model on p. 133 but not by the published structure, is a separate conjunct. Since the bijections land on the subtype of G.strategies i, the strategies of each player are distinct facility sets. No nonemptiness of the strategy sets and no lower bound on the number of players is assumed: the theorem holds for one player as well.
import Mathlib import Definitions.Def_CongestionPoA_AsymSum_Model import Definitions.Def_MondererShapley_ClosedPath_IsPotentialGame import Definitions.Def_MondererShapley_Congestion_IsIsomorphic import Definitions.Def_MondererShapley_Congestion_congestionPayoff open CongestionPoA.AsymSum
namespace MondererShapley.Congestion
/-- Monderer and Shapley (1996), p. 133, Theorem 3.2: every finite potential game is isomorphic to a
congestion game. The congestion game has facility set `M = {1, …, m}` (`Fin m`), every strategy of
every player is a nonempty set of facilities, and the bijections `gⁱ` map `Yⁱ` onto the strategy
sets `Σⁱ`. -/
theorem theorem_3_2 {ι : Type*} [Fintype ι] [DecidableEq ι] {Y : ι → Type*} [∀ i, Fintype (Y i)]
(u : ι → (∀ i, Y i) → ℝ) (hu : MondererShapley.ClosedPath.IsPotentialGame u) :
∃ (m : ℕ) (G : CongestionGame ι (Fin m)),
(∀ i, ∀ A ∈ G.strategies i, A.Nonempty) ∧ IsIsomorphic u (congestionPayoff G) := by sorry
end MondererShapley.Congestion
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.