Repeated Prisoner's Dilemma

Nordstrom, Introduction to Game Theory · Section 4.4 · CC BY-SA 4.0

Play once: defect. Play forever: cooperate. Finite repetition unravels by backward induction: the last round has no future, so defect; but then the second-to-last round is effectively last, so defect; and so on. Infinite repetition breaks the chain. The shadow of the future makes tit-for-tat viable.

Finite repetition: backward induction unravels

If both players know the game ends after round N, work backward. In round N there is no future punishment, so both defect. But then round N-1 is effectively the last real round, so both defect there too. The logic cascades all the way to round 1. Finite repetition gives the same result as playing once.

Scheme

; Repeated PD payoff matrix (per round)
; C = cooperate, D = defect
(define (pd-round me other)
  (cond
    ((and (eq? me 'C) (eq? other 'C)) 3)
    ((and (eq? me 'C) (eq? other 'D)) 0)
    ((and (eq? me 'D) (eq? other 'C)) 5)
    ((and (eq? me 'D) (eq? other 'D)) 1)))

; Backward induction: in a finite game, defect every round
(define (finite-game rounds)
  (let loop ((r 1) (total-me 0) (total-other 0))
    (if (> r rounds)
      (list total-me total-other)
      ; Both defect every round
      (loop (+ r 1)
            (+ total-me (pd-round 'D 'D))
            (+ total-other (pd-round 'D 'D))))))

(display "10-round finite game (both defect): ")
(display (finite-game 10))
(newline)
(display "per-round: 1 each. Could have had 3 each.")

Infinite repetition: tit-for-tat cooperates

When the game has no known endpoint, the future matters. Tit-for-tat: cooperate on round 1, then copy your opponent's last move. It is responsive (punishes defection), nice (starts cooperative), and forgiving (returns to cooperation). Axelrod's tournaments showed it outperforms pure strategies. Tit-for-tat is a closed feedback loop: perceive the opponent's last move, remember it, act on it. This is the same structure that makes general intelligence work -- consolidation over repeated interactions.

Scheme

; Tit-for-tat vs various strategies over N rounds

(define (play-rounds strat1 strat2 n)
  (let loop ((r 1) (hist1 '()) (hist2 '())
             (total1 0) (total2 0))
    (if (> r n)
      (list total1 total2)
      (let ((m1 (strat1 r hist2))
            (m2 (strat2 r hist1)))
        (loop (+ r 1)
              (cons m1 hist1) (cons m2 hist2)
              (+ total1 (pd-round m1 m2))
              (+ total2 (pd-round m2 m1)))))))

