5D Library › Evolutionary Game Theory, Direct and Indirect Reciprocity and the Emergence of Cooperation · 中文

Chapter 3 Direct Reciprocity: Tournaments, Noise and Forgiveness

Two tournaments

In 1971 Trivers proposed that unrelated individuals can sustain cooperation through “reciprocal altruism”: I help you today and you help me tomorrow; as long as they will meet again, a cheat loses future help (Trivers 1971). In game theory the idea takes the form of the repeated prisoner’s dilemma.

Evidence

Axelrod’s tournaments. Axelrod invited researchers in game theory and related fields to submit computer programs to play the repeated prisoner’s dilemma, had them play each other in pairs (each program also played a copy of itself), and ranked them by total score. The first tournament had 14 programs (plus a random strategy), with 200 rounds per match; the winner was tit for tat (TFT), submitted by Anatol Rapoport: cooperate in the first round and then repeat whatever the other player did in the previous round (Axelrod 1980a). After the results and analysis of the first tournament had been published, the second tournament received 62 programs, the length of matches was made random, and tit for tat won again (Axelrod 1980b). Axelrod summed up the features of successful programs: never be the first to defect (nice), retaliate at once against defection (provocable), return to cooperation after retaliating (forgiving), and behave simply and clearly. In 1981 Axelrod and the biologist Hamilton linked these results to biological evolution in Science (Axelrod and Hamilton 1981).

Two points are often overlooked. First, tit for tat can never score more than its opponent in any match: it defects only after the other side has defected, so the number of times it takes advantage of the other cannot exceed the number of times it is taken advantage of. Its high total comes from sustaining cooperation with many programs, not from beating anybody. Second, the rankings depend on the field of entries. Axelrod himself tested the robustness of his conclusions with “hypothetical tournaments” in which the field was altered (Axelrod 1980b).

Calculation

# A small round-robin tournament in the spirit of Axelrod (1980): eleven simple rules;
# every pair (and each rule against its own twin) plays 200 rounds of the prisoner's
# dilemma with Axelrod's payoffs R = 3, S = 0, T = 5, P = 1. With execution noise eps,
# each intended move is flipped with probability eps. Scores are average points per
# round. This is NOT a replay of Axelrod's tournaments, whose 14 and 62 entries were
# more varied; rankings depend on the field of entries.
import random
rng = random.Random(5)
PAY = {("C", "C"): 3, ("C", "D"): 0, ("D", "C"): 5, ("D", "D"): 1}

def allc(m, o): return "C"
def alld(m, o): return "D"
def tft(m, o): return o[-1] if o else "C"
def stft(m, o): return o[-1] if o else "D"                 # suspicious TFT
def tf2t(m, o): return "D" if o[-2:] == ["D", "D"] else "C"
def grim(m, o): return "D" if "D" in o else "C"
def wsls(m, o):                                            # win-stay, lose-shift (Pavlov)
    if not m: return "C"
    return m[-1] if PAY[(m[-1], o[-1])] >= 3 else ("D" if m[-1] == "C" else "C")
def gtft(m, o):                                            # forgives a D with prob. 1/3
    if not o or o[-1] == "C": return "C"
    return "C" if rng.random() < 1 / 3 else "D"
def joss(m, o):                                            # TFT, but sneaks in 10 % D
    if o and o[-1] == "D": return "D"
    return "D" if rng.random() < 0.1 else "C"
def tester(m, o):              # probes with D in round 1; if the other side does not hit
    if not m: return "D"       # back in round 2, it defects every other round; else TFT
    if len(m) == 1: return "C"
    if o[1] == "D": return o[-1]
    return "D" if len(m) % 2 == 0 else "C"
def rand(m, o): return "C" if rng.random() < 0.5 else "D"
RULES = {"TFT": tft, "TF2T": tf2t, "GTFT": gtft, "WSLS": wsls, "GRIM": grim, "ALLC": allc,
         "STFT": stft, "JOSS": joss, "RANDOM": rand, "ALLD": alld,
         "TESTER": tester}

def match(f, g, eps, n=200):
    a, b, sa, sb = [], [], 0, 0
    for _ in range(n):
        x, y = f(a, b), g(b, a)
        if rng.random() < eps: x = "D" if x == "C" else "C"
        if rng.random() < eps: y = "D" if y == "C" else "C"
        a.append(x); b.append(y); sa += PAY[(x, y)]; sb += PAY[(y, x)]
    return sa / n, sb / n

