Proof of Lemma 20, p. 47 — at a fixed point, u_i((i:j); x_−i) = t_i on the support and ≤ t_i off it
ProvedFixpNash.DivFree.fixedPoint_purePayofffixed-pointgame-theorynash-equilibriump2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1
Consider a finite game in which every player has a nonempty set of pure strategies, and let be a mixed profile with , that is, for all . Then for every player and every :
This is the first half of the proof of Lemma 20: at a fixed point, all strategies in a player's support earn the same payoff and no strategy earns more, which makes a Nash equilibrium.
Formalization Note. is the threshold of the definition file, the unique root of . Every strategy set is assumed nonempty, the paper's tacit assumption.
Preamble
import Mathlib import Definitions.Def_agt_games import Definitions.Def_DGPNash_NashMap_nashMap import Definitions.Def_FixpNash_DivFree_Map
Formal statement
namespace FixpNash.DivFree
/-- Proof of Lemma 20, p. 47: at a fixed point `x ∈ Δ` of `G_I`,
`uᵢ((i:j); x₋ᵢ) = tᵢ` whenever `xᵢⱼ > 0` and `uᵢ((i:j); x₋ᵢ) ≤ tᵢ` whenever `xᵢⱼ = 0`. -/
theorem fixedPoint_purePayoff {ι : Type*} [Fintype ι] [DecidableEq ι]
{S : ι → Type*} [∀ i, Fintype (S i)] [∀ i, DecidableEq (S i)]
(u : ι → (∀ i, S i) → ℝ)
(hS : ∀ i, Nonempty (S i)) (x : ∀ i, S i → ℝ)
(hx : AGT.IsMixedProfile x) (hfix : G u x = x) :
∀ (i : ι) (j : S i),
(0 < x i j → DGPNash.NashMap.purePayoff u x i j = threshold u x i) ∧
(x i j = 0 → DGPNash.NashMap.purePayoff u x i j ≤ threshold u x i) := by sorry
end FixpNash.DivFree
Source
Etessami & Yannakakis, On the complexity of Nash equilibria and other fixed points, author manuscript (SIAM J. Comput. 39 (2010)), Section 4, proof of Lemma 20, p. 47
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.