AFTD Auto-Formalizing Theoretical Domains

agMP

def

Matching pennies as a 2-player, 2-strategy anonymous game: player 0 wants to match the other player, player 1 wants to mismatch.

Statement

def agMP : AGGame 2 2 where
  u p i y
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
none listed
Built on 1
  • AGGameAn anonymous game with n players and s strategies (setting of arXiv 0710.5582, "Computing equilibria in anonymous games", Section 2): the…
Used by 5
  • ag_two_exactExact answer for two strategies. For anonymous games with s = 2 strategies the best possible pure approximation is exactly 2λ = sλ: every…
  • agMP_lipschitzMatching pennies, as an anonymous game, is 1/2-Lipschitz in the l1 norm on count vectors.
  • agMP_u_eqThe rational payoff of matching pennies equals its integer payoff table agMPv.
  • agMP_normalizedMatching pennies, written as a 2-player 2-strategy anonymous game, has payoffs in [0,1].
  • agMP_no_pureNEIn matching pennies every pure profile leaves a player with regret 1 = 2λ.

Lean source view module on GitHub

/-- Matching pennies as a 2-player, 2-strategy anonymous game: player `0` wants to match the other player, player `1` wants to mismatch. -/
def agMP : AGGame 2 2 where
  u p i y := if p = 0 then (if y i = 1 then 1 else 0) else (if y i = 0 then 1 else 0)
See it in the graphDiscuss this resultChallenge it