Cooperation: The Prisoner’s Dilemma

Gary T. Leavens^{∗} Department of Computer Science, 229 Atanasoff Hall Iowa State University, Ames, Iowa 50011-1040 USA leavens@cs.iastate.edu

April 30, 1993

1 The Prisoner’s Dilemma

The iterated prisoner’s dilemma is described in Douglas Hofstadeter’s book Metamagical Themas: Questing for the essence of mind and pattern (Basic Books, New York, 1985), chapter 29, and more fully in Robert Axelrod’s book The Evolution of Cooperation (Basic Books, New York, 1984). In a prisoner’s dilemma, two prisoners can each choose to either cooperate or defect. If both cooperate, they are rewarded by a payoff R. If both defect their reward is smaller, the punishment P. If one cooperates and the other defects, the defector gets the temptation T, while cooperator gets the sucker’s payoff S. The conditions for a prisoner’s dilemma are that

T > R > P > S  (1)
(T + S)/2 < R  (2)

The second condition ensures that alternating cooperation and defection makes the payoffs smaller than continual cooperation.

The iterated prisoner’s dilemma is like the prisoner’s dilemma, only repeated over many encounters.

2 The Program

The program is divided into several files. The file main.C holds the main program. This program uses an instance of the class World to do the real work. After running the example tournament, the results are printed.

∗This work is supported in part by the National Science Foundation under the Grant CCR-9108654.

⟨main.C ⟩≡

  #include "World.h"
  main() {

⟨create the World instance w⟩

    w->example();
    w->print_results(cout);
    return(0);
  }

To allow maximum flexibility in coding and debugging, the creation of the world is handled by a separate function. This allows derived classes of World to be used without changing the main program.

⟨create the World instance w⟩≡

    extern World *WorldMaker();
    World* w = WorldMaker();

3 Worlds

3.1 Class World

The class World is an abstract base class that describes the protocol that worlds must follow to be used by the main program. Its interface is described in the file World.h. Objects of class World are collections of prisoners. A world is responsible for playing the prisoners against each other according to the rules of the dilemma (the member function example), and for printing itself on an

ostream.

⟨World.h⟩≡

  #if !defined(_WORLD_H)
  #define _WORLD_H
  #include <iostream.h>
  #include "Prisoner.h"
  class World {
  public:
    virtual void example(int numRounds = 20) = 0;
      // MODIFIES: *this
      // EFFECT: run the prisoner's dilemma for numRounds rounds.
    virtual void print_results(ostream& o) = 0;
      // MODIFIES: o

// EFFECT: Write a printed representation for the results
// of w's tournament on o.
protected:
void play_against(Prisoner* fst, Prisoner* snd, int numRounds) {
// MODIFIES: *fst, *snd
// EFFECT: play *fst against *snd for numRounds
// newRound really means ``new partner''
fst->newRound();   // These were fixed.
snd->newRound();
for (int i = 1; i <= numRounds; i++) {
  one_round(fst, snd);
}
}
virtual void one_round(Prisoner* fst, Prisoner* snd);
// MODIFIES: *fst, *snd
// EFFECT: play *fst against *snd for numRounds
};
#endif

The file World.C contains the implementation of the one_round member function of World. Both prisoners are asked for their decisions, and then both are informed of the choices. A prisoner does not have to remember its own choice.

⟨World.C ⟩≡

#include "World.h"
void World::one_round(Prisoner* fst, Prisoner* snd) {
Decision fsts, snds;
fsts = fst->decide();
snds = snd->decide();
fst->yours_others(fsts, snds);
snd->yours_others(snds, fsts);
}

3.2 WorldMaker

The function WorldMaker is placed in a separate file. This allows derived classes of the class World to be used. This version of WorldMaker uses the the class StdWorld. The header file StdWorld.h itself includes the header file World.h, so the latter need not be included here.

⟨WorldMaker.C ⟩≡

  #include "StdWorld.h"
  #include "PrisonerTypes.h"

⟨addTwice macro definition⟩

  World * WorldMaker()
  {
    StdWorld *w = new StdWorld;

⟨add a bunch of Prisoners to the world⟩

    return(w);
  }

Each kind of prisoner is added to the world twice, so that its strategy can be played against itself. Since prisoners may be confused if they are playing against themselves, it will not do to add the same prisoner object twice. What has to be done is to create each strategy twice. The following definition helps with this task, as it creates two new objects of the same strategy. It is a macro because in C++ classes are not first-class values.

⟨addTwice macro definition⟩≡

  #define addTwice(strategy) \
   { w->addPrisoner(new strategy); w->addPrisoner(new strategy); }

In this version of the program, there are only two strategies (types of prisoners).

⟨add a bunch of Prisoners to the world⟩≡

    addTwice(AllC);
    addTwice(AllD);

3.3 The Standard World

The standard world is a collection of prisoners (strategies). Derived classes of World might allow tracing, or evolution, etc.

The interface of StdWorld is derived from World. The member functions example and print_results need to be redefined, because they are not pure virtual in StdWorld, but will be implemented. The StdWorld class also provides the addPrisoner member function; this is not in the interface of World because the main program does not need to know about it. However, it is needed by

WorldMaker.

⟨StdWorld.h⟩≡

#if !defined(_STDWORLD_H)
#define _STDWORLD_H
#include "World.h"

