Repeated Games and Learning Dynamics

"On the first round I defected and felt clever. By the thousandth round, surrounded by agents who remembered, I had learned to say hello."

An Agent That Discovered Tomorrow

The earlier sections of this chapter treated a game as a one-time event. Two agents meet, each reasons about the other, and they settle on an equilibrium such as the mutual defection of the Prisoner's Dilemma, which is grim but rational when you will never see your opponent again. That framing already carried us through representations (Section 28.3), cooperative coalitions, social welfare, and mechanism design. But it misses the defining feature of the systems this part of the book is about. A fleet of trading agents, a swarm of delivery robots, a market of bidding services, a population of language-model agents negotiating on a shared task: these do not meet once. They interact continuously, they remember, and crucially they change their behavior in response to what the others did. The static theory is the grammar; repetition and learning are where the sentences get written.

Two distinct ideas live in this section, and it helps to keep them apart. The first is repeated play with fixed, fully rational agents: the agents still reason about equilibria, but now over an infinite or unknown-length horizon, and the threat of future punishment expands what counts as equilibrium behavior. The second is learning dynamics: agents that are not computing equilibria at all, but adapting through trial, feedback, and regret, whose collective trajectory nonetheless converges toward the same solution concepts. The first explains why cooperation can be stable; the second explains how a population of adaptive agents actually reaches stable behavior. Both are the bridge into multi-agent reinforcement learning in Chapter 30.

1. Why Repetition Changes the Game Beginner

Recall the Prisoner's Dilemma payoff structure: each agent is tempted to defect because defection is the dominant move in a single encounter, yet both defecting leaves them worse off than both cooperating. In one shot, rationality and the bad outcome coincide. Now play the same game between the same two agents an indefinite number of times, with each agent valuing future payoffs through a discount factor $\delta \in [0, 1)$, so that a reward $r$ received $t$ rounds from now is worth $\delta^t r$ today. The total value of a strategy is the discounted sum $\sum_{t=0}^{\infty} \delta^t r_t$. The single move is unchanged, but the strategic object is no longer a choice of action; it is a choice of plan, a rule that maps the entire history of play to the next move.

This is what opens the door to cooperation. Suppose both agents adopt the rule "cooperate as long as the other has always cooperated; defect forever the moment they defect." If you defect once, you gain the one-round temptation payoff, but you forfeit every future round of mutual cooperation, trading a stream worth roughly $\frac{R}{1-\delta}$ for a one-time gain followed by the punishment stream. When $\delta$ is large enough, that trade is a loss, so cooperation is each agent's best response to the other. Cooperation has become a Nash equilibrium of the repeated game without changing a single payoff in the underlying game. The only new ingredient is a shared future worth protecting, captured entirely by $\delta$.

2. The Folk Theorem and Tit-for-Tat Intermediate

The observation that cooperation can be an equilibrium generalizes dramatically. The Folk Theorem states that in an infinitely repeated game with sufficiently patient players (discount factor close enough to one), essentially any outcome in which each agent earns at least its guaranteed worst-case payoff can be sustained as a Nash equilibrium of the repeated game. The agent's worst-case guarantee is its minmax value, the most it can secure when every other agent ganks it:

and the theorem says any payoff profile giving every agent strictly more than its $\underline{v}_i$ is reachable as an equilibrium, supported by the threat that any deviator gets minmaxed forever after. The name is a piece of discipline humor: the result was folklore, known and used before anyone published a careful proof.

The Folk Theorem is a double-edged sword. Its optimistic reading is that cooperation is not a fragile accident but a robust possibility, sustainable by patient agents who can punish. Its sobering reading is that the repeated game has a staggering multiplicity of equilibria, almost any outcome at all, so equilibrium analysis alone no longer predicts what agents will actually do. Something must select among the equilibria, and that selection is exactly what learning dynamics provide.

Tit-for-Tat is the canonical reciprocal strategy, and its tournament dominance is the empirical companion to the Folk Theorem: simple reciprocity, with no model of the opponent and no equilibrium computation, is enough to sustain cooperation against a wide field of strategies. Our runnable demo below reproduces the round-robin and confirms that reciprocal strategies finish at the top. Reciprocity also generalizes: variants that forgive occasional mistakes (Generous Tit-for-Tat, win-stay-lose-shift) outperform strict Tit-for-Tat once moves are noisy, a foreshadowing of the noisy, partially observed worlds that Chapter 29 agents inhabit.

3. Agents That Adapt Instead of Compute Intermediate

Computing a Nash equilibrium is hard in general, and worse, it presumes every agent knows the full game and trusts the others to be equally rational. Real agents rarely enjoy that luxury. So instead of computing an equilibrium, they learn one: they keep a running record of what worked, adjust their behavior toward it, and let the equilibrium emerge from the dynamics. Three update rules anchor this view, and each is a building block for the algorithms of Chapter 30.