def tournament(eps, reps):
    tot = {k: 0.0 for k in RULES}
    names = list(RULES)
    for _ in range(reps):
        for i, p in enumerate(names):
            for q in names[i:]:
                s1, s2 = match(RULES[p], RULES[q], eps)
                if p == q: tot[p] += s1
                else: tot[p] += s1; tot[q] += s2
    return {k: v / (reps * len(names)) for k, v in tot.items()}

for eps, reps in ((0.0, 20), (0.01, 20), (0.05, 20)):
    res = sorted(tournament(eps, reps).items(), key=lambda kv: -kv[1])
    print(f"noise {eps:4.2f}: " + "  ".join(f"{k} {v:.2f}" for k, v in res[:5]))
    print("            " + "  ".join(f"{k} {v:.2f}" for k, v in res[5:]))

print("a rule against its own twin, points per round (mean of 200 matches)")
print("        noise 0   1 %, 200 rounds   1 %, 5000 rounds   5 %, 5000 rounds")
for name in ("TFT", "GTFT", "WSLS", "GRIM"):
    row = []
    for eps, n in ((0.0, 200), (0.01, 200), (0.01, 5000), (0.05, 5000)):
        f = RULES[name]
        row.append(sum(match(f, f, eps, n)[0] for _ in range(200)) / 200)
    print(f"  {name:5s}  {row[0]:.2f}        {row[1]:.2f}              {row[2]:.2f}"
          f"               {row[3]:.2f}")
# noise 0.00: GTFT 2.64  TF2T 2.54  TFT 2.50  WSLS 2.43  ALLC 2.43
#             TESTER 2.31  GRIM 2.29  RANDOM 2.21  STFT 2.04  ALLD 1.86  JOSS 1.86
# noise 0.01: GTFT 2.43  TF2T 2.37  TESTER 2.31  WSLS 2.30  TFT 2.25
#             RANDOM 2.20  ALLC 2.16  STFT 2.13  GRIM 2.07  JOSS 1.98  ALLD 1.89
# noise 0.05: TESTER 2.31  GTFT 2.30  TF2T 2.25  WSLS 2.25  RANDOM 2.23
#             TFT 2.21  STFT 2.18  JOSS 2.15  GRIM 2.04  ALLC 2.04  ALLD 2.03
# a rule against its own twin, points per round (mean of 200 matches)
#         noise 0   1 %, 200 rounds   1 %, 5000 rounds   5 %, 5000 rounds
#   TFT    3.00        2.43              2.26               2.25
#   GTFT   3.00        2.97              2.97               2.86
#   WSLS   3.00        2.95              2.95               2.78
#   GRIM   3.00        1.51              1.05               1.15

The program runs a small round robin among 11 simple rules, with Axelrod’s payoffs: mutual cooperation gives each R=3R = 3, mutual defection P=1P = 1, defecting against a cooperator T=5T = 5 and being defected against S=0S = 0. It is not a replay of Axelrod’s tournaments. In this field, without noise, tit for tat comes third (2.50), behind generous tit for tat (GTFT, which still cooperates with probability 1/3 after being defected against; 2.64) and “tit for two tats” (TF2T, which retaliates only after two consecutive defections; 2.54). With 1 % execution errors tit for tat falls to fifth (2.25), and with 5 % to sixth. The rankings shift with noise and with the opponents, which is exactly the second point above.

The second part of the program is clearer still. Without noise every rule earns 3.00, full cooperation, against its own copy. With 1 % execution errors two tit-for-tat players average only 2.43 over 200 rounds and 2.26 over 5,000 rounds; GRIM (defect for ever after a single defection) does worse, 1.51 over 200 rounds. The reason is that when one side defects once by accident, the other retaliates in the next round, the first retaliates in turn, and the two fall into an alternation of “your defection, my defection” until the next error brings them back to cooperation or into mutual defection. Generous tit for tat and win-stay, lose-shift (WSLS) stay at 2.95 or above under the same conditions.

Markov chains under noise

