p. 11 — a profile is a Nash equilibrium iff no switch to a pure strategy pays
ProvedFixpNash.DivFree.isMixedNash_iff_purePayoff_legame-theorynash-equilibriump2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1
In a finite game, a profile is a Nash equilibrium when it is a mixed strategy profile and, for every player and every mixed strategy of player , . It suffices to check switches to pure strategies only:
Here is player 's expected payoff and the expected payoff when switches to the pure strategy while the others keep .
This is the test used in both directions of the characterization of Nash equilibria as fixed points of .
Formalization Note. Both sides require to be a mixed profile; the paper's "x∗ is a NE iff …" ranges over strategy profiles. The definition of Nash equilibrium is the published AGT.IsMixedNash (deviations to arbitrary lotteries).
Preamble
import Mathlib import Definitions.Def_agt_games import Definitions.Def_DGPNash_NashMap_nashMap import Definitions.Def_FixpNash_DivFree_Map
Formal statement
namespace FixpNash.DivFree
/-- p. 11: a mixed profile is a Nash equilibrium iff no player gains by switching to a
pure strategy: `uᵢ(x) ≥ uᵢ((i:j); x₋ᵢ)` for every player `i` and every `j ∈ Sᵢ`. -/
theorem isMixedNash_iff_purePayoff_le {ι : Type*} [Fintype ι] [DecidableEq ι]
{S : ι → Type*} [∀ i, Fintype (S i)] [∀ i, DecidableEq (S i)]
(u : ι → (∀ i, S i) → ℝ)
(x : ∀ i, S i → ℝ) :
AGT.IsMixedNash u x ↔
AGT.IsMixedProfile x ∧
∀ (i : ι) (j : S i),
DGPNash.NashMap.purePayoff u x i j ≤ AGT.expectedPayoff u x i := by sorry
end FixpNash.DivFree
Source
Etessami & Yannakakis, On the complexity of Nash equilibria and other fixed points, author manuscript (SIAM J. Comput. 39 (2010)), Section 2.2, p. 11
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.