Fictitious play. The simplest learner assumes its opponents play according to the empirical frequencies of their past moves, then best-responds to that belief. Each round it updates the frequency counts and best-responds again. In many important classes of games (zero-sum games, potential games), the empirical play of fictitious players converges to a Nash equilibrium. The weakness is that it needs a model of the opponent's action distribution and assumes that distribution is stationary, an assumption that fails precisely when the opponent is also learning.

Replicator dynamics. Borrowed from evolutionary biology, this view treats a strategy's share of a large population as growing in proportion to how much better than average it performs. Strategies that beat the population average spread; those below it die out. Replicator dynamics turns "which strategies are stable?" into "which population mixes are evolutionary fixed points?", and its rest points are closely tied to Nash equilibria. It is the natural language for the emergence of cooperation in a population: a small cluster of reciprocal cooperators can invade and take over a population of defectors when interactions repeat, which is the formal version of why Tit-for-Tat spread through Axelrod's later evolutionary tournaments.

No-regret learning. The most powerful and most practical idea drops opponent modeling entirely. An agent measures its regret: how much better off it would have been had it always played some fixed action instead of what it actually did. Formally, after $T$ rounds the regret for action $a$ is

the cumulative gain from substituting $a$ in every round, where $a^{-}_t$ is what the others did at round $t$. An algorithm is no-regret if its average regret $\max_a R_T(a) / T \to 0$ as $T$ grows: in the long run it does as well as the best single action chosen in hindsight. Regret matching achieves this with a strikingly simple rule: play each action with probability proportional to its accumulated positive regret. No model of the opponent, no equilibrium solve, just "do more of what you wish you had done."

4. A Tournament and a Convergence, From Scratch Intermediate

The demo below makes both ideas concrete in pure Python. Part A runs an Axelrod-style round-robin of the iterated Prisoner's Dilemma among five strategies, scoring each against every opponent (including itself) over 200 rounds, to show that reciprocity wins. Part B drops two regret-matching learners into Rock-Paper-Scissors, a zero-sum game whose unique equilibrium is the uniform mix, and tracks whether their time-averaged strategies converge to it. The first half illustrates Sections 1 and 2; the second illustrates the no-regret result of Section 3.

import random
random.seed(7)

# ----- Part A: iterated Prisoner's Dilemma round-robin -----
# Payoff to the row player. R=3 (both C), S=0, T=5, P=1 (both D): T > R > P > S.
PAYOFF = {('C','C'): 3, ('C','D'): 0, ('D','C'): 5, ('D','D'): 1}

def always_c(me, opp):      return 'C'
def always_d(me, opp):      return 'D'
def tit_for_tat(me, opp):   return 'C' if not opp else opp[-1]   # copy last move
def grim(me, opp):          return 'D' if 'D' in opp else 'C'     # never forgive
def random_player(me, opp): return random.choice(['C','D'])

STRATS = {'Tit-for-Tat': tit_for_tat, 'Always-Cooperate': always_c,
          'Always-Defect': always_d, 'Grim-Trigger': grim, 'Random': random_player}

def play(a_fn, b_fn, rounds=200):
    ha, hb, sa, sb = [], [], 0, 0
    for _ in range(rounds):
        a, b = a_fn(ha, hb), b_fn(hb, ha)
        sa += PAYOFF[(a, b)]; sb += PAYOFF[(b, a)]
        ha.append(a); hb.append(b)
    return sa, sb

ROUNDS = 200
totals = {n: 0 for n in STRATS}
for na, fa in STRATS.items():
    for nb, fb in STRATS.items():
        sa, _ = play(fa, fb, ROUNDS); totals[na] += sa

print("Iterated Prisoner's Dilemma round-robin (%d rounds/match)" % ROUNDS)
print("%-18s %10s %12s" % ("strategy", "total", "avg/round"))
for n in sorted(totals, key=totals.get, reverse=True):
    print("%-18s %10d %12.3f" % (n, totals[n], totals[n] / (len(STRATS) * ROUNDS)))

# ----- Part B: two regret-matching learners on Rock-Paper-Scissors -----
ACTIONS = ['R', 'P', 'S']
RPS = {'R': {'R':0,'P':-1,'S':1}, 'P': {'R':1,'P':0,'S':-1}, 'S': {'R':-1,'P':1,'S':0}}

def regret_match(reg):                       # strategy from positive regrets
    pos = [max(r, 0.0) for r in reg]; z = sum(pos)
    return [p / z for p in pos] if z > 0 else [1/3, 1/3, 1/3]

