AFTD Auto-Formalizing Theoretical Domains

agMP_check

theoremverified

Finite check: in matching pennies, every pure profile ![a, b] leaves some player with regret at least 1.

Statement

theorem agMP_check : ∀ a b : Fin 2, ∃ p j : Fin 2,
    agMPv p (![a, b] p) (agCnt ![a, b] p) + 1 ≤ agMPv p j (agCnt ![a, b] p)
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
  • agCntNumber of players other than p using strategy j in the pure profile σ.
  • agMPvInteger form of the matching-pennies payoffs.
Used by 1
  • agMP_no_pureNEIn matching pennies every pure profile leaves a player with regret 1 = 2λ.

Lean source view module on GitHub

/-- Finite check: in matching pennies, every pure profile `![a, b]` leaves some player with regret at least `1`. -/theorem agMP_check : ∀ a b : Fin 2, ∃ p j : Fin 2,    agMPv p (![a, b] p) (agCnt ![a, b] p) + 1 ≤ agMPv p j (agCnt ![a, b] p) := by  decide
See it in the graphDiscuss this resultChallenge it