Program Equilibrium: Trading Code Makes Cooperation More Likely Than Trading People, but Coordination Is Extremely Hard
Program equilibrium lets two parties read each other's source code and use Löb's theorem to achieve cooperation; but cooperation depends on nearly identical code or shared randomness, and in reality the coordination cost is 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 increment 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 OesterheldThe fatal flaw of program equilibrium is that you must agree on a signal in advance
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 one extra space, or writing ‘cooperate if identical, otherwise defect’ as ‘defect if different, otherwise cooperate’, is such a tiny change that it makes the whole cooperation mechanism fail.
— Caspar OesterheldProof search does not fall into infinite recursion
Intuitively, ‘proving that 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 non-trivial is that you cannot prove that 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, and the epsilon branch is equivalent to the first round before you have seen any action from the opponent.
— Caspar OesterheldA shared random string makes all simulations halt at once
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 input 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 and also 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 extremely low probability, and when I simulate Alice I use a completely different random string, so I cannot tell whether she will really deviate; when you simulate her you use your randomness, so ‘you detect her deviating’ and ‘I detect her deviating’ are also uncorrelated. The result is that low-probability deviations can hardly be caught simultaneously, and punishment cannot be coordinated. He also mentions 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 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 may 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 they are a little better than ‘everyone punishing me to the maximum extent’, they are all equilibria. The more equilibria there are, the harder it is for us to coordinate on one of them. He mentions that the correlated case at least has a convex equilibrium space, which is somewhat better than choosing among six discrete points, but overall he agrees that the equilibrium selection problem is very important, and this is the motivation for 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 the program equilibrium setup was first proposed | around 1984 | 8:11 |
| Number of times program equilibrium has been rediscovered/reinvented | about three | 8:11 |
| Number of programs allowed to be submitted 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 halting rounds for epsilon grounded fairbot | 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 |
| Proportion 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 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.