def sample(strat):
    r, c = random.random(), 0.0
    for i, p in enumerate(strat):
        c += p
        if r <= c: return i
    return len(strat) - 1

reg1, reg2 = [0.0]*3, [0.0]*3
sum1, sum2 = [0.0]*3, [0.0]*3
T = 20000
for _ in range(T):
    s1, s2 = regret_match(reg1), regret_match(reg2)
    for i in range(3): sum1[i] += s1[i]; sum2[i] += s2[i]
    a1, a2 = sample(s1), sample(s2)
    u1 = RPS[ACTIONS[a1]][ACTIONS[a2]]            # counterfactual regret update
    for i in range(3): reg1[i] += RPS[ACTIONS[i]][ACTIONS[a2]] - u1
    u2 = RPS[ACTIONS[a2]][ACTIONS[a1]]
    for i in range(3): reg2[i] += RPS[ACTIONS[i]][ACTIONS[a1]] - u2

avg1 = [x / T for x in sum1]
print("\nRegret matching on Rock-Paper-Scissors (T=%d)" % T)
print("player 1 time-averaged strategy: R=%.3f P=%.3f S=%.3f" % tuple(avg1))
print("equilibrium target             : R=0.333 P=0.333 S=0.333")
print("max deviation from uniform     : %.3f" % max(abs(p - 1/3) for p in avg1))

Iterated Prisoner's Dilemma round-robin (200 rounds/match)
strategy                total    avg/round
Grim-Trigger             2594        2.594
Tit-for-Tat              2445        2.445
Always-Defect            2204        2.204
Always-Cooperate         2127        2.127
Random                   1914        1.914

Regret matching on Rock-Paper-Scissors (T=20000)
player 1 time-averaged strategy: R=0.332 P=0.334 S=0.335
equilibrium target             : R=0.333 P=0.333 S=0.333
max deviation from uniform     : 0.001

The two results are the chapter's two halves in miniature. The tournament shows why cooperation is sustainable: strategies that reciprocate beat strategies that exploit, exactly as the Folk Theorem and Axelrod predict. The convergence shows how adaptive agents find equilibrium: by minimizing regret, not by computing a fixed point. Reference Figure 28.7.1 alongside the output, the left panel is Part A's logic, the right panel is Part B's trajectory.

# pip install axelrod
import axelrod as axl
players = [axl.TitForTat(), axl.Cooperator(), axl.Defector(),
           axl.Grudger(), axl.Random()]
results = axl.Tournament(players, turns=200, repetitions=5).play()
print(results.ranked_names)        # reciprocal strategies rank at the top

# pip install open_spiel  -> regret-matching / CFR equilibrium solvers
# from open_spiel.python.algorithms import cfr
# solver = cfr.CFRSolver(pyspiel.load_game("kuhn_poker"))

5. Why This Matters for Multi-Agent AI Advanced

The reason this section closes the chapter, rather than sitting as an afterthought, is that real multi-agent AI systems are not agents computing equilibria; they are agents learning against each other. Every agent's policy is changing as it learns, which means that from any single agent's point of view the environment is non-stationary: the rules of the world (the behavior of the others) shift underneath it precisely because the others are adapting too. This is the central difficulty that makes multi-agent reinforcement learning fundamentally harder than the single-agent case, where the environment holds still while the agent learns. We name it here because it is a direct consequence of the learning dynamics above, and we hand it forward to its full treatment in Chapter 30, where moving-target learning, opponent modeling, and convergence guarantees are the main event.

Non-stationarity is also why the convergence results of Section 3 are so valuable: they are among the few guarantees that survive when everyone learns at once. No-regret learning converging to correlated equilibria, and fictitious play converging in zero-sum and potential games, are the theoretical anchors that keep multi-agent learning from being pure empirical guesswork. They tell us which classes of multi-agent problems are tractable and which are not, and they connect the practical RL infrastructure of Chapter 20, the actor-learner machinery that runs self-play at scale, to the equilibrium concepts that say what that self-play is converging toward.

6. Chapter Summary and What Comes Next Beginner

This section completes Chapter 28, which assembled the game-theoretic foundation that the rest of Part VI stands on. We can now state that foundation as one connected story.

From here the book turns from foundations to systems. Chapter 29 builds multi-agent systems proper, agent architectures, communication, coordination, negotiation, coalition formation, and consensus, applying this chapter's equilibria and mechanisms to real coordination protocols. Chapter 30 then makes the learning explicit, lifting repeated normal-form games to Markov games and confronting head-on the non-stationarity that Section 5 named. The reciprocity, regret, and equilibrium-selection ideas you met here are the seeds of those chapters; watch for them returning as reward shaping, centralized-training-decentralized-execution, and opponent modeling.