Lemma 6, part 1 (p. 24) — in every Nash equilibrium all blocks of player i have the same total probability
ProvedFixpNash.Blocks.lemma_6_part_1game-theorymatching-penniesnash-equilibriump2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1
Let players of a finite game form a block matching-pennies pair (block map , first term , constant , parameter ), and let be a mixed Nash equilibrium. Then all blocks of player have the same total probability:
Since the blocks partition and there are of them, each block then has probability . Part 2 of Lemma 6 is derived from this statement.
Preamble
import Mathlib import Definitions.Def_agt_games import Definitions.Def_FixpNash_Blocks_Form
Formal statement
namespace FixpNash.Blocks
/-- Lemma 6, part 1 (p. 24): in every Nash equilibrium `x`, all blocks of player `i` have
the same total probability. -/
theorem lemma_6_part_1 {ι : Type*} [Fintype ι] [DecidableEq ι]
{S : ι → Type*} [∀ k, Fintype (S k)] [∀ k, DecidableEq (S k)]
(u : ι → (∀ k, S k) → ℝ) (i i' : ι) (β : S i → S i')
(μ : (∀ k, S k) → ℝ) (M : ℝ) (n : ℕ) (hG : IsBlockPair u i i' β μ M n)
(x : ∀ k, S k → ℝ) (hx : AGT.IsMixedNash u x) :
∀ k k' : S i', blockProb β x k = blockProb β x k' := by sorry
end FixpNash.Blocks
Source
Etessami & Yannakakis, On the complexity of Nash equilibria and other fixed points, author manuscript (SIAM J. Comput. 39 (2010)), Lemma 6, part 1, and the end of its proof, p. 24
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.