Lemma 5.4 — changing only the nonstrategic component can make every payoff zero at every pure Nash equilibrium
ProvedHarmonicGames.Pareto.lemma_5_4game-theoryharmonic-gamesnash-equilibriump2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be a finite game with players , nonempty finite strategy sets and utilities . Then there exists a game with utilities such that
- the potential and harmonic components of are identical to those of :
- in all players get zero payoff at all strategy profiles that are pure Nash equilibria of : for every and every pure Nash equilibrium of .
The lemma is the normalisation step of Section 5.3: it shows that the payoff levels at equilibria are fixed by the nonstrategic component alone, which Theorem 5.9 then exploits.
Formalization Note Pure Nash equilibrium of is AGT.IsPureNash (payoff E u), condition (1) of the paper. The components are the maps of Theorem 4.1, with pseudoinverses taken for the unweighted inner product on games. If has no pure Nash equilibrium, condition 2 is vacuous and works; this agrees with the paper.
Preamble
import Mathlib import Definitions.Def_agt_games import Definitions.Def_HarmonicGames_Pareto_Games
Formal statement
namespace HarmonicGames.Pareto
/-- **Lemma 5.4** (p. 31). For every game `u` there is a game `û` with (i) the same potential
and harmonic components as `u` and (ii) `û^m(p) = 0` for every player `m` at every strategy
profile `p` that is a pure Nash equilibrium of `u`. -/
theorem lemma_5_4 {ι : Type} [Fintype ι] [DecidableEq ι] (E : ι → Type)
[∀ m, Fintype (E m)] [∀ m, DecidableEq (E m)] [∀ m, Nonempty (E m)]
(u : HarmonicGames.Decomposition.Games E) :
∃ û : HarmonicGames.Decomposition.Games E, HarmonicGames.Decomposition.potentialComponent E û = HarmonicGames.Decomposition.potentialComponent E u ∧
HarmonicGames.Decomposition.harmonicComponent E û = HarmonicGames.Decomposition.harmonicComponent E u ∧
∀ p : ∀ m, E m, AGT.IsPureNash (HarmonicGames.GenericPure.payoff E u) p → ∀ m, HarmonicGames.GenericPure.payoff E û m p = 0 := by sorry
end HarmonicGames.Pareto
Source
Candogan, Menache, Ozdaglar, Parrilo, Flows and Decompositions of Games: Harmonic and Potential Games, arXiv:1005.2405v2, p. 31, Lemma 5.4
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.