Program equilibrium is a game-theoretic solution concept for a scenario in which players submit computer programs to play the game on their behalf and the programs can read each other's source code.
The term was introduced by Moshe Tennenholtz in 2004.
[1] The same setting had previously been studied by R. Preston McAfee,[2] J. V. Howard[3] and Ariel Rubinstein.
[4] The program equilibrium literature considers the following setting.
For simplicity, consider a two-player game in which
Then we construct a new (normal-form) program game in which each player
The payoff (utility) for the players is then determined as follows.
For convenience one also often imagines that programs can access their own source code.
[nb 1] Finally, the utilities for the players are given by
, i.e., by applying the utility functions for the base game to the chosen strategies.
One way to deal with this is to restrict both players' sets of available programs to prevent non-halting programs.
that constitute a Nash equilibrium of the program game.
Instead of programs, some authors have the players submit other kinds of objects, such as logical formulas specifying what action to play depending on an encoding of the logical formula submitted by the opponent.
[6][7] Various authors have proposed ways to achieve cooperative program equilibrium in the Prisoner's Dilemma.
Multiple authors have independently proposed the following program for the Prisoner's Dilemma:[1][3][2] If both players submit this program, then the if-clause will resolve to true in the execution of both programs.
[5] If the players fail to coordinate on the exact source code they submit (for example, if one player adds an extra space character), both programs will defect.
The development of the techniques below is in part motivated by this fragility issue.
[8][9][10] Moreover, if one player were to instead submit a program that defects against the above program, then (assuming consistency of the proof system is used) the if-condition would resolve to false and the above program would defect.
If both players submit this program, then they terminate almost surely and cooperate.
The expected number of steps to termination is given by the geometric series.
Moreover, if both players submit this program, neither can profitably deviate, assuming
is sufficiently small, because defecting with probability
We here give a theorem that characterizes what payoffs can be achieved in program equilibrium.
The theorem uses the following terminology: A pair of payoffs
is called feasible if there is a pair of (potentially mixed) strategies
That is, a pair of payoffs is called feasible if it is achieved in some strategy profile.
is called individually rational if it is better than that player's minimax payoff; that is, if
, where the minimum is over all mixed strategies for Player
[nb 2] Theorem (folk theorem for program equilibrium):[4][1] Let G be a base game.
Then the following two claims are equivalent: The result is referred to as a folk theorem in reference to the so-called folk theorems (game theory) for repeated games, which use the same conditions on equilibrium payoffs