Proof of Proposition 3, p. 21 — Σ_j x_{i,j} g_{i,j}(x) = 0
ProvedFixpNash.WeakApprox.sum_mul_gain_eq_zerogame-theorynash-equilibriump2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be a finite game and a mixed profile. For every player , the gains average to zero under :
Splitting the sum by the sign of , with and where , gives , the identity on which the second direction of the proof of Proposition 3 is built.
Formalization Note The page writes the sum as ; it runs over all of . is a mixed profile in the sense of agt_games.
Preamble
import Mathlib import Definitions.Def_agt_games import Definitions.Def_FixpNash_WeakApprox_NashFunction
Formal statement
namespace FixpNash.WeakApprox
/-- Proof of Proposition 3, p. 21: for a mixed profile `x` and every player `i`,
`Σ_j x_{i,j} g_{i,j}(x) = 0`. -/
theorem sum_mul_gain_eq_zero {ι : Type*} [Fintype ι] [DecidableEq ι]
{S : ι → Type*} [∀ i, Fintype (S i)] [∀ i, DecidableEq (S i)]
(u : ι → (∀ i, S i) → ℝ) (x : ∀ i, S i → ℝ) (hx : AGT.IsMixedProfile x) (i : ι) :
∑ j : S i, x i j * gain u x i j = 0 := 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)), proof of Proposition 3, second direction, p. 21
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.