Mathematical Foundations of AI Alignment, Lecture 20 (Program Equilibria)
Overview
Aaron Roth explains program equilibria as Nash equilibria in a higher-level game where players choose inspectable or simulatable programs rather than actions. In the Prisoner’s Dilemma, he shows how programs can support cooperation through exact code matching or recursive simulation with an escape probability ε ≤ 1/2, then connects joint simulation to discounted repeated games, where grim trigger sustains cooperation when the discount factor δ is at least 1/2.
Key takeaways
- Program equilibrium treats deployed software, not underlying actions, as the strategic choices; a unilateral program change can therefore alter both players’ actions.
- Exact source-code matching supports mutual cooperation in the Prisoner’s Dilemma but is brittle because equivalent programs may have different source strings and source access may be unavailable.
- The fε simulate-and-copy strategy halts through an escape probability ε and sustains cooperation as a program equilibrium when ε ≤ 1/2.
- Joint simulation of a repeated game gives the same expected incentives as a discounted repeated game because the probability that round t is real is (1 − δ)δᵗ.
- Grim trigger supports cooperation when δ ≥ 1/2, but adding cooperative equilibria does not remove mutual defection or rule out harmful coordination such as cartels.
- Faithful simulation is essential: if an agent can recognize that it is being simulated, it could cooperate during tests and defect when its action matters.
Chapters
- In ordinary Nash equilibrium, a unilateral deviation changes a player’s action while holding the other player’s action fixed.
- In program equilibria, each player chooses software to act on their behalf, and an agent may inspect or simulate its opponent’s program.
- Changing one program can change both players’ resulting actions because the other agent may respond to the new program.
- Cooperation costs its player $1 and gives the opponent $2, so mutual cooperation produces a payoff of $1 each.
- Defection is a dominant strategy in the one-shot game because a player avoids the $1 cost regardless of the opponent’s choice.
- The Nash outcome of mutual defection yields less social welfare than mutual cooperation.
- The underlying game remains the Prisoner’s Dilemma, but the strategic choices become programs that return actions.
- A program can take the opponent’s program as input and use it to determine what action to play.
- A unilateral program change can alter the opponent’s action even when the opponent’s program itself stays fixed.
- Programs could be modeled as Turing machines or as Python code that accepts another program’s source code as input.
- A program is not automatically a well-defined strategy because it may run forever rather than return an action.
- The model restricts attention to pairs of programs that return an action with probability one when run against each other.
- A pair of programs P and Q is in program equilibrium when neither player can improve by switching to another program unilaterally.
- The payoff is still calculated from the actions played in the underlying game, such as the Prisoner’s Dilemma.
- Unlike a base-game deviation, a program deviation can change the fixed opponent program’s output through its access to the new program.
- A program can compare its own source-code string with the opponent’s and cooperate only when the strings match exactly.
- Two copies of the matching program cooperate and each receive payoff 1 in the Prisoner’s Dilemma.
- A unilateral deviation makes the strings differ, causing the unchanged program to defect and limiting the deviator’s payoff to at most 0.
- Functionally identical programs can differ in whitespace, variable names, or implementation, so literal string comparison may reject equivalent strategies.
- Exact source inspection requires more access than is typical for deployed models such as Claude or GPT, where users generally make API calls.
- The next construction therefore relies on simulating an opponent’s behavior rather than reading its source code.
- The simulation model assumes agents cannot tell whether they are in reality or inside a simulation, even at deeper simulation levels.
- Randomness is independent at each level, so an agent’s simulated execution does not simply reuse the outer agent’s coin flips.
- If each agent waits for the other’s simulation to return, recursive calls can create an infinite regress and never produce actions.
- A natural strategy simulates the opponent and copies its action, cooperating if the simulation cooperates and defecting if it defects.
- When both agents use this rule, each simulation calls the other agent, which calls back again, preventing either from returning an action.
- The strategy must be modified to stop recursion while preserving enough incentive for both agents to cooperate.
- The strategy fε cooperates immediately with probability ε, without simulating the opponent.
- With probability 1 − ε, fε simulates the opponent with access to its own program and copies the returned action.
- For any ε greater than zero and less than one, repeated independent escape chances make the recursion terminate with probability one.
- Two copies of fε eventually return cooperation, so their underlying Prisoner’s Dilemma outcome is mutual cooperation.
- For a deviating program, let p be its probability of cooperation and q the unchanged fε program’s probability of cooperation; then q = ε + (1 − ε)p.
- The deviator’s expected payoff is 2q − p = 2ε + (1 − 2ε)p, which is maximized by p = 1 when ε ≤ 1/2.
- At ε greater than 1/2 the coefficient on p becomes negative, so defection can be profitable instead.
- A joint simulator runs both agents through a consistent history of a simulated repeated game, although only one round is real.
- Agents do not know which round will determine their payoff, so a simulated defection may trigger punishment before the real round occurs.
- The payoff remains the payoff from the single real round; players do not directly value the simulated rounds.
- At each recursion level, the simulator continues with probability δ or stops with probability 1 − δ.
- Both agents receive the same simulated history, choose actions based on that history, and have their action pair appended to it.
- At the base level, the chosen actions are played for real; actions returned by deeper levels instead extend the history passed upward.
- The number of simulated levels N has geometric distribution P(N = t) = (1 − δ)δᵗ.
- The recursion terminates with probability one whenever δ < 1.
- Agents observe earlier action pairs but cannot tell whether their current decision is at the real level or within the simulation.
- In a standard repeated game, strategies map histories to actions and payoffs are discounted by δ over time.
- In joint simulation, the probability that round t is the real round is (1 − δ)δᵗ, yielding the same weighted expected payoff.
- Because both models give the same incentives for every strategy pair, their Nash equilibria coincide; repeated-game results such as folk theorems carry over.
- Grim trigger cooperates as long as the opponent has always cooperated and defects forever after any observed defection.
- With both players using grim trigger, cooperation is an equilibrium in the repeated-game model, and therefore in the equivalent joint-simulation model, when δ is at least 1/2.
- A deviation gains 1 at the defection round but loses 1 in every later round; when future rounds are sufficiently valuable, the discounted losses outweigh the immediate gain.
- Program equilibria add cooperative outcomes to the one-shot Prisoner’s Dilemma, but mutual defection remains an equilibrium.
- Expanding the strategy space can enable mutual benefit as well as harmful coordination, including collusion and cartels.
- Simulatable agents increase the blast radius of a unilateral deviation because changing one program may change the other agent’s behavior.
Transcript excerpt
0:00 All right, I want to talk about a program equilibria. Just sort of an interesting idea for how you should think about strategic interactions in a world where principle might not be like directly acting um their own, but rather might be deploying say a software agent to act on their behalf. And the general idea is that in sort of traditional game theory when we study equilibrium, the premise is that what we have the ability to unilaterally control and hence the sort of basis on which we define the stability of equilibria is that we can sort of unilaterally
0:50 change the action that we take in the underlying game. And by unilateral, you know, what we mean is I can change my action, but like I can't change your action. And the, you know, what equilibrium requires is that play be stable in the sense that nobody should be able to improve their own payoff by changing their own action, holding everyone else's fixed. But you know in a world in which we have you know maybe like AI agents perhaps we're not like directly choosing the action we take rather the part of the game that we play is in deciding what agent to deploy. Like maybe what we're doing is we're deciding what piece of software to act on our behalf. And the thing about a piece of software is that
1:40 um it can be inspected. It can be simulated and this potentially opens up like a channel for cooperation even in one shy games that doesn't exist if if the premise is that you're playing in the game um yourselves just because you are much more opaque than the piece of software I can't simulate you and see what you would do in different situations. The idea of program
This is the start of the transcript. Save this video free for the whole transcript, searchable and time-coded.
In this course
Related notes
Summary, takeaways, and chapters were generated by AI from the video's transcript and may contain errors. The video belongs to its creator, Aaron Roth.