Proposition 3 — ε-NE and weak approximate fixed points of Nash's function, with the explicit ε′ of the proof
ProvedFixpNash.WeakApprox.proposition_3Let be a finite game in normal form in which every player has at least one pure strategy. Let be the maximum number of pure strategies of a player, the maximum, over all players , of the difference between the maximum and the minimum payoff of player under any pure strategy profile, and . Let be Nash's function. Then:
- for every , every -Nash equilibrium of is a weak -approximate fixed point of , i.e.
- for every with , every weak -approximate fixed point of with
(a mixed profile with ) is an -Nash equilibrium of .
The paper states Proposition 3 as a complexity statement: "Computing an -NE (for a given game, , and given ) is P-time equivalent to computing a weak -approximate fixed point of Nash's function (for a given instance of Nash's function, , and given )." Its proof establishes the two implications above, with the explicit tolerances and , 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 -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 is a weak -approximate fixed point (strict, as defined on p. 16); the computation on p. 20 prints the looser bound "", but the strict bound holds with the same . Part 2 assumes , as the page does "without loss of generality" (an -NE for is an -NE for every larger ). , , are computed from the game. Payoffs are real rather than rational. The -NE is the published IsEpsApproxNash.
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
/-- 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
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.