Making “tit for tat falls into a cycle of retaliation” precise needs a tool. A strategy that looks only at the previous round (a memory-one strategy) can be written as four numbers 𝒑=(pCC,pCD,pDC,pDD)\mathbf p = (p_{CC}, p_{CD}, p_{DC}, p_{DD}): the probability of cooperating in this round after the previous round’s outcome for oneself and the other was CC, CD, DC or DD. Tit for tat is (1,0,1,0)(1, 0, 1, 0) and win-stay, lose-shift is (1,0,0,1)(1, 0, 0, 1): after “winning” (RR or TT) it keeps its previous move, after “losing” (SS or PP) it switches. When two such strategies play, the previous round’s outcome forms a four-state Markov chain; an execution error ε\varepsilon turns each probability into (1−ε)p+ε(1−p)(1 – \varepsilon)p + \varepsilon(1 – p). Long-run average payoffs follow from the stationary distribution of the chain.

Calculation

# Memory-one strategies p = (p_CC, p_CD, p_DC, p_DD): probability of cooperating after
# (own last move, other's last move). With execution error eps an intended move is
# flipped. Two such players form a 4-state Markov chain; long-run payoffs come from its
# stationary distribution (infinitely repeated game, no discounting).
import itertools

def flip(p, eps): return tuple((1 - eps) * x + eps * (1 - x) for x in p)

def stationary(p, q, eps):
    p, q = flip(p, eps), flip(q, eps)
    qs = (q[0], q[2], q[1], q[3])          # the other player sees CD as DC and vice versa
    M = [[a * b, a * (1 - b), (1 - a) * b, (1 - a) * (1 - b)] for a, b in zip(p, qs)]
    A = [[M[j][i] - (i == j) for j in range(4)] for i in range(4)]   # v (M - I) = 0
    A[3] = [1.0] * 4                                                  # and sum(v) = 1
    rhs = [0.0, 0.0, 0.0, 1.0]
    for col in range(4):                     # Gaussian elimination with pivoting
        piv = max(range(col, 4), key=lambda r: abs(A[r][col]))
        A[col], A[piv] = A[piv], A[col]; rhs[col], rhs[piv] = rhs[piv], rhs[col]
        for r in range(4):
            if r != col and A[r][col]:
                f = A[r][col] / A[col][col]
                A[r] = [x - f * y for x, y in zip(A[r], A[col])]; rhs[r] -= f * rhs[col]
    return [rhs[i] / A[i][i] for i in range(4)]

def payoffs(p, q, eps, R, S, T, P):
    v = stationary(p, q, eps)
    return (v[0] * R + v[1] * S + v[2] * T + v[3] * P,
            v[0] * R + v[1] * T + v[2] * S + v[3] * P)

b, c, eps = 3.0, 1.0, 0.01
DON = (b - c, -c, b, 0.0)                    # donation game: R, S, T, P
g = 1 - c / b
ST = {"TFT": (1, 0, 1, 0), "GTFT": (1, g, 1, g), "GTFT 0.5": (1, 0.5, 1, 0.5),
      "WSLS": (1, 0, 0, 1),
      "ALLC": (1, 1, 1, 1), "ALLD": (0, 0, 0, 0)}
print(f"donation game b = {b:.0f}, c = {c:.0f}, error {eps:.0%};"
      f" GTFT forgives with 1 - c/b = {g:.3f}")
print("resident   payoff vs itself   ALLD invader gets   ALLC invader gets")
for r in ("TFT", "GTFT", "GTFT 0.5", "WSLS"):
    own = payoffs(ST[r], ST[r], eps, *DON)[0]
    vd = payoffs(ST["ALLD"], ST[r], eps, *DON)[0]
    vc = payoffs(ST["ALLC"], ST[r], eps, *DON)[0]
    print(f"  {r:8s}     {own:.3f}             {vd:.3f}              {vc:.3f}")
v = stationary(ST["TFT"], ST["TFT"], eps)
print("TFT pair, long-run share of CC, CD, DC, DD: " + ", ".join(f"{x:.3f}" for x in v))

# How much generosity can GTFT afford? Scan q; GTFT(q) is a best reply to itself if no
# deterministic memory-one rule (16 of them) earns more against it. Compare with
# q* = min{1 - (T - R)/(R - S), (R - P)/(T - P)} (Nowak & Sigmund 1992; Molander 1985).
RULE16 = list(itertools.product((0, 1), repeat=4))
def stable_range(R, S, T, P, e=1e-5):
    ok = []
    for k in range(1, 1000):
        q = k / 1000; gt = (1, q, 1, q)
        own = payoffs(gt, gt, e, R, S, T, P)[0]
        if max(payoffs(r, gt, e, R, S, T, P)[0] for r in RULE16) <= own + 1e-3:
            ok.append(q)
    return min(ok), max(ok)
