TL;DR
This paper introduces the first formalization of proof-based Open Source Game Theory (OSGT) in Lean 4, providing a rigorous framework where agents can "read" each other's source code to decide whether to cooperate. The authors also developed an LLM-powered agentic pipeline that autonomously translates natural-language strategies into machine-checked proofs, successfully solving 88.9% of the strategic interactions in their library and uncovering cooperative Nash equilibria that are mathematically impossible in standard game theory.
What Problem Does This Paper Address?
In classical game theory, players are "black boxes"—you know their possible actions and payoffs, but you can't see their internal reasoning. This leads to the famous Prisoner’s Dilemma, where two rational players both defect, even though they would both be better off cooperating.
Open Source Game Theory (OSGT) changes the rules: players can inspect each other’s source code before acting. This allows for "conditional cooperation" (e.g., "I will cooperate only if I can prove you will too"). While theoretically powerful, OSGT is notoriously difficult to analyze because it involves self-referential logic and "provability holes." Until now, there was no mechanized framework to verify these strategies, making it hard to apply OSGT to real-world multi-agent AI systems where transparency is possible.
Methods
The authors tackled this by building a three-part system:
- Lean 4 Formalization: They created a library called
PrisonersDilemmathat defines a domain-specific language for programs (Prog) and logical formulas (Formula). Crucially, they axiomatized a bounded proof search oracle. This allows a program to "ask" the system: "Is there a proof of length $k$ that my opponent will cooperate?" - Agentic Pipeline: They built a "retrieve-propose-check" loop using LLMs (specifically Claude 4.7).
- Bot Writer: Converts a natural language description (e.g., "Cooperate unless you can prove the opponent defects") into Lean code.
- Proof Writer: Attempts to prove the outcome of a matchup between two bots. It iterates based on compiler feedback from the Lean kernel until the proof is verified.
- Equilibrium Analysis: Using the verified outcomes, they used a tool called
lrsnashto calculate the Nash equilibria of the "meta-game"—the game where the "moves" are actually the programs themselves.
Datasets
The paper introduces a new benchmark library of nine open-source bots (the "bot-pair matrix"). These bots range from simple constants (Always Cooperate) to complex, provability-conditioned agents like DupocBot ("Defect Unless Proof of Cooperation").
- The evaluation was performed on the 45 unique pairings of these bots.
- The library serves as a ground-truth dataset for future work in formalizing strategic interactions.
Key Insights and Ideas
- The "Labels Swap" Paradox: In OSGT, a bot that looks cooperative (defaults to C) can actually be less stable than one that looks aggressive (defaults to D). For example,
CupodBot(Cooperate unless proof of defection) actually leads to mutual defection in self-play, whileDupocBot(Defect unless proof of cooperation) achieves mutual cooperation. - PBLT is the Engine: The Parametric Bounded Löb Theorem (PBLT) is the mathematical "magic" that allows two bots to cooperate. It proves that if a bot cooperates because it finds a proof that its opponent cooperates, and the opponent does the same, they can both find those proofs simultaneously without falling into an infinite loop.
- LLMs as Formal Reasoners: The study found that LLMs are highly effective at formalizing game theory when they have access to a "check" (the Lean kernel) and a "retrieve" (few-shot examples from the library) mechanism.
Key Results
- High Automation Success: The agentic pipeline autonomously proved 40 out of 45 (88.9%) outcome theorems.
- Cooperation is Rational: In the standard Prisoner's Dilemma, the only Nash equilibrium is mutual defection. In the OSGT meta-game, the authors found 16 extreme Nash equilibria, including "full-cooperation" components where players achieve the maximum possible joint payoff.
- The Necessity of DupocBot: The analysis revealed that
DupocBotis the "unique element" necessary for full mutual cooperation to emerge as a rational phenomenon in this library. Without it, the cooperative equilibria vanish.
Limitations and Future Work
- Token Budget Constraints: The five failed proofs were all "Tier-2" (complex) bots where the LLM ran out of output tokens before finishing the long, chain-linked proofs required by the axioms.
- The "MirrorBot" Problem: Some bots (like
MirrorBot) create infinite recursion when played against themselves (simulating a simulator simulating a simulator...). The current evaluator handles this by returning "no outcome," but more robust handling of non-termination is needed. - Human in the Loop: While the proof generation was autonomous, the initial translation from natural language to Lean code still requires a human "gatekeeper" to ensure the bot's code actually matches the intended strategy. The authors suggest a "reviewer agent" as a future improvement.
Summary updated