a bird's-eye perspective on program equilibria

January 22, 2026

The concept of "program equilibrium" was first introduced by Tenneholtz in 2004, where he notices that the program $$\begin{array}{rl}& \text{IF }{P}_1=P_2,\text{ THEN COOPERATE}\\ & \text{ELSE DEFECT}\end{array}$$

cooperates with itself in the Prisoner's Dilemma, and moreover given a state of two players adopting this program in the Prisoner's Dilemma there is no incentive for either to deviate.

Unfortunately, this result as stated only holds on the basis of syntactic analysis: essentially, given two .txt files each representing a player's program, check line by line that they're equivalent and if so cooperate. (More sophisticated versions of syntactic analysis exist but all suffer from needing to coordinate on a shared language, transmission mechanism, etc.). In an ideal world, you'd replace $\text{IF }{P}_1=P_2$ with a semantic guarantee: verifying effective equivalence via the behavior of programs rather than their apparent structure.

I'm aware of two ways of doing this:

(1) Simulation. Perhaps the most straightforward way to verify the behavior of a program is to run it. The most naive implementation of the simulation-based approach, running $P_2$ with $P_1$ as input, fails if applied symmetrically from a non-halting infinite regress. However, getting around this is possible with relatively low cost (see the $ϵ$-GroundedFairBot proposed by Oesterheld and variations thereof).

(2) Proof search. "If I can prove that you cooperate with me, then I cooperate. Otherwise I defect." Typically you parametrize programs as logical sentences taking the outputs of the other programs in the game as parameters, and use some Lobian-like theorem to prove cooperation. (Interesting is Critch's proof this holds even with access to only bounded provers).

These are not the only methods for robustly achieving $(C,C)$ in a Prisoner's Dilemma: a more classical approach is to introduce some sort of information revelation and make $(C,C)$ a robust equilibrium in this "correlated" setting. However, taking this "open-source" approach to negotiation has the conceptual benefit (at least to me) of highlighting what sorts of programs form robust coalitions given broad instantiation. Interesting to ponder from the perspective of "what sorts of policy structures should I update myself towards."

Recommended: Oesterheld's annotated bibliography.