p. 24, proof of Lemma 6 — if the blocks are unequal, i′ puts probability 0 on the strategies matching maximum-probability blocks
ProvedFixpNash.Blocks.matching_prob_zero_of_max_blockgame-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 ; see the definition item), and let be a mixed Nash equilibrium. Write for the total probability of block . Suppose that the block probabilities are not all equal, and let be a strategy of whose block has maximum total probability:
Then
In the paper's words: if is the set of blocks of maximum probability, the strategies of corresponding to blocks in have probability , because otherwise could improve its expected payoff. This is the first step of the proof of Lemma 6, part 1.
Preamble
import Mathlib import Definitions.Def_agt_games import Definitions.Def_FixpNash_Blocks_Form
Formal statement
namespace FixpNash.Blocks
/-- Proof of Lemma 6, p. 24: if a Nash equilibrium `x` gives unequal total probability to
some blocks of player `i`, then every strategy `k` of `i'` whose block has maximum total
probability gets probability `0` in `x`. -/
theorem matching_prob_zero_of_max_block {ι : 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)
(hunequal : ∃ k₁ k₂ : S i', blockProb β x k₁ ≠ blockProb β x k₂)
(k : S i') (hk : ∀ k' : S i', blockProb β x k' ≤ blockProb β x k) :
x i' k = 0 := 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)), proof of Lemma 6, part 1, p. 24
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.