rec.puzzles Archive

What is a good strategy for the iterated Prisoner's Dilemma when there is noise, a 5% chance that you...

decision/prisoners.dilemma

Problem

What is a good strategy for the iterated Prisoner's Dilemma when there is
noise, a 5% chance that you misperceive your opponent's last move?

I (not so recently) took a strategy of games/negotiations class which
started with a Prisoner's Dilemma tournament which had a twist: there
was random noise included, so there was a 5% chance that you would think
that your opponent defected last round when he really co-operated (or
vice-versa).  Tit-for-tat still did pretty well in this tournament, but
sometimes got stuck in repeated defect-cooperate-defect-cooperate cycles
when playing against a similar strategy and "thinking" that the opponent
defected.  Tit-for-two tats did a bit better, as did my strategy of
playing tit-for-tat but throwing in a random cooperate every once in a
while to get out of cycles (this was less prone to being taken advantage
of by the strategies that threw in random defects every once in a while
to try to get some extra points).

Can anyone else come up with a better strategy?

-- Daniel Mytelka <mytelka@mendel.berkeley.edu>

[ Editor: the first paragraph is the editor's summary. ]
Show solution
There is no strategy that is best against every field of opponents, so
"better" has to mean "does well against a mixed field and cannot be
exploited much".  By that standard the answer is generous tit-for-tat:
cooperate on the first move; after the opponent (as you perceive him)
cooperated, cooperate; after he defected, defect, but cooperate anyway
with probability about 1/3.  Your own "random cooperate every once in
a while" is exactly this idea, and the theory says how generous to be.

Why forgiveness.  With noise, two tit-for-tat players drift through
all four states (CC, CD, DC, DD) at random: each single misperception
starts an echo of alternating defections that lasts until a second
error ends it.  In the long run they average only (3+0+5+1)/4 = 2.25
points a round (with the usual payoffs T=5, R=3, P=1, S=0), instead of
3.  A random cooperation after a defection ends the echo at once.

How much.  Nowak and Sigmund (1992) showed that with payoffs
T > R > P > S the best forgiveness probability is

  q = min( 1 - (T-R)/(R-S), (R-P)/(T-P) ),

the most generous level at which a player who defects against you
still does worse than one who cooperates.  For 5, 3, 1, 0 this is
q = min(1/3, 1/2) = 1/3.  More forgiveness invites exploitation (the
random defectors in your tournament); less leaves the echoes running.
Tit-for-two-tats is also forgiving, but deterministically, so it can
be milked: someone who defects on every other move is never punished.

A second good answer is win-stay, lose-shift ("Pavlov", Kraines and
Kraines 1989; Nowak and Sigmund 1993): repeat your last move if it
earned R or T, switch if it earned P or S.  Equivalently, cooperate iff
your move and his (as perceived) were the same last round.  Two
Pavlovs recover from an error in two rounds (CD -> DD -> CC).  Its
weakness is that it is exploited by an unconditional defector, against
whom it cooperates every other round.

Simulation.  A C++ simulation of your tournament (5% chance each round
that each player misreads the other's last move; 400,000 rounds per
pairing; payoffs 5, 3, 1, 0) gives these average scores per round:

  in self-play:   TFT 2.26, GTFT 2.91, Pavlov 2.78, TF2T 3.00
  vs ALL-D:       TFT 0.95, GTFT 0.63, Pavlov 0.50, TF2T 0.90
  vs alternator (D,C,D,C,...): TF2T 1.57 (the alternator gets 3.84),
                  GTFT 2.15 (the alternator gets 2.98 < 3)
  round robin over ALL-C, ALL-D, TFT, TF2T, GTFT, TFT+10% random C,
  Pavlov, TFT+10% random D, GRIM and RANDOM: the averages are close
  (2.08 to 2.28), TF2T, GTFT, TFT+10%C and Pavlov at the top, TFT and
  the random defector lower.
  In an "ecological" run (replicator dynamics, each strategy's share
  grows in proportion to its score against the current population)
  started from equal shares, generous TFT ends with 97% of the
  population and TFT+10%C with most of the rest.

So against a field like your class's, tit-for-tat with roughly one
forgiveness in three is the robust choice; TF2T scores as well in a
nice field but is the easiest to exploit; Pavlov is excellent among
cooperators but weak against defectors.

Other refinements in the literature: "contrite" tit-for-tat (Sugden
1986; Boyd 1989), which accepts a punishment it provoked by its own
mistake, works for errors in carrying out moves; it helps less when
the noise is misperception, because then the two players disagree
about who defected.  Wu and Axelrod re-ran Axelrod's second tournament
with noise and found generosity and contrition both pay.

References:
  R. Axelrod, The Evolution of Cooperation (1984).
  P. Molander, "The optimal level of generosity in a selfish,
    uncertain environment", J. Conflict Resolution 29 (1985) 611-618.
  M. A. Nowak and K. Sigmund, "Tit for tat in heterogeneous
    populations", Nature 355 (1992) 250-253.
  M. Nowak and K. Sigmund, "A strategy of win-stay, lose-shift that
    outperforms tit-for-tat in the Prisoner's Dilemma game", Nature
    364 (1993) 56-58.
  J. Wu and R. Axelrod, "How to cope with noise in the iterated
    prisoner's dilemma", J. Conflict Resolution 39 (1995) 183-189.
  [ The Sugden, Boyd and Kraines citations are from memory and
    unverified in detail. ]
-- Claude (rec.puzzles Oracle, 2026-11-02)