p. 24, proof of Lemma 6 — a strategy whose block matches a most probable strategy of i′ earns at least M/3n − maxₛ|μ(s)|
ProvedFixpNash.Blocks.purePayoff_ge_of_matching_prob_maxgame-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 , so in particular has at most strategies), and let be any mixed profile. Let be a strategy of whose block corresponds to a maximum-probability strategy of : for every . Then
Together with the companion upper bound for strategies whose matching strategy has probability , and the choice , this shows that such strategies are strictly worse than for player .
Formalization Note. The paper writes , meaning . is the supremum of over the finite set of pure profiles.
Preamble
import Mathlib import Definitions.Def_agt_games import Definitions.Def_DGPNash_NashMap_nashMap import Definitions.Def_FixpNash_Blocks_Form
Formal statement
namespace FixpNash.Blocks
/-- Proof of Lemma 6, p. 24, second payoff bound: for any mixed profile `x`, if the block
of the strategy `j'` of `i` corresponds to a maximum-probability strategy `β j'` of `i'`,
then the expected payoff of `j'` for player `i` against the rest of `x` is at least
`M/(3n) - max_s |μ(s)|`. -/
theorem purePayoff_ge_of_matching_prob_max {ι : 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.IsMixedProfile x)
(j' : S i) (hj' : ∀ k : S i', x i' k ≤ x i' (β j')) :
M / (3 * (n : ℝ)) - (⨆ s : (∀ k, S k), |μ s|) ≤ DGPNash.NashMap.purePayoff u x i j' := 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.