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. The same setting had previously been studied by R. Preston McAfee, J. V. Howard and Ariel Rubinstein.
The program equilibrium literature considers the following setting. Consider a normal-form game as a base game. For simplicity, consider a two-player game in which
S1
S2
u1
u2
i
pi
pi
p-i
si
i
ui(s1,s2)
i=1,2
One has to further deal with the possibility that one of the programs
pi
A program equilibrium is a pair of programs
(p1,p2)
(p1,p2)
i
pi'
(pi',p-i)
(p1,p2)
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.
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:
algorithm CliqueBot(opponent_program): if opponent_program
If both players submit this program, then the if-clause will resolve to true in the execution of both programs. As a result, both programs will cooperate. Moreover, (CliqueBot,CliqueBot) is an equilibrium. If either player deviates to some other program
pi
pi
This approach has been criticized for being fragile. 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.
Another approach is based on letting each player's program try to prove something about the opponent's program or about how the two programs relate. One example of such a program is the following:
algorithm FairBot(opponent_program): if there is a proof that opponent_program(this_program) = Cooperate then return Cooperate else return Defect
Using Löb's theorem it can be shown that when both players submit this program, they cooperate against each other. 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. Therefore, (FairBot,FairBot) is a program equilibrium as well.
Another proposed program is the following:
algorithm
\epsilon
\epsilon
Here
\epsilon
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
\epsilon
\Delta
(1-\epsilon)\Delta
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
(v1,v2)
(s1,s2)
ui(s1,s2)=vi
i
vi
vi\geq
min | |
\sigma-i |
max | |
si |
ui(\sigma-i,si)
-i
Theorem (folk theorem for program equilibrium): Let G be a base game. Let
(v1,v2)
(v1,v2)
(p1,p2)
(v1,v2)
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
(v1,v2)