for name, (R, S, T, P) in (("donation b=3, c=1", DON), ("Axelrod 3,0,5,1", (3, 0, 5, 1)),
                           ("R,S,T,P = 3,0,4,1", (3, 0, 4, 1))):
    f1, f2 = 1 - (T - R) / (R - S), (R - P) / (T - P)
    lo, hi = stable_range(R, S, T, P)
    print(f"{name:18s}: stable for q in [{lo:.3f}, {hi:.3f}];"
          f" formula min({f1:.3f}, {f2:.3f}) = {min(f1, f2):.3f}")

# WSLS against ALLD: WSLS alternates C, D, so ALLD earns (T + P)/2 = b/2 per round.
print("WSLS resident, error 1 %: own payoff vs ALLD invader's payoff")
for bb in (1.5, 2.0, 2.5, 4.0):
    D = (bb - 1, -1, bb, 0)
    print(f"  b/c = {bb}: {payoffs(ST['WSLS'], ST['WSLS'], eps, *D)[0]:.3f} vs"
          f" {payoffs(ST['ALLD'], ST['WSLS'], eps, *D)[0]:.3f}")

# Press & Dyson (2012) extortion with chi = 3, Axelrod payoffs, phi = 1/26: p = (1 - 2
# phi (chi - 1), 1 - phi (1 + 4 chi), phi (4 + chi), 0) = (11/13, 1/2, 7/26, 0).
chi, phi = 3, 1 / 26
EXT = (1 - 2 * phi * (chi - 1), 1 - phi * (1 + 4 * chi), phi * (4 + chi), 0)
print("extortioner (chi = 3) vs opponent: (s_X - P)/(s_Y - P), s_X, s_Y")
for name, q in (("ALLC", (1, 1, 1, 1)), ("TFT", (1, 0, 1, 0)), ("WSLS", (1, 0, 0, 1)),
                ("random 0.5", (0.5,) * 4), ("GTFT 1/3", (1, 1 / 3, 1, 1 / 3))):
    sx, sy = payoffs(EXT, q, 0.0, 3, 0, 5, 1)
    ratio = f"{(sx - 1) / (sy - 1):.3f}" if abs(sy - 1) > 1e-9 else "0 = 3 x 0"
    print(f"  {name:10s}: {ratio:9s}   {sx:.3f}  {sy:.3f}")
sx, sy = payoffs(EXT, EXT, 0.0, 3, 0, 5, 1)
print(f"  two extortioners: {sx:.3f} each; two cooperators would get 3.000")
# donation game b = 3, c = 1, error 1%; GTFT forgives with 1 - c/b = 0.667
# resident   payoff vs itself   ALLD invader gets   ALLC invader gets
#   TFT          1.000             0.049              1.951
#   GTFT         1.970             1.990              1.970
#   GTFT 0.5     1.961             1.505              1.965
#   WSLS         1.941             1.490              0.510
# TFT pair, long-run share of CC, CD, DC, DD: 0.250, 0.250, 0.250, 0.250
# donation b=3, c=1 : stable for q in [0.020, 0.666]; formula min(0.667, 0.667) = 0.667
# Axelrod 3,0,5,1   : stable for q in [0.010, 0.333]; formula min(0.333, 0.500) = 0.333
# R,S,T,P = 3,0,4,1 : stable for q in [0.020, 0.666]; formula min(0.667, 0.667) = 0.667
# WSLS resident, error 1 %: own payoff vs ALLD invader's payoff
#   b/c = 1.5: 0.485 vs 0.740
#   b/c = 2.0: 0.971 vs 0.990
#   b/c = 2.5: 1.456 vs 1.240
#   b/c = 4.0: 2.912 vs 1.990
# extortioner (chi = 3) vs opponent: (s_X - P)/(s_Y - P), s_X, s_Y
#   ALLC      : 3.000       3.727  1.909
#   TFT       : 0 = 3 x 0   1.000  1.000
#   WSLS      : 3.000       2.364  1.455
#   random 0.5: 3.000       2.562  1.521
#   GTFT 1/3  : 3.000       2.616  1.539
#   two extortioners: 1.000 each; two cooperators would get 3.000

There are four results.

