Lemma 2.5, proof — transitivity of improvement reachability
ProvedMondererShapley.Improvement.improvesTo_transgame-theoryp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1potential-games
Let have the FIP and write when a finite strict improvement path leads from to a distinct profile . Then this relation is transitive:
This is the intermediate claim stated in the proof of Lemma 2.5. The FIP is essential because a closed strict improvement walk would violate it.
Formalization Note Strategy sets may be infinite here; the paper says only “a game with the FIP” at this point.
Preamble
import Mathlib import Definitions.Def_MondererShapley_Improvement_ImprovesTo import Definitions.Def_MondererShapley_Improvement_HasFIP
Formal statement
namespace MondererShapley.Improvement
variable {ι : Type*} [DecidableEq ι] {Y : ι → Type*}
/-- In the proof of Lemma 2.5 (p. 129), the FIP makes `>` transitive. -/
theorem improvesTo_trans [Fintype ι] (u : ι → (∀ i, Y i) → ℝ)
(hFIP : HasFIP u) (x y z : ∀ i, Y i)
(hxy : ImprovesTo u x y) (hyz : ImprovesTo u y z) :
ImprovesTo u x z := by sorry
end MondererShapley.Improvement
Source
Monderer and Shapley, Potential Games, Games Econ. Behav. 14 (1996), p. 129 (PDF p. 6), Lemma 2.5 proof, “>” is transitive
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.