Proof of Proposition 3, p. 20 — an ε′/(n+1)-NE is a weak ε′-approximate fixed point of Nash's function
ProvedFixpNash.WeakApprox.eps_nash_is_weak_fixed_pointLet be a finite game, let be the maximum number of pure strategies of a player, and let be Nash's function. Let and put . If is an -Nash equilibrium of , then is a weak -approximate fixed point of : is a mixed profile and
This is the first direction of the proof of Proposition 3: an -NE is almost fixed by Nash's function, with a tolerance only a factor larger than .
Formalization Note The proof on p. 20 ends with ". Therefore, is a weak -approximate fixed point", and the weak approximation of p. 16 is strict. The theorem states the page's conclusion, the strict weak approximation (IsWeakApproxFixedPoint); it holds with the printed , since every coordinate of is at most in absolute value. The page's is . is computed from the game (maxNumStrategies); the -NE is the published IsEpsApproxNash, which includes that is a mixed profile.
import Mathlib import Definitions.Def_agt_games import Definitions.Def_DGPNash_NashMap_nashMap import Definitions.Def_DGPNash_WellSupported_Equilibria import Definitions.Def_FixpNash_WeakApprox_NashFunction import Definitions.Def_FixpNash_WeakApprox_GameConstants
namespace FixpNash.WeakApprox
/-- Proof of Proposition 3, first direction (p. 20): with `n` the maximum number of pure
strategies of a player, an `ε'/(n+1)`-NE `x` is a weak `ε'`-approximate fixed point of Nash's
function, i.e. `x ∈ D_Γ` and `|F_Γ(x)_{(i,j)} - x_{i,j}| < ε'` for all `i, j`. -/
theorem eps_nash_is_weak_fixed_point {ι : Type*} [Fintype ι] [DecidableEq ι]
{S : ι → Type*} [∀ i, Fintype (S i)] [∀ i, DecidableEq (S i)]
(u : ι → (∀ i, S i) → ℝ) (ε' : ℝ) (hε' : 0 < ε') (x : ∀ i, S i → ℝ)
(hx : DGPNash.WellSupported.IsEpsApproxNash u x (ε' / ((maxNumStrategies S : ℝ) + 1))) :
IsWeakApproxFixedPoint u x ε' := by sorry
end FixpNash.WeakApprox
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.