Lemma 2.5 — FIP iff generalized ordinal potential
ProvedMondererShapley.Improvement.lemma_2_5game-theoryp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1potential-games
Let be a finite strategic-form game with payoff functions . The game has the finite improvement property if and only if it admits a generalized ordinal potential:
This characterizes termination of all strict unilateral improvement paths by a real-valued function that rises along every such step.
Formalization Note The player set and each strategy set are finite. The FIP is expressed as the absence of an infinite improvement path; a path step changes exactly one strategy to a different one.
Preamble
import Mathlib import Definitions.Def_MondererShapley_Improvement_HasFIP import Definitions.Def_MondererShapley_Improvement_IsGenOrdinalPotential
Formal statement
namespace MondererShapley.Improvement
variable {ι : Type*} [DecidableEq ι] {Y : ι → Type*}
/-- Lemma 2.5 (p. 129): the FIP characterizes generalized ordinal potentials in finite games. -/
theorem lemma_2_5 [Fintype ι] [∀ i, Fintype (Y i)]
(u : ι → (∀ i, Y i) → ℝ) :
HasFIP u ↔ ∃ P : (∀ i, Y i) → ℝ, IsGenOrdinalPotential u P := by sorry
end MondererShapley.Improvement
Source
Monderer and Shapley, Potential Games, Games Econ. Behav. 14 (1996), p. 129 (PDF p. 6), Lemma 2.5
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.