p. 12 — for an ε-NE it is sufficient to check switches to pure strategies
ProvedFixpNash.WeakApprox.isEpsApproxNash_iff_pureLet be a finite game with players , finite pure-strategy sets and real payoffs , let be a real vector indexed by the pairs with , and let be a real number. Recall that is an -Nash equilibrium (-NE) if is a mixed profile and for every player and every mixed strategy of , . Then is an -NE if and only if is a mixed profile and
that is, for all .
The paper states this in parentheses where it defines -NE ("again, it is sufficient to check switches to pure strategies only"). Both directions of Proposition 3 use it: the first to read off from an -NE, the second to conclude an -NE from .
Formalization Note The -NE is the published DGPNash.WellSupported.IsEpsApproxNash and the published DGPNash.NashMap.purePayoff. The statement is made for every real ; the paper uses it for .
import Mathlib import Definitions.Def_agt_games import Definitions.Def_DGPNash_NashMap_nashMap import Definitions.Def_DGPNash_WellSupported_Equilibria
namespace FixpNash.WeakApprox
/-- p. 12: for an ε-NE "it is sufficient to check switches to pure strategies only". -/
theorem isEpsApproxNash_iff_pure {ι : Type*} [Fintype ι] [DecidableEq ι]
{S : ι → Type*} [∀ i, Fintype (S i)] [∀ i, DecidableEq (S i)]
(u : ι → (∀ i, S i) → ℝ) (x : ∀ i, S i → ℝ) (ε : ℝ) :
DGPNash.WellSupported.IsEpsApproxNash 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.WeakApprox
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.