Proof of Lemma 20, p. 47 — at a Nash equilibrium, t_i = r_i = u_i(x)
ProvedFixpNash.DivFree.threshold_eq_expectedPayofffixed-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 Nash equilibrium. Write for the expected payoff of player in . Then for every player the threshold of the map at equals :
This is the key step of the second half of the proof of Lemma 20: at an equilibrium for all , hence , so is the threshold, and follows.
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 Nash equilibrium `x`, the threshold `tᵢ` equals
player `i`'s expected payoff `rᵢ = uᵢ(x)`. -/
theorem threshold_eq_expectedPayoff {ι : 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 → ℝ)
(hNE : AGT.IsMixedNash u x) :
∀ i : ι, threshold u x i = AGT.expectedPayoff 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.