AFTD Auto-Formalizing Theoretical Domains

agMP_no_pureNE

theoremverified

In matching pennies every pure profile leaves a player with regret 1 = 2λ.

Statement

theorem agMP_no_pureNE (ε : ℚ) (hε : ε < 2 * (1 / 2)) (σ : Fin 2 → Fin 2) :
    ¬ agMP.PureNE ε σ
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 6
  • agCntNumber of players other than p using strategy j in the pure profile σ.
  • AGGame.PureNEThe pure profile σ is an ε-approximate pure Nash equilibrium.
  • agMPMatching pennies as a 2-player, 2-strategy anonymous game: player 0 wants to match the other player, player 1 wants to mismatch.
  • agMPvInteger form of the matching-pennies payoffs.
  • agMP_u_eqThe rational payoff of matching pennies equals its integer payoff table agMPv.
  • agMP_checkFinite check: in matching pennies, every pure profile ![a, b] leaves some player with regret at least 1.
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

/-- In matching pennies every pure profile leaves a player with regret `1 = 2λ`. -/theorem agMP_no_pureNE (ε : ℚ) (hε : ε < 2 * (1 / 2)) (σ : Fin 2 → Fin 2) :    ¬ agMP.PureNE ε σ := by  intro h  have hσ : σ = ![σ 0, σ 1] := by    funext q; fin_cases q <;> rfl  obtain ⟨p, j, hpj⟩ := agMP_check (σ 0) (σ 1)  rw [← hσ] at hpj  have := h p j  rw [agMP_u_eq, agMP_u_eq] at this  have hq : ((agMPv p (σ p) (agCnt σ p) + 1 : ℕ) : ℚ) ≤ (agMPv p j (agCnt σ p) : ℚ) := by    exact_mod_cast hpj  push_cast at hq  linarith
See it in the graphDiscuss this resultChallenge it