⟨StdWorld representation’s include files⟩

class StdWorld : public World {
public:
  StdWorld()
    // CONSTRUCTS: *this
    // EFFECT: initialize *this to have no prisoners.
    : contestants() {}
  virtual void addPrisoner(Prisoner* p);
     // MODIFIES: *this
     // EFFECT: add p to this world.
  void example(int numRounds);
  void print_results(ostream& o);

⟨StdWorld’s protected and private parts⟩

};
#endif

The world keeps track of a list of Prisoners. A list is better than an array or some other static structure, since the addPrisoner operation must be able to add Prisoners dynamically.

We use an implementation of lists from a “Library of Efficient Data Types and Algorithms” (LEDA) by Stefan Näher (available by anonymous ftp from ftp.uni-sb.de). The inclusion of the LEDA header file <LEDA/list.h> makes the lists from LEDA available. The typedef makes it easier to refer to a list of pointers to prisoners. The list is not actually a list of prisoners, so that objects of several derived classes of prisoners can be included in the list.

⟨StdWorld representation’s include files⟩≡

#include "Prisoner.h"
#include <LEDA/list.h>
typedef list<Prisoner *> PrisonerList;

⟨StdWorld’s protected and private parts⟩≡

private:
   PrisonerList contestants;

The file StdWorld.C contains the implementation of the standard world.

⟨StdWorld.C ⟩≡

#include "StdWorld.h"
⟨StdWorld’s addPrisoner member function⟩

⟨StdWorld’s example member function⟩

⟨StdWorld’s print_results member function⟩

The addPrisoner member function simply delegates to the contestants list member function append.

⟨StdWorld’s addPrisoner member function⟩≡
void StdWorld::addPrisoner(Prisoner* p)
{
  contestants.append(p);
}

The member function example must run the tournament. The forall_items macro is defined by LEDA do the body (in {}) for each list_item in the list of contestants, with the list_item assigned to the variable fst. The member function inf for lists gets the information (in this case a pointer of type

Prisoner*) from a list_item.

⟨StdWorld’s example member function⟩≡

void StdWorld::example(int numRounds = 20)
{
  list_item fst, snd;
  forall_items(fst, contestants) {
    for (snd = contestants.succ(fst); snd ; snd = contestants.succ(snd)) {
      play_against(contestants.inf(fst), contestants.inf(snd), numRounds);
    }
  }
}

The forall macro is also defined by LEDA.

⟨StdWorld’s print_results member function⟩≡
void StdWorld::print_results(ostream& o)
{
  Prisoner* p;
  forall(p, contestants) {
    p->print_results(o);
  }
}

4 Decisions

A decision is either to cooperate or defect. This is represented by an enumeration type. The payoffFor function returns the payoff

⟨Decision.h⟩≡

#if !defined(_DECISION_H)
#define _DECISION_H
enum Decision {cooperate = 0, defect = 1};
extern int payoffFor(Decision mine, Decision yours);
    // EFFECT: return the payoff for me if I decided mine and you yours.
#endif

The actual payoff matrix is kept in a static variable, so it is local to the file

Decision.C.

⟨Decision.C ⟩≡

#include "Decision.h"
static int payoffs[2][2] = { {-1, -5}, {0, -3}};
int payoffFor(Decision mine, Decision yours)
{
  return(payoffs[mine][yours]);
}

5 Prisoners

The header file Prisoner.h contains the definition of the abstract base class Prisoner. All types of prisoners will be defined as subtypes of this type. To define a subtype, one must, at a minimum, redefine the pure virtual member

functions newRound, decide, and name.

⟨Prisoner.h⟩≡

#if !defined(_PRISONER_H)
#define _PRISONER_H
#include <iostream.h>
#include "Decision.h"
class Prisoner {
public:

virtual void newRound() = 0;
// MODIFIES: *this
// EFFECT: discard any history information,
// as a new partner in the dilemma has arrived.
virtual Decision decide() = 0;
// MODIFIES: *this
// EFFECT: decide whether to cooperate or defect.
virtual void yours_others(Decision yours, Decision others) {
// MODIFIES: *this
// EFFECT: record the winnings from this round.
// You will need to override this to update any history variables.
won += payoffFor(yours, others);
}
virtual const char *name() const = 0;
// EFFECT: return the name of this strategy
int winnings() const {
// EFFECT: return this prisoner's winnings
return won;
}
virtual void print_results(ostream& o) const {
o << name() << " won " << winnings() << "\n";
}
private:
int won;  // perhaps ``years_in_jail'' would be better
};
#endif

The header file PrisonerTypes.h collects the declarations of all the prisoners types. Note that Prisoner.h has to guard against being included several times. In this version of the program there are only two types of prisoners.

⟨PrisonerTypes.h⟩≡

#include "Prisoner.h"
#include "AllC.h"
#include "AllD.h"

Prisoners of type AllC always cooperate.

⟨AllC.h⟩≡

#include "Prisoner.h"
class AllC : public Prisoner {
public:
void newRound() {}

const char* name() const { return "AllC"; }
Decision decide() {
  return cooperate;
}
};

Prisoners of type AllC always cooperate.

⟨AllD.h⟩≡

#include "Prisoner.h"
class AllD : public Prisoner {
public:
void newRound() {}
const char* name() const { return "AllD"; }
Decision decide() {
  return defect;
}
};