First, under 1 % errors two tit-for-tat players spend 25 % of the time in each of the four states CC, CD, DC and DD in the long run, with average payoff (R+S+T+P)/4(R + S + T + P)/4, which in the donation game with b=3b = 3, c=1c = 1 is 1.000, half of full cooperation (2). This does not depend on the error rate: the lower the rate, the longer it takes to reach this stationary state, but for any positive rate the long-run result is the same (Figure 2, left). It also implies a subtler problem: in a population of tit-for-tat players an always-cooperate player earns 1.951, more than tit for tat’s own 1.000, so a tit-for-tat population is gradually diluted by “unconditional nice guys”, paving the way for invasion by always defect.

Second, the forgiveness probability of generous tit for tat. In 1992 Nowak and Sigmund found in population simulations containing many stochastic strategies that tit for tat acts as a “catalyst”: it first clears out the defectors and is then replaced by the more forgiving generous tit for tat (Nowak and Sigmund 1992). Generous tit for tat still cooperates with probability qq after being defected against, and the upper limit on qq is

q*=min⁡{1−T−RR−S,R−PT−P}q^* = \min\left\{1 – \frac{T – R}{R – S},\ \frac{R – P}{T – P}\right\}

Molander had obtained this result in 1985 in discussing “the optimal level of generosity in a selfish, uncertain environment” (Molander 1985). In the donation game both terms equal 1−c/b1 – c/b. The program searches all 16 deterministic memory-one strategies for the best reply to generous tit for tat and finds that it is a best reply to itself for qq up to 0.666, in agreement with 1−c/b=0.6671 – c/b = 0.667; with Axelrod’s payoffs the limit is 1/3 and with (R,S,T,P)=(3,0,4,1)(R, S, T, P) = (3, 0, 4, 1) it is 2/3, both matching the formula. Note that 1−c/b1 – c/b is the upper limit that still resists always defect. Molander’s “optimal level of generosity”, and the generous tit for tat that evolved in Nowak and Sigmund’s simulations (forgiving about 1/3 of defections under Axelrod’s payoffs), both refer to values on or near this boundary: as forgiving as possible without being exploited by defectors. But exactly at the boundary there is no margin: without errors always defect gains qb=b−cqb = b – c per round from its forgiveness, the same as two generous tit-for-tat players earn by cooperating; with 1 % errors always defect already earns slightly more against it (1.990) than it earns itself (1.970). With q=0.5q = 0.5 a defector earns only 1.505, while generous tit for tat earns 1.961. The framework’s “the forgiveness probability is 1−c/b1 – c/b” should be read as “the forgiveness probability must not exceed 1−c/b1 – c/b, and in practice should stay a little below it”.

Third, the condition for win-stay, lose-shift. In 1993 Nowak and Sigmund found in population simulations with errors that win-stay, lose-shift often beats tit for tat: it restores cooperation within two rounds after an error (both sides defect once, both “lose”, and so both switch back to cooperation together), and it exploits unconditional cooperators (Nowak and Sigmund 1993). Kraines and Kraines had studied the strategy in 1989 under the name “Pavlov” (Kraines and Kraines 1989). But its advantage is conditional: against always defect, win-stay, lose-shift alternates between cooperation and defection, so the defector receives TT once and PP once every two rounds, an average of (T+P)/2(T + P)/2. A population of win-stay, lose-shift resists defectors only if R>(T+P)/2R > (T + P)/2, which in the donation game is b−c>b/2b – c > b/2, or b/c>2b/c > 2. The program shows that with 1 % errors, at b/c=1.5b/c = 1.5 and 2.0 the defector’s payoff (0.740, 0.990) exceeds win-stay, lose-shift’s own (0.485, 0.971), while at b/c=2.5b/c = 2.5 and 4 it is lower. With Axelrod’s payoffs R=3R = 3 is exactly (T+P)/2=3(T + P)/2 = 3, so win-stay, lose-shift sits on the boundary.

Fourth, zero-determinant strategies. In 2012 Press and Dyson discovered that some memory-one strategies can unilaterally impose a linear relation between their own and their opponent’s long-run payoffs; among them, “extortion” strategies enforce sX−P=χ(sY−P)s_X – P = \chi\,(s_Y – P) with χ>1\chi > 1, whatever the opponent does (Press and Dyson 2012). The program takes χ=3\chi = 3; against always cooperate, win-stay, lose-shift, a random strategy and generous tit for tat the ratio is exactly 3.000; against tit for tat both sides end at PP and the relation holds in the form 0=3×00 = 3 \times 0. An extortioner never loses a match, but two extortioners meeting each other earn only 1.000, far less than the 3.000 of two cooperators.

