Program equilibrium and open-source game theory – an annotated bibliography

Compiled by Caspar Oesterheld (oesterheld@cmu.edu). Last updated Nov 17, 2023.
  1. R. Preston McAfee (May 1984): Effective Computability in Economic Decisions. This paper introduces the basic idea of achieving cooperation in (a variant of) the Prisoner's Dilemma in equilibirum by having players submit programs who then get access to each other's source code. McAfee's program works by syntactic comparison, roughly: "if opponent source code is equal to mine, then cooperate; else defect".
  2. J. V. Howard (1988): Cooperation in the Prisoner's Dilemma, Theory and Decision, 24, pages 203–213. Similar to McAfee in terms of what it shows about program equilibrium.
  3. Section 10.4 of Ariel Rubinstein (1998): Modeling Bounded Rationality, MIT Press. The discussion is brief and based on syntactic comparison but already gives the folk theorem (with proof left as a "project" to the reader).
  4. Moshe Tennenholtz (2004): Program equilibrium, Games and Economic Behavior, 49(2), pages 363–373. Formally defines program equilibrium and proves the folk theorem using programs based on syntactic comparison.
  5. Lance Fortnow (2009): Program equilibria and discounted computation time. TARK '09: Proceedings of the 12th Conference on Theoretical Aspects of Rationality and Knowledge, pages 128–133.
  6. Mihaly Barasz, Paul Christiano, Benja Fallenstein, Marcello Herreshoff, Patrick LaVictoire, and Eliezer Yudkowsky (January 2014): Robust Cooperation in the Prisoner"s Dilemma: Program Equilibrium via Provability Logic. This paper studies programs like the following: "If I can prove that you cooperate against me, I cooperate. Else I defect." Contrary to what one might expect, such a program cooperates when paired with a copy of itself. To our knowledge this is the earliest example of a program that achieves cooperation in equilibrium while relying on semantic analysis of the opponent program.
  7. Andrew Critch (2019): A Parametric, Resource-Bounded Generalization of Löb's Theorem, and a Robust Cooperation Criterion for Open-Source Game Theory, Journal of Symbolic Logic 84(4), pages 1368–1381. Subtly but importantly refines Barasz et al.'s approach.
  8. Caspar Oesterheld (2019): Robust program equilibrium, Theory and Decision, 86(1), pages 143–159. Studies programs of the form, "with ε probability cooperate; with the remaining probability simulate the opponent and copy their action".
  9. Andrew Critch, Michael Dennis, Stuart Russell (2022): Cooperative and uncooperative institution designs: Surprises and problems in open-source game theory.
  10. Caspar Oesterheld (2022): A Note on the Compatibility of Different Robust Program Equilibria of the Prisoner's Dilemma.
  11. Caspar Oesterheld, Johannes Treutlein, Roger Grosse, Vincent Conitzer, Jakob Foerster (2022): Similarity-based Cooperative Equilibrium.
  12. Anthony DiGiovanni and Jesse Clifton (2023): Commitment Games with Conditional Information Disclosure. AAAI 2023.
Some further writings, not in the form of papers, incomplete:
  1. Alex Mennen ran an open-source Prisoner's Dilemma tournanment in 2013. [Announcement and description; results]
  2. Caspar Oesterheld (2018): Testing εGroundedFairBot in a Transparent Prisoner's Dilemma Tournament.
  3. Caspar Oesterheld (2023): Results of the CAIF summer school open prompt prisoner's dilemma tournament.
Program equilibrium can be seen as a form of bilateral (more generally multilateral), simultaneous, mutually conditional commitment (which contrasts with, for example, the widely studied Stackelberg games in which one player commits and the other responds). There are various other models of bilateral commitment, some of which avoid some of the interesting questions posed by program games ("how should and can the programs reason about each other, given logical paradoxes, circularities, multplicity of fixed points, etc.?"). Still, they all follow the structure of the figure below.
The game structure underlying program games and other formalisms of bilateral commitment.
Here's a presumably incomplete list:
  1. Logical formulas as a language of commitment. Instead of specifying one's commitment as a computer program, one might specify one's commitment in the form of a logical formula (e.g., in Peano arithmetic). This approach differs relatively little from the computer program-based approach, because some of the most natural formulas to use can also be written as computer programs. Arguably, the provability logic / Löb's theorem-based approaches listed above could be listed here instead. (The current classification mostly follows the papers' framings.) One difference is that some logical formulas allow for ambiguity of outcomes. For example, in logical-formula-based settings, the commitment, "I do whatever you do", may be permissible, whereas it is not permissible in a program-based setting.
  2. Preferences as a language of commitment. Consider a setting in which Alice and Bob hire representatives Charlie and Dan, respectively, to make decision on their behalfs. They incentivize their representative by giving them a utility function (for example, in the form of committing to pay them depending on the outcomes they achieve). Assume further that Charlie can see Bob's incentive contract for Dan, and Dan can see Alice's incentive contract for Charlie. In general it will be in Charlie's interest to consider Dan's incentives. Thus, delegating to utility-maximizing representatives induces a similar bilateral commitment setting as program equilibrium. The main difference is that preferences (utility functions) (rather than computer programs) are used as a language to specify the mutually conditional behavior.
  3. Specifying mutual dependence in action space. A strategy in a program equilibrium setting typically takes an opponent program as input and outputs an action. Instead, some authors have considered cases in which a strategy directly depends on the opponent's actions. A further mechanism (e.g., a fixed point finder) is then needed to resolve this mutual dependence on one another's actions.
  4. Bilateral commitment without a commitment language. The literature on program equilibrium typically conisders a setting in which commitments that condition on other player's commitment are specified in some general-purpose language, e.g., as computer programs or logical formulas. But we could also assume that commitments are simply objects of some set for each players and that a commitment game specifies how to resolve any given combination of choices of these objects. This approach is followed by the following papers:
Acknowledgments: I'd like to thank John Mori for bringing some of the work in the economics literature to my attention (Peters and Szentes 2012 and references therein).