Theorem 2.8: exact potentials and closed paths of length four
ProvedMondererShapley.ClosedPath.theorem_2_8game-theoryp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1potential-games
For a strategic-form game with finitely many players, the following four claims are equivalent:
- admits an exact potential.
- for every finite closed path .
- for every finite simple closed path .
- for every finite simple closed path of length four.
In symbols, the final criterion uses
on every simple closed with . This characterization reduces the global potential property to a local condition on four-corner cycles.
Formalization Note The statement retains all four equivalence clauses. Players form a finite type; their strategy sets are arbitrary. A step changes exactly one coordinate to a different value, a simple closed path repeats no vertex before its terminal return, and its length is its number of steps.
Preamble
import Mathlib import Definitions.Def_MondererShapley_ClosedPath_IsPotentialGame import Definitions.Def_MondererShapley_ClosedPath_FinPath
Formal statement
namespace MondererShapley.ClosedPath
variable {ι : Type*} [DecidableEq ι] {Y : ι → Type*}
/-- The four equivalent conditions of Theorem 2.8, p. 131. -/
theorem theorem_2_8 [Fintype ι] (u : ι → (∀ i, Y i) → ℝ) :
[IsPotentialGame u,
∀ γ : FinPath Y, γ.IsClosed → γ.I u = 0,
∀ γ : FinPath Y, γ.IsSimpleClosed → γ.I u = 0,
∀ γ : FinPath Y, γ.IsSimpleClosed → γ.len = 4 → γ.I u = 0].TFAE := by sorry
end MondererShapley.ClosedPath
Source
Monderer and Shapley, Potential Games, Games Econ. Behav. 14 (1996), p. 131 (PDF p. 8), Theorem 2.8; https://doi.org/10.1006/game.1996.0044
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.