agMP_lipschitz
theoremverified
Matching pennies, as an anonymous game, is 1/2-Lipschitz in the l1 norm on count vectors.
Statement
open Finset in theorem agMP_lipschitz : agMP.Lipschitz (1 / 2)
- Source
- step towards ag_two_exact / ag_three_lower / ag_four_lower (Computing Equilibria in Anonymous Games, FOCS 2007 (arXiv:0710.5582), concluding conjecture that s*lambda is a lower bound)
- Verified
- 06 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- AGGame.Lipschitzλ-Lipschitz utilities: |u(x) − u(y)| ≤ λ ‖x − y‖₁ for all partitions x, y of the other n − 1 players.
- agMPMatching pennies as a 2-player, 2-strategy anonymous game: player 0 wants to match the other player, player 1 wants to mismatch.
- Used by 1
- ag_two_exactExact answer for two strategies. For anonymous games with s = 2 strategies the best possible pure approximation is exactly 2λ = sλ: every…
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
open Finset intheorem agMP_lipschitz : agMP.Lipschitz (1 / 2) := by intro p i x y hx hy simp only [Fin.sum_univ_two] at hx hy have hx' : (x 0 = 1 ∧ x 1 = 0) ∨ (x 0 = 0 ∧ x 1 = 1) := by omega have hy' : (y 0 = 1 ∧ y 1 = 0) ∨ (y 0 = 0 ∧ y 1 = 1) := by omega simp only [Fin.sum_univ_two, agMP] fin_cases p <;> fin_cases i <;> rcases hx' with ⟨a1, a2⟩ | ⟨a1, a2⟩ <;> rcases hy' with ⟨b1, b2⟩ | ⟨b1, b2⟩ <;> simp [a1, a2, b1, b2] <;> norm_num