Proof of Proposition 3, p. 21 — |φ_{i,j} − x_{i,j}Σ_l φ_{i,l}| < ε′(1 + Σ_l φ_{i,l}) < ε²/2cn²
ProvedFixpNash.WeakApprox.coordinatewise_boundLet be a finite game with constants (the maximum number of pure strategies of a player), (the maximum over players of the spread between their largest and smallest pure payoff) and . Let , put
and let be a weak -approximate fixed point of Nash's function: a mixed profile with . Write . Then for every player and every ,
where the sums run over .
This turns the approximate fixed-point condition into a bound on each positive gain relative to the total positive gain of the player; the case analysis that concludes the proof of Proposition 3 starts from it.
Formalization Note Both inequalities of the page's chain are stated, as a conjunction. is the page's "Assume without loss of generality that ". and are computed from the game (maxNumStrategies, cConst); is read as , as the page writes it two lines later.
import Mathlib import Definitions.Def_agt_games import Definitions.Def_FixpNash_WeakApprox_NashFunction import Definitions.Def_FixpNash_WeakApprox_GameConstants
namespace FixpNash.WeakApprox
/-- Proof of Proposition 3, p. 21: with `ε' = ε²/(4c²n³)` and `φ_{i,j} = max{0, g_{i,j}}`, a weak
`ε'`-approximate fixed point satisfies
`|φ_{i,j}(x) - x_{i,j} Σ_l φ_{i,l}(x)| < ε'(1 + Σ_l φ_{i,l}(x)) < ε²/(2cn²)`. -/
theorem coordinatewise_bound {ι : Type*} [Fintype ι] [DecidableEq ι]
{S : ι → Type*} [∀ i, Fintype (S i)] [∀ i, DecidableEq (S i)]
(u : ι → (∀ i, S i) → ℝ) (ε : ℝ) (hε : 0 < ε) (hε1 : ε ≤ 1) (x : ∀ i, S i → ℝ)
(hx : IsWeakApproxFixedPoint u x
(ε ^ 2 / (4 * cConst u ^ 2 * (maxNumStrategies S : ℝ) ^ 3))) :
∀ (i : ι) (j : S i),
|max 0 (gain u x i j) - x i j * ∑ l : S i, max 0 (gain u x i l)| <
ε ^ 2 / (4 * cConst u ^ 2 * (maxNumStrategies S : ℝ) ^ 3) *
(1 + ∑ l : S i, max 0 (gain u x i l)) ∧
ε ^ 2 / (4 * cConst u ^ 2 * (maxNumStrategies S : ℝ) ^ 3) *
(1 + ∑ l : S i, max 0 (gain u x i l)) <
ε ^ 2 / (2 * cConst u * (maxNumStrategies S : ℝ) ^ 2) := by sorry
end FixpNash.WeakApprox
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.