Proving Your Way to Cooperation: Formalizing Proof-Based Open Source Game Theory in Lean

Colomban Duclaux, Riccardo Formenti, Pepijn Cobben, Bernhard Schölkopf, Zhijing JinAI4Math @ ICML 2026 · OpenReview

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:

  1. Lean 4 Formalization: They created a library called PrisonersDilemma that 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?"
  2. Agentic Pipeline: They built a "retrieve-propose-check" loop using LLMs (specifically Claude 4.7).
  3. Bot Writer: Converts a natural language description (e.g., "Cooperate unless you can prove the opponent defects") into Lean code.
  4. 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.
  5. Equilibrium Analysis: Using the verified outcomes, they used a tool called lrsnash to 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, while DupocBot (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 DupocBot is 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

Abstract

Open Source Game Theory studies strategic interaction between agents with full mutual transparency, and offers a promising route to robust cooperation in multi-agent systems. Its proof-based branch, in which agents condition on bounded proof search over each other's source code, is theoretically rich, but lacks any mechanized framework, limiting both its empirical study and its integration into practical systems. We address this gap with the first Lean 4 formalization of proof-based Open Source Game Theory, comprising nine open-source programs together with manually written, machine-checked proofs of the outcome theorems that govern their pairwise play. On top of this verified library, we build an agentic pipeline that turns natural-language strategy descriptions into Lean-verified outcome theorems. This pipeline autonomously reproves 40 of the 45 outcome theorems in the resulting bot-pair matrix. As a first application, we use the verified outcomes to enumerate the Nash equilibria of the induced Prisoner’s Dilemma program meta-game and find a broad spectrum of cooperative equilibria absent from the underlying game.
BibTeX
@inproceedings{duclaux2026proving,
  author = {Colomban Duclaux and Riccardo Formenti and Pepijn Cobben and Bernhard Schölkopf and Zhijing Jin},
  title = {{Proving Your Way to Cooperation: Formalizing Proof-Based Open Source Game Theory in Lean}},
  booktitle = {AI4Math @ ICML},
  year = {2026},
  url = {https://openreview.net/forum?id=Wc5TAIUC8k},
}
Figure