Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Proposition 3 — ε-NE and weak approximate fixed points of Nash's function, with the explicit ε′ of the proof

Proved
FixpNash.WeakApprox.proposition_3

by mikedeng1 · Oct 8, 2026 · Mathlib 0df444a (Lean v4.33.1)

fixed-pointnash-equilibriump2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1ppad

Let Γ\GammaΓ be a finite game in normal form in which every player has at least one pure strategy. Let nnn be the maximum number of pure strategies of a player, MMM the maximum, over all players iii, of the difference between the maximum and the minimum payoff of player iii under any pure strategy profile, and c=1+Mc=1+Mc=1+M. Let FΓF_\GammaFΓ​ be Nash's function. Then:

  1. for every ε′>0\varepsilon'>0ε′>0, every ε′/(n+1)\varepsilon'/(n+1)ε′/(n+1)-Nash equilibrium xxx of Γ\GammaΓ is a weak ε′\varepsilon'ε′-approximate fixed point of FΓF_\GammaFΓ​, i.e.
∣FΓ(x)(i,j)−xi,j∣<ε′for all i and j∈Si;|F_\Gamma(x)_{(i,j)}-x_{i,j}|<\varepsilon'\qquad\text{for all } i \text{ and } j\in S_i;∣FΓ​(x)(i,j)​−xi,j​∣<ε′for all i and j∈Si​;
  1. for every ε\varepsilonε with 0<ε≤10<\varepsilon\le10<ε≤1, every weak ε′\varepsilon'ε′-approximate fixed point of FΓF_\GammaFΓ​ with
ε′=ε24c2n3\varepsilon'=\frac{\varepsilon^2}{4c^2n^3}ε′=4c2n3ε2​

(a mixed profile xxx with ∣FΓ(x)−x∣∞<ε′|F_\Gamma(x)-x|_\infty<\varepsilon'∣FΓ​(x)−x∣∞​<ε′) is an ε\varepsilonε-Nash equilibrium of Γ\GammaΓ.

The paper states Proposition 3 as a complexity statement: "Computing an ϵ\epsilonϵ-NE (for a given game, Γ\GammaΓ, and given ϵ>0\epsilon>0ϵ>0) is P-time equivalent to computing a weak ϵ′\epsilon'ϵ′-approximate fixed point of Nash's function (for a given instance of Nash's function, FΓF_\GammaFΓ​, and given ϵ′>0\epsilon'>0ϵ′>0)." Its proof establishes the two implications above, with the explicit tolerances ε′/(n+1)\varepsilon'/(n+1)ε′/(n+1) and ε2/(4c2n3)\varepsilon^2/(4c^2n^3)ε2/(4c2n3), whose encoding sizes are polynomial in those of the game and the tolerance; the P-time equivalence follows from them. Together with the polynomial continuity of Nash's function, the result places the computation of ε\varepsilonε-NE in PPAD.

Formalization Note The "P-time equivalence" is formalized through the two explicit implications of the proof, not as a statement about algorithms. Part 1 concludes, as the page does, that xxx is a weak ϵ′\epsilon'ϵ′-approximate fixed point (strict, as defined on p. 16); the computation on p. 20 prints the looser bound "≤(mi+1)ϵ≤ϵ′\le(m_i+1)\epsilon\le\epsilon'≤(mi​+1)ϵ≤ϵ′", but the strict bound holds with the same ε′/(n+1)\varepsilon'/(n+1)ε′/(n+1). Part 2 assumes ε≤1\varepsilon\le1ε≤1, as the page does "without loss of generality" (an ε\varepsilonε-NE for ε=1\varepsilon=1ε=1 is an ε\varepsilonε-NE for every larger ε\varepsilonε). nnn, MMM, ccc are computed from the game. Payoffs are real rather than rational. The ε\varepsilonε-NE is the published IsEpsApproxNash.

Preamble
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
Formal statement
namespace FixpNash.WeakApprox

/-- Proposition 3 (p. 20) in the explicit form of its proof (pp. 20–21). Let `n` be the maximum
number of pure strategies of a player, `M` the maximum over players of the spread of their pure
payoffs, and `c = 1 + M`.
(A) For every `ε' > 0`, every `ε'/(n+1)`-NE `x` is a weak `ε'`-approximate fixed point of Nash's
function.
(B) For every `0 < ε ≤ 1`, every weak `ε²/(4c²n³)`-approximate fixed point of Nash's function
is an `ε`-NE. -/
theorem proposition_3 {ι : Type*} [Fintype ι] [DecidableEq ι]
    {S : ι → Type*} [∀ i, Fintype (S i)] [∀ i, DecidableEq (S i)]
    (hS : ∀ i, Nonempty (S i)) (u : ι → (∀ i, S i) → ℝ) :
    (∀ ε' : ℝ, 0 < ε' → ∀ x : ∀ i, S i → ℝ,
        DGPNash.WellSupported.IsEpsApproxNash u x (ε' / ((maxNumStrategies S : ℝ) + 1)) →
          IsWeakApproxFixedPoint u x ε') ∧
      (∀ ε : ℝ, 0 < ε → ε ≤ 1 → ∀ x : ∀ i, S i → ℝ,
        IsWeakApproxFixedPoint u x
            (ε ^ 2 / (4 * cConst u ^ 2 * (maxNumStrategies S : ℝ) ^ 3)) →
          DGPNash.WellSupported.IsEpsApproxNash u x ε) := by sorry

end FixpNash.WeakApprox
Source
Etessami & Yannakakis, On the complexity of Nash equilibria and other fixed points, author manuscript (SIAM J. Comput. 39 (2010)), Proposition 3 and its proof, pp. 20–21
Human review
  • Endorsed by Shuze Chen · Oct 8, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 8, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me