Which one does evolution pick?

Winning a match and evolving in a population are different things. The next program places these strategies in a finite population: each time a random individual imitates another with a probability that rises with the other’s payoff advantage, and mutations are rare, so the population is usually made up of a single strategy and is occasionally taken over by a new one. Computing all pairwise fixation probabilities gives the long-run share of time the population spends with each strategy (Imhof et al. 2007).

Calculation

# Which memory-one rule does evolution pick? Finite population of N players, donation
# game with error eps = 1 %, long-run payoffs from p06's Markov chain. Imitation by
# pairwise comparison: a random player copies a random other with probability 1 / (1 +
# exp(-beta * (payoff difference))). With rare mutations (Fudenberg-Imhof limit, as in
# Imhof, Fudenberg & Nowak 2007) the population is almost always monomorphic; we compute
# all fixation probabilities and the long-run share of time spent in each strategy.
import importlib.util, io, contextlib, math, pathlib
spec = importlib.util.spec_from_file_location(
    "p06", pathlib.Path(__file__).resolve().parent / "p06_markov_noise.py")
p06 = importlib.util.module_from_spec(spec)
with contextlib.redirect_stdout(io.StringIO()):
    spec.loader.exec_module(p06)

def fixation(A, i, j, N, beta):
    """Probability that one i-mutant takes over a population of j-players."""
    tot, prod = 1.0, 1.0
    for k in range(1, N):
        pi = ((k - 1) * A[i][i] + (N - k) * A[i][j]) / (N - 1)
        pj = (k * A[j][i] + (N - k - 1) * A[j][j]) / (N - 1)
        prod *= math.exp(-beta * (pi - pj)); tot += prod
        if prod > 1e300: return 0.0
    return 1 / tot

def rules(b, chi=3.0):
    # extortioner for the donation game (R, S, T, P) = (b - 1, -1, b, 0), Press-Dyson form
    # with phi chosen so that p_CD = 1/2: s_X = chi * s_Y against any opponent
    phi = 0.5 / (1 + chi * b)
    ext = (1 - phi * (chi - 1) * (b - 1), 0.5, phi * (b + chi), 0)
    return {"ALLD": (0, 0, 0, 0), "ALLC": (1, 1, 1, 1), "TFT": (1, 0, 1, 0),
            "GTFT": (1, 1 / 3, 1, 1 / 3), "WSLS": (1, 0, 0, 1), "EXTORT": ext}

def abundance(names, b, N, beta=1.0, eps=0.01):
    D, R = (b - 1, -1, b, 0), rules(b)
    A = [[p06.payoffs(R[x], R[y], eps, *D)[0] for y in names] for x in names]
    n = len(names)
    T = [[fixation(A, i, j, N, beta) / (n - 1) if i != j else 0 for i in range(n)]
         for j in range(n)]                        # T[j][i]: from all-j to all-i
    for j in range(n): T[j][j] = 1 - sum(T[j])
    v = [1 / n] * n
    for _ in range(200000):
        w = [sum(v[j] * T[j][i] for j in range(n)) for i in range(n)]
        if max(abs(x - y) for x, y in zip(v, w)) < 1e-14: break
        v = w
    return v

NAMES = list(rules(3.0))
print("long-run share of time (N = 100, beta = 1, error 1 %)")
print("  b/c   " + "  ".join(f"{k:>6s}" for k in NAMES))
for b in (1.5, 2.0, 2.5, 3.0, 4.0, 6.0):
    v = abundance(NAMES, b, 100)
    print(f"  {b:3.1f}   " + "  ".join(f"{x:6.3f}" for x in v))
print("ALLD, ALLC, TFT, WSLS only (as in Imhof et al. 2007), b/c = 2.5 and 4:")
sub = ["ALLD", "ALLC", "TFT", "WSLS"]
for b in (2.5, 4.0):
    v = abundance(sub, b, 100)
    print(f"  b/c = {b}: " + ", ".join(f"{k} {x:.3f}" for k, x in zip(sub, v)))
print("population size and extortion, b/c = 3 (share of EXTORT; of ALLD)")
for N in (4, 10, 30, 100):
    v = abundance(NAMES, 3.0, N)
    print(f"  N = {N:3d}: EXTORT {v[5]:.3f}; ALLD {v[0]:.3f}; WSLS {v[4]:.3f}")
