Lemma 5.1 — at a pure Nash equilibrium of a harmonic game every player is indifferent among all strategies
ProvedHarmonicGames.GenericPure.lemma_5_1game-theoryharmonic-gamesnash-equilibriump2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be a finite game with nonempty strategy sets, and suppose is a harmonic game, i.e. its utility collection lies in . Let be a pure Nash equilibrium of : for every player and every . Then
So at a pure equilibrium of a harmonic game, every player is indifferent between all of their strategies. This is the key step in showing that harmonic games generically have no pure Nash equilibrium.
Formalization Note Pure Nash equilibrium is AGT.IsPureNash from the published agt_games bundle, which is condition (1) of the paper. is Function.update p m q.
Preamble
import Mathlib import Definitions.Def_agt_games import Definitions.Def_HarmonicGames_GenericPure_Games
Formal statement
namespace HarmonicGames.GenericPure
/-- **Lemma 5.1** (p. 23). Let `u` be a harmonic game (`u ∈ H ⊕ N`) and `p` a pure Nash
equilibrium of `u`. Then every player is indifferent between all of their strategies at `p`:
`u^m(p^m, p^{-m}) = u^m(q^m, p^{-m})` for all `m` and `q^m ∈ E^m`. -/
theorem lemma_5_1 {ι : Type} [Fintype ι] [DecidableEq ι] (E : ι → Type)
[∀ m, Fintype (E m)] [∀ m, DecidableEq (E m)] [∀ m, Nonempty (E m)]
(u : HarmonicGames.Decomposition.Games E) (hu : IsHarmonicGame E u) (p : ∀ m, E m)
(hp : AGT.IsPureNash (payoff E u) p) :
∀ (m : ι) (q : E m), payoff E u m p = payoff E u m (Function.update p m q) := by sorry
end HarmonicGames.GenericPure
Source
Candogan, Menache, Ozdaglar, Parrilo, Flows and Decompositions of Games: Harmonic and Potential Games, arXiv:1005.2405v2, p. 23, Lemma 5.1, equation (32)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.