Program Equilibrium: Trading Code Cooperates More Than Trading People, but Coordination Is Extremely Hard
Program equilibrium lets two parties read each other's source code and achieve cooperation via Löb's theorem; but cooperation depends on nearly identical code or shared randomness, and in reality coordination costs are extremely high.
The video won't play here. Listen to the audio instead:
The argument · tap a timestamp to hear it
Program equilibrium: hand over code first, then play the game
Program equilibrium is a setup in game theory: players do not directly choose to cooperate or defect, but each submits a computer program, and the program acts on their behalf. The key addition is that at runtime a program can read the opponent's source code and decide on that basis whether to cooperate or defect. So you can write a program like ‘if the opponent's program equals myself, cooperate; otherwise defect’— it constitutes a Nash equilibrium against itself, and both sides get 3 instead of 1 each. Caspar stresses that this setup was first proposed around 1984, and has since been rediscovered or reinvented about three times.
— Caspar OesterheldProgram equilibrium's fatal flaw is needing a prearranged signal
The practical trouble with this mechanism is that the two programs must be ‘identical’ or satisfy some syntactic correspondence in order to cooperate with each other. If the two sides can communicate beforehand, they can simply say ‘I'll submit this code, you submit the same code’; but if the two are independent and write their programs at different times, coordination becomes very difficult. Even a single extra space, or writing ‘cooperate if identical, otherwise defect’ as ‘defect if different, otherwise cooperate’, is such a tiny change that it breaks the whole cooperation mechanism.
— Caspar OesterheldProof search does not fall into infinite recursion
Intuitively, ‘proving the opponent will cooperate’ and ‘directly running the opponent's program’ should both fall into an infinite loop — and the latter indeed does. But proof search does not: this relies on a relatively obscure result in logic, Löb's theorem. Its form is: if you can prove ‘if P is provable then P is true’, then you can prove P. The reason this is nontrivial is that you cannot prove your own proof system is always sound, so you cannot unconditionally infer P from ‘P is provable’. Löb's theorem happens to be exactly the tool program equilibrium needs, and once it is written down, the cooperation property follows almost immediately.
— Caspar OesterheldBreaking the infinite loop with epsilon probability
The naive approach — ‘run the opponent's program, and if it cooperates I cooperate’ — loops forever when both sides submit simultaneously. The fix: with a small probability epsilon, cooperate directly without looking at the opponent's program at all; only when this low-probability event does not trigger do you simulate the opponent and copy its action. This way every level of recursion has probability epsilon of stopping, and both sides eventually halt with probability one. This corresponds to a strategy in a repeated game that looks only at the opponent's last move, with the epsilon branch standing in for the first round before you have seen any of the opponent's actions.
— Caspar OesterheldA shared random string makes all simulations halt together
A new paper (first author Emry Cooper, with Vince Conitzer also on it) uses a trick to solve infinite simulation: model randomness as an infinite string of random numbers that a program receives at startup. When calling both opponents and yourself, pass the same random string and drop the first bit. Everyone checks whether the first bit is less than epsilon; if so, halt, otherwise drop the first bit and recurse. Because they share the same string, all simulations halt together at the same position. This lets you simulate multiple opponents as well as multiple past time steps.
— Caspar OesterheldUncorrelated randomness makes punishment fail
Why can't the uncorrelated case get the full folk theorem? Caspar gives a three-player intuition: Alice can use her own private randomness to deviate with very low probability, and when I simulate Alice I use a completely different random string, so I cannot tell whether she would really deviate; when you simulate her you use your random numbers, so ‘you detect her deviating’ and ‘I detect her deviating’ are also uncorrelated. The result is that low-probability deviations can hardly ever be caught simultaneously, so punishment cannot be coordinated. He also notes that if punishment requires two people to perform a specific action at the same time, this uncorrelatedness is even more fatal.
— Caspar OesterheldSimulationist programs are stronger than pybots
The third part of the paper defines more general simulationist programs: intuitively they do only one thing — run the opponent and the other players as inputs. Caspar says this class of programs is stronger than epsilon grounded pybots at reaching equilibrium in the uncorrelated case. The intuition: pybots require everyone to do the same thing, whereas simulationist programs allow only me to need to do the simulation, so I can independently sample your program ten thousand times — something pybots cannot do. The definition itself is recursive, and the base case might be ‘simulate the empty object’ or simply ignore the opponent's input.
— Caspar OesterheldThe folk theorem is bad news, not good news
Caspar's attitude toward the folk theorem is the opposite of mainstream game theory: game theorists usually treat it as a positive result, while he ‘feels very mixed about it’, because it means anything can happen, including a great many outcomes that are terrible for me — as long as it is a little better than ‘everyone punishing me to the maximum’, it is an equilibrium. The more equilibria there are, the harder it is for us to coordinate on one of them. He notes that the correlated case at least has a convex equilibrium space, which is somewhat better than choosing among six discrete points, but on the whole he agrees that the equilibrium selection problem is very important, and this is the motivation behind much of his work.
— Caspar OesterheldIn their own words · checked verbatim
the crucial addition is that the programs get to get access to each other's source code at runtime
Caspar Oesterheld4:10
all these like very minor changes would already break these uh schemes
Caspar Oesterheld13:16
robust program equilibrium is not actually a solution concept in the sense that Nash equilibrium is or trembling hand equilibrium is
Caspar Oesterheld17:22
Lub's theorem says that if you can prove that if you could prove P then P would be true then you would be able to prove P.
Caspar Oesterheld41:41
you just have like a very high credence that like if you face a corporate bot probably something funny is going on, right?
Caspar Oesterheld1:24:13
But if you don't have shared randomness, all of this like like this is all like complete fiction, right?
Caspar Oesterheld2:13:46
I think game theorists often view this as sort of like a positive results whereas I have like very mixed feelings about this because it's it's kind of like a well anything can happen
Caspar Oesterheld2:24:53
the programs themselves aren't rational they're doing don't do expected utility maximization they just do what their source code says
Caspar Oesterheld2:28:56
Figures
| Year program equilibrium was first proposed | around 1984 | 8:11 |
| Number of times program equilibrium was rediscovered/reinvented | about three | 8:11 |
| Number of programs allowed in the Manifold tournament | at most three | 6:11 |
| Year of Andrew Critch's bounded Löb theorem paper | 2019 | 46:44 |
| Average number of rounds for epsilon grounded fairbot to halt | about 1/epsilon | 1:07:58 |
| Condition for the simulation tree to grow | when epsilon is less than one half, the simulation tree grows faster than it shrinks | 1:46:31 |
| Proof system required by PrudentBot | PA plus the assumption that the system is consistent (PA plus one) | 1:40:24 |
| Share of essentially ineffective programs in the tournament | about 30% | 1:30:16 |
| Number of times a simulationist program independently samples the opponent (example) | 10,000 | 2:18:49 |
| Number of players in the game discussed (example) | 3 | 2:07:43 |
Glossary
- program equilibrium
- A game-theoretic setup: players submit programs, and at runtime the programs read each other's source code to decide their actions.
- Löb's theorem
- If ‘if P is provable then P is true’ is provable, then P is provable.
- folk theorem
- In a repeated game, any outcome better than the minimax payoff can be an equilibrium.
- epsilon grounded fairbot
- A program that cooperates directly with probability epsilon, and otherwise simulates the opponent and copies its action.
- simulationist programs
- Programs that do only one thing: run the opponent and the other players as inputs; recursively defined.
How to listen
Founders and engineers interested in game theory, AI alignment and mechanism design, especially those who want to understand the underlying logic of multi-agent cooperation.
Listeners uninterested in the details of logic and proof theory can skip the technical derivation from 40:40 to 1:07:58.