# long-run share of time (N = 100, beta = 1, error 1 %)
#   b/c     ALLD    ALLC     TFT    GTFT    WSLS  EXTORT
#   1.5    0.710   0.011   0.057   0.142   0.050   0.030
#   2.0    0.402   0.013   0.025   0.373   0.181   0.006
#   2.5    0.049   0.002   0.003   0.064   0.881   0.000
#   3.0    0.000   0.000   0.000   0.001   0.999   0.000
#   4.0    0.000   0.000   0.000   0.000   1.000   0.000
#   6.0    0.000   0.000   0.000   0.000   1.000   0.000
# ALLD, ALLC, TFT, WSLS only (as in Imhof et al. 2007), b/c = 2.5 and 4:
#   b/c = 2.5: ALLD 0.072, ALLC 0.004, TFT 0.007, WSLS 0.918
#   b/c = 4.0: ALLD 0.000, ALLC 0.000, TFT 0.000, WSLS 1.000
# population size and extortion, b/c = 3 (share of EXTORT; of ALLD)
#   N =   4: EXTORT 0.148; ALLD 0.307; WSLS 0.193
#   N =  10: EXTORT 0.036; ALLD 0.223; WSLS 0.380
#   N =  30: EXTORT 0.002; ALLD 0.069; WSLS 0.778
#   N = 100: EXTORT 0.000; ALLD 0.000; WSLS 0.999

In a population of 100 with 1 % errors, at b/c=1.5b/c = 1.5 the population spends 71 % of the time with always defect; at b/c=2b/c = 2 always defect and generous tit for tat each take about two-fifths (0.402 and 0.373), and win-stay, lose-shift 0.181; at b/c=2.5b/c = 2.5 win-stay, lose-shift takes 0.881, and for b/c≥3b/c \ge 3 nearly all the time. Comparing only always defect, always cooperate, tit for tat and win-stay, lose-shift reproduces the conclusion of Imhof, Fudenberg and Nowak (2007): below a critical benefit-to-cost ratio always defect is selected, above it win-stay, lose-shift, and tit for tat itself never predominates (Imhof et al. 2007).

The extortion strategy almost never appears in the population of 100 (0.000 at b/c=3b/c = 3); the smaller the population, the more common it is: 14.8 % of the time with 4 players and 3.6 % with 10. This agrees with Hilbe, Nowak and Sigmund (2013): extortion can gain an advantage in small populations but not in large ones (Hilbe et al. 2013). In the same year Stewart and Plotkin found that what is evolutionarily robust is the “generous” class of zero-determinant strategies; extortioners do badly against each other (Stewart and Plotkin 2013).

Left: in the donation game with b = 3, c = 1, the long-run average payoff of three strategies against their own copies as a function of the error rate. Tit for tat earns only 1 at any positive error rate (full cooperation is 2); generous tit for tat and win-stay, lose-shift stay close to 2 for error rates below about 1 %. Right: in a population of 100 with 1 % errors, the long-run share of time the population spends with each strategy as a function of b/c.

Evidence

Experiments with people. In experiments on the repeated prisoner’s dilemma with execution errors, Fudenberg, Rand and Dreber (2012) found that participants sustained cooperation quite well, and that the most common successful strategies were “slow to anger and fast to forgive”: they did not retaliate at once against a single defection and returned quickly to cooperation (Fudenberg et al. 2012). Dal Bó and Fréchette (2018) surveyed a large body of experiments on infinitely repeated games: the higher the probability of continued interaction, the more cooperation; but cooperation being “possible” as an equilibrium is not enough, and the size of the basin of attraction of the defecting strategy predicts actual cooperation better (Dal Bó and Fréchette 2018). This matches the bottom-right panel of Figure 1.

Hypothesis · not established

Error-tolerance hypothesis (not yet established). The author conjectures that in long-term partnerships in which deliveries occasionally go wrong (late or wrong shipments), partners who agree in advance that “a first slip is discussed, not penalised” have a higher rate of continued partnership after a year than partners who agree that “every slip is penalised under the contract”, provided the error rate is below about 5 %; at high error rates the difference disappears. A testable prediction comes from prospective observation of many partnerships or from randomised simulation experiments. If the two kinds of agreement show no difference in survival, or strict penalties show higher survival, the hypothesis is refuted.

Chapter summary