; Strategies
(define (always-defect r hist) 'D)
(define (always-cooperate r hist) 'C)
(define (tit-for-tat r hist)
  (if (= r 1) 'C (car hist)))

; Tournaments
(display "TFT vs TFT (20 rounds):     ")
(display (play-rounds tit-for-tat tit-for-tat 20))
(newline)
(display "TFT vs always-D (20 rounds): ")
(display (play-rounds tit-for-tat always-defect 20))
(newline)
(display "always-D vs always-D:        ")
(display (play-rounds always-defect always-defect 20))
(newline)
(display "always-C vs always-D:        ")
(display (play-rounds always-cooperate always-defect 20))
; TFT vs TFT: 60 each (mutual cooperation)
; TFT vs D: TFT gets hurt round 1 then matches

; Tit-for-tat vs various strategies over N rounds

(define (play-rounds strat1 strat2 n)
  (let loop ((r 1) (hist1 '()) (hist2 '())
             (total1 0) (total2 0))
    (if (> r n)
      (list total1 total2)
      (let ((m1 (strat1 r hist2))
            (m2 (strat2 r hist1)))
        (loop (+ r 1)
              (cons m1 hist1) (cons m2 hist2)
              (+ total1 (pd-round m1 m2))
              (+ total2 (pd-round m2 m1)))))))

; Strategies
(define (always-defect r hist) 'D)
(define (always-cooperate r hist) 'C)
(define (tit-for-tat r hist)
  (if (= r 1) 'C (car hist)))

; Tournaments
(display "TFT vs TFT (20 rounds):     ")
(display (play-rounds tit-for-tat tit-for-tat 20))
(newline)
(display "TFT vs always-D (20 rounds): ")
(display (play-rounds tit-for-tat always-defect 20))
(newline)
(display "always-D vs always-D:        ")
(display (play-rounds always-defect always-defect 20))
(newline)
(display "always-C vs always-D:        ")
(display (play-rounds always-cooperate always-defect 20))
; TFT vs TFT: 60 each (mutual cooperation)
; TFT vs D: TFT gets hurt round 1 then matches

The shadow of the future

Cooperation holds when the expected value of future cooperation exceeds the one-time gain from defecting. With a discount factor d (probability the game continues), cooperation via tit-for-tat is sustainable when the present value of cooperation outweighs the temptation to defect. As d approaches 1, the future looms large and cooperation stabilizes.

Scheme

; Shadow of the future: when does tit-for-tat sustain cooperation?
; Per-round payoffs: CC=3, DC=5, DD=1
; Cooperating forever: 3 / (1 - d)
; Defect then get punished: 5 + d*1 / (1 - d)
; Cooperation holds when: 3/(1-d) >= 5 + d/(1-d)
; Simplifies to: d >= 1/2

(define (coop-value d)
  (/ 3.0 (- 1.0 d)))

(define (defect-value d)
  (+ 5.0 (/ (* d 1.0) (- 1.0 d))))

(define (cooperation-holds? d)
  (>= (coop-value d) (defect-value d)))

(display "d=0.3: coop=") (display (number->string (coop-value 0.3) 1))
(display " defect=") (display (number->string (defect-value 0.3) 1))
(display " holds? ") (display (cooperation-holds? 0.3)) (newline)

(display "d=0.5: coop=") (display (number->string (coop-value 0.5) 1))
(display " defect=") (display (number->string (defect-value 0.5) 1))
(display " holds? ") (display (cooperation-holds? 0.5)) (newline)

(display "d=0.8: coop=") (display (number->string (coop-value 0.8) 1))
(display " defect=") (display (number->string (defect-value 0.8) 1))
(display " holds? ") (display (cooperation-holds? 0.8)) (newline)

(display "Threshold: d >= 1/2")

; Shadow of the future: when does tit-for-tat sustain cooperation?
; Per-round payoffs: CC=3, DC=5, DD=1
; Cooperating forever: 3 / (1 - d)
; Defect then get punished: 5 + d*1 / (1 - d)
; Cooperation holds when: 3/(1-d) >= 5 + d/(1-d)
; Simplifies to: d >= 1/2

(define (coop-value d)
  (/ 3.0 (- 1.0 d)))

(define (defect-value d)
  (+ 5.0 (/ (* d 1.0) (- 1.0 d))))

(define (cooperation-holds? d)
  (>= (coop-value d) (defect-value d)))

(display "d=0.3: coop=") (display (number->string (coop-value 0.3) 1))
(display " defect=") (display (number->string (defect-value 0.3) 1))
(display " holds? ") (display (cooperation-holds? 0.3)) (newline)

(display "d=0.5: coop=") (display (number->string (coop-value 0.5) 1))
(display " defect=") (display (number->string (defect-value 0.5) 1))
(display " holds? ") (display (cooperation-holds? 0.5)) (newline)

(display "d=0.8: coop=") (display (number->string (coop-value 0.8) 1))
(display " defect=") (display (number->string (defect-value 0.8) 1))
(display " holds? ") (display (cooperation-holds? 0.8)) (newline)

(display "Threshold: d >= 1/2")

Notation reference

Term	Scheme	Meaning
Tit-for-tat	(tit-for-tat r hist)	Cooperate first, then mirror opponent
Discount factor d	(coop-value d)	Probability game continues next round
Backward induction	(finite-game rounds)	Solve from the last round backward
Shadow of the future	(cooperation-holds? d)	Future payoff makes cooperation rational

Neighbors

Game theory foundations

🎲 Nordstrom 12 — Prisoner's Dilemma and Chicken (the one-shot case)
🎲 Nordstrom 13 — Volunteer's Dilemma

Paper connections

🍞 Hedges 2018 — compositional game theory makes repeated games composable via sequential composition of open games

Foundations (Wikipedia)

Translation notes

The payoff matrix here uses Nordstrom's convention (CC=3, CD=0, DC=5, DD=1), which is the standard form from Axelrod's tournaments. The discount factor analysis simplifies the folk theorem to its core insight: cooperation in repeated games requires d above a threshold determined by the payoff ratios. Axelrod's three properties of successful strategies (responsive, nice, unexploitable) are demonstrated by the tit-for-tat implementation.

← Volunteer's Dilemma by june.kim fin · 14 of 14