Lemma 20 — the fixed points of G_I are precisely the Nash equilibria
ProvedFixpNash.DivFree.fixedPoint_iff_isMixedNashLet be a finite game in which every player has a nonempty set of pure strategies, let be the set of mixed strategy profiles, and let be the map , where is the unique real number with . For every ,
That is, the fixed points of are precisely the Nash equilibria of the game.
Since is a continuous self-map of the compact convex set , the lemma gives an elementary proof of Nash's theorem through Brouwer's fixed point theorem, and, because needs no division, it shows that the class FIXP is unchanged when division is removed from the circuits (Theorem 22).
Formalization Note. A "fixed point of " is a point of its domain with , hence the hypothesis . Nash equilibrium is the published AGT.IsMixedNash (deviations to arbitrary mixed strategies). Every strategy set is assumed nonempty, the paper's tacit assumption (otherwise is empty and does not exist). Payoffs are real, a generalization of the paper's rational payoffs.
import Mathlib import Definitions.Def_agt_games import Definitions.Def_DGPNash_NashMap_nashMap import Definitions.Def_FixpNash_DivFree_Map
namespace FixpNash.DivFree
/-- Lemma 20, p. 47: the fixed points of `G_I` in its domain `Δ` are precisely the
Nash equilibria of the game. -/
theorem fixedPoint_iff_isMixedNash {ι : Type*} [Fintype ι] [DecidableEq ι]
{S : ι → Type*} [∀ i, Fintype (S i)] [∀ i, DecidableEq (S i)]
(u : ι → (∀ i, S i) → ℝ)
(hS : ∀ i, Nonempty (S i)) (x : ∀ i, S i → ℝ)
(hx : AGT.IsMixedProfile x) :
G u x = x ↔ AGT.IsMixedNash u x := by sorry
end FixpNash.DivFree
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.