AFTD Auto-Formalizing Theoretical Domains

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

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
See it in the graphDiscuss this resultChallenge it