Lemma 4.1 —
ProvedHarmonicGames.Decomposition.lemma_4_1game-theoryharmonic-gameslinear-algebrap2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1potential-games
For a finite game with players and nonempty finite strategy sets , let be the gradient along -comparable pairs of profiles, the Laplacian of the graph of -comparable profiles, and (adjoint and Moore–Penrose pseudoinverse for the inner products (7)).
Lemma 4.1. With the number of strategies of player ,
The Laplacian of each player's comparison graph is thus a multiple of the orthogonal projection onto ; this is what makes the pseudoinverses in the decomposition explicit.
Formalization Note is Fintype.card (E m); adjoints and pseudoinverses are for the -weighted inner product on edge flows and the standard one on .
Preamble
import Mathlib import Definitions.Def_HarmonicGames_Decomposition_Pinv import Definitions.Def_HarmonicGames_Decomposition_Flows import Definitions.Def_HarmonicGames_Decomposition_Games
Formal statement
namespace HarmonicGames.Decomposition
theorem lemma_4_1 (ι : Type) [Fintype ι] [DecidableEq ι] (E : ι → Type) [∀ m, Fintype (E m)]
[∀ m, DecidableEq (E m)] [∀ m, Nonempty (E m)] (m : ι) :
Delta0m E m = (Fintype.card (E m) : ℝ) • Pim E m := by sorry
end HarmonicGames.Decomposition
Source
Candogan, Menache, Ozdaglar, Parrilo, Flows and Decompositions of Games: Harmonic and Potential Games, arXiv:1005.2405v2, p. 15, Lemma 4.1
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.