Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 3.2 — every finite potential game is isomorphic to a congestion game

Proved
MondererShapley.Congestion.theorem_3_2

by mikedeng1 · Oct 6, 2026 · Mathlib 0df444a (Lean v4.33.1)

congestion-gamesgame-theoryp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1potential-games

Let Γ\GammaΓ be a finite potential game: finitely many players NNN, finite strategy sets YiY^iYi, payoff functions ui:Y→Ru^i : Y \to \mathbb{R}ui:Y→R, and an exact potential PPP for Γ\GammaΓ. Then there are a finite facility set M={1,…,m}M = \{1, \dots, m\}M={1,…,m} and a congestion model C(N,M,(Σi)i∈N,(cj)j∈M)C(N, M, (\Sigma^i)_{i\in N}, (c_j)_{j\in M})C(N,M,(Σi)i∈N​,(cj​)j∈M​) in which every strategy Ai∈ΣiA^i \in \Sigma^iAi∈Σi is a nonempty set of facilities, such that Γ\GammaΓ is isomorphic to the associated congestion game: there are bijections gi:Yi→Σig^i : Y^i \to \Sigma^igi:Yi→Σi with

ui(y1,…,yn)=vi(g1(y1),…,gn(yn))for every i∈N and every (y1,…,yn)∈Y,u^i(y^1, \dots, y^n) = v^i\big(g^1(y^1), \dots, g^n(y^n)\big) \qquad \text{for every } i \in N \text{ and every } (y^1, \dots, y^n) \in Y,ui(y1,…,yn)=vi(g1(y1),…,gn(yn))for every i∈N and every (y1,…,yn)∈Y,

where vi(A)=∑j∈Aicj(σj(A))v^i(A) = \sum_{j\in A^i} c_j(\sigma_j(A))vi(A)=∑j∈Ai​cj​(σj​(A)) 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 mmm (the paper's M={1,…,m}M = \{1,\dots,m\}M={1,…,m}). The congestion model is the published CongestionPoA.AsymSum.CongestionGame, whose latency j k is the paper's cj(k)c_j(k)cj​(k) (an arbitrary real number; values at k=0k = 0k=0 and k>nk > nk>n 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.

Preamble
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
Formal statement
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
Source
Monderer and Shapley, Potential Games, Games Econ. Behav. 14 (1996), p. 133 (PDF p. 10), Theorem 3.2; proof in Appendix B, pp. 140–141
Human review
  • Endorsed by Shuze Chen · Oct 6, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 6, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me