Lemma 6 (p. 24) — block matching pennies: equal block probabilities and full support for i′ in every Nash equilibrium
ProvedFixpNash.Blocks.lemma_6Let be a finite game with a pair of players such that the pure strategies of are partitioned into blocks, the blocks are in one-to-one correspondence with the pure strategies of (via a surjective map sending a strategy to the strategy of that its block corresponds to), and the payoffs of have the form
where does not depend on , , and has at most strategies. Then every mixed Nash equilibrium of has the following properties.
- The total probability allocated to the strategies in each block of player is the same for all the blocks: for all .
- All strategies of player have nonzero probability: for all .
In the reduction of Section 3 of Etessami and Yannakakis (Step 2 of the proof of Theorem 4), which encodes the gates of an arithmetic circuit into a game, this lemma is what forces every unprimed player to divide its probability evenly among its blocks, so that the probabilities inside a block can encode the value of a circuit gate.
Formalization Note. The game is the agt_games vocabulary (finite players and strategy types, real payoffs, AGT.IsMixedNash with deviations to arbitrary mixed strategies). The hypothesis "the payoffs of are of the form given above" is the predicate FixpNash.Blocks.IsBlockPair; it includes the bound " has at most strategies", which the paper's proof uses ("since has at most strategies", p. 24), and the condition that does not depend on , which the proof does not use. "Nonzero probability" is stated as , equivalent to for a probability vector.
import Mathlib import Definitions.Def_agt_games import Definitions.Def_FixpNash_Blocks_Form
namespace FixpNash.Blocks
/-- Lemma 6 (Etessami–Yannakakis, p. 24): if the players `i, i'` of a finite game form a
block matching-pennies pair of the form given on pp. 23–24, then every Nash equilibrium
`x` satisfies
1. the total probability allocated to the strategies in each block of player `i` is the
same for all the blocks;
2. all strategies of player `i'` have nonzero probability. -/
theorem lemma_6 {ι : 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') ∧ (∀ k : S i', x i' k ≠ 0) := by sorry
end FixpNash.Blocks
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.