Tit for tat won Axelrod’s two tournaments, but it never beats an opponent in a single match, and its ranking depends on the field. With execution errors two tit-for-tat players fall into a retaliation cycle and their long-run payoff drops to the average of the four outcomes. Generous tit for tat’s forgiveness has an upper limit min⁡{1−(T−R)/(R−S),(R−P)/(T−P)}\min\{1 – (T – R)/(R – S), (R – P)/(T – P)\}, which is 1−c/b1 – c/b in the donation game; win-stay, lose-shift is robust when b/c>2b/c > 2 and prevails in evolution. Zero-determinant extortioners never lose a match but are eliminated in evolution in large populations. Direct reciprocity needs the same pair to meet again and again; the next chapter turns to the case of helping someone one will never meet again.

References

Axelrod, Robert. 1980a. “Effective Choice in the Prisoner’s Dilemma.” Journal of Conflict Resolution 24 (1): 3–25. https://doi.org/10.1177/002200278002400101.
Axelrod, Robert. 1980b. “More Effective Choice in the Prisoner’s Dilemma.” Journal of Conflict Resolution 24 (3): 379–403. https://doi.org/10.1177/002200278002400301.
Axelrod, Robert, and William D. Hamilton. 1981. “The Evolution of Cooperation.” Science 211 (4489): 1390–96. https://doi.org/10.1126/science.7466396.
Dal Bó, Pedro, and Guillaume R. Fréchette. 2018. “On the Determinants of Cooperation in Infinitely Repeated Games: A Survey.” Journal of Economic Literature 56 (1): 60–114. https://doi.org/10.1257/jel.20160980.
Fudenberg, Drew, David G. Rand, and Anna Dreber. 2012. “Slow to Anger and Fast to Forgive: Cooperation in an Uncertain World.” American Economic Review 102 (2): 720–49. https://doi.org/10.1257/aer.102.2.720.
Hilbe, Christian, Martin A. Nowak, and Karl Sigmund. 2013. “Evolution of Extortion in Iterated Prisoner’s Dilemma Games.” Proceedings of the National Academy of Sciences 110 (17): 6913–18. https://doi.org/10.1073/pnas.1214834110.
Imhof, Lorens A., Drew Fudenberg, and Martin A. Nowak. 2007. “Tit-for-Tat or Win-Stay, Lose-Shift?” Journal of Theoretical Biology 247 (3): 574–80. https://doi.org/10.1016/j.jtbi.2007.03.027.
Kraines, David, and Vivian Kraines. 1989. “Pavlov and the Prisoner’s Dilemma.” Theory and Decision 26 (1): 47–79. https://doi.org/10.1007/BF00134056.
Molander, Per. 1985. “The Optimal Level of Generosity in a Selfish, Uncertain Environment.” Journal of Conflict Resolution 29 (4): 611–18. https://doi.org/10.1177/0022002785029004004.
Nowak, Martin A., and Karl Sigmund. 1992. “Tit for Tat in Heterogeneous Populations.” Nature 355 (6357): 250–53. https://doi.org/10.1038/355250a0.
Nowak, Martin, and Karl Sigmund. 1993. “A Strategy of Win-Stay, Lose-Shift That Outperforms Tit-for-Tat in the Prisoner’s Dilemma Game.” Nature 364 (6432): 56–58. https://doi.org/10.1038/364056a0.
Press, William H., and Freeman J. Dyson. 2012. “Iterated Prisoner’s Dilemma Contains Strategies That Dominate Any Evolutionary Opponent.” Proceedings of the National Academy of Sciences 109 (26): 10409–13. https://doi.org/10.1073/pnas.1206569109.
Stewart, Alexander J., and Joshua B. Plotkin. 2013. “From Extortion to Generosity, Evolution in the Iterated Prisoner’s Dilemma.” Proceedings of the National Academy of Sciences 110 (38): 15348–53. https://doi.org/10.1073/pnas.1306246110.
Trivers, Robert L. 1971. “The Evolution of Reciprocal Altruism.” The Quarterly Review of Biology 46 (1): 35–57. https://doi.org/10.1086/406755.

Fan, Y. (2026). Evolutionary Game Theory, Direct and Indirect Reciprocity and the Emergence of Cooperation: From Hamilton's Rule and Axelrod's Tournaments to Reputation and Costly Punishment, Read Beside Classical Confucian and Mohist Ethics [演化博弈、直接与间接互惠及合作涌现的数学模型] (Version 1.0.0). 5D Library. https://doi.org/10.5281/zenodo.23788551 · Licensed under Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International (CC BY-NC-ND 4.0).