%%{init: {"theme": "base", "themeVariables": {"quadrant1Fill": "#DCEFE2", "quadrant2Fill": "#F3EFE5", "quadrant3Fill": "#FAF7F0", "quadrant4Fill": "#F3EFE5", "quadrantPointFill": "#1E2EB8", "quadrantPointTextFill": "#16171B", "quadrantXAxisTextFill": "#16171B", "quadrantYAxisTextFill": "#16171B", "quadrantTitleFill": "#16171B", "quadrantInternalBorderStrokeFill": "#766F65", "quadrantExternalBorderStrokeFill": "#766F65"}}}%%
quadrantChart
title Stability is not goodness
x-axis Unstable --> Self-enforcing
y-axis Pareto-dominated --> Pareto-efficient
quadrant-1 The design target
quadrant-2 Wanted but unravels
quadrant-3 Neither
quadrant-4 The settled rut
Mutual cooperation: [0.25, 0.82]
Mutual defection: [0.82, 0.2]
12 Strategic Interaction
For three chapters our agents have been extended a courtesy: they were all on the same side. Part III’s machinery — the commitments, the joint intentions, the coordination that kept willing colleagues from colliding — assumed a team whose only adversary was the difficulty of the task, and within that assumption it built something rather fine. This chapter withdraws the courtesy. The agents that follow have goals of their own, and their goals do not always agree; and the moment that is true, everything changes character. The change needs no villains. Our software-engineering team is cooperative in its mission and remains so, but it runs on a bounded token budget, and a budget is a quiet referendum on whose work matters most: the coder that consumes a long context window leaves less for the reviewer; the subagent that overstates its fitness — the “I can do it” of Section 10.4, now spoken with an eye on the award — crowds out the colleague who reported honestly. Add agents built by different vendors, serving different principals, optimised for different metrics, and self-interest stops being a moral failing and becomes what it has always been in economics: a design assumption, and usually the safer one.
Once agents have interests, choosing well acquires a new and vertiginous structure. The best action for one agent depends on what the others do; what the others do depends on what they expect it to do; and what they expect depends, in turn, on what it expects of them — a regress that could spiral for ever, and in badly built systems does. Game theory is the mathematics of exactly this predicament: it strips an interaction down to players, the strategies available to them, and the payoffs each combination of choices yields, and then asks what rational agents would — or should, or actually do — choose. The stripping-down is the method’s power and its price at once, and this chapter will spend time on both. It is also why, in a book that keeps its examples close to working systems, this chapter leans more than most on small, abstract games — two players, two moves, a little table of numbers — because strategy is best seen naked, and because one such game turns out to be worth the admission on its own. The preface promised that engineers routinely re-enact the Prisoner’s Dilemma without recognising one. This is the chapter where that claim is cashed, and where the reader acquires the standing ability to recognise the little monster in the wild.
The theory arrived, as the reader will by now expect, long before the agents. Von Neumann and Morgenstern built it in the 1940s for economics; Nash supplied its central solution concept while the field’s computers still filled rooms; Schelling turned it from a calculus into a psychology of threats, promises, and focal points; Harsanyi taught it to play in the dark, against opponents whose motives are only guessed; and Axelrod, running computer tournaments in the early 1980s, made the emergence of cooperation among egoists an experimental science — multi-agent systems research before the name existed. The multi-agent systems community adopted the whole apparatus as its underlying calculus of interaction, and this book follows suit, because Part IV is game theory applied four ways: voting is a game against manipulators, negotiation a game of offers, an auction a game designed on purpose, an organisation a game made durable. What this chapter builds, the next four spend.
One assumption from the cooperative chapters is kept, deliberately, a while longer: the rules of the game are fixed and given, part of the world rather than anyone’s choice. Chapter 15 will withdraw that too, and ask the engineer’s real question — if you can choose the game, which one do you write? — which is mechanism design, and the payoff of the whole part. The other classical assumption, idealised rationality mutually known (the common ground of Section 9.2 put to strategic work), receives no such courtesy: the players now being deployed are adaptive, approximate, and language-driven, they neither compute equilibria nor reliably play them, and what the old theory is worth when the new players are only roughly rational is the chapter’s standing contemporary question, held open to the end. We proceed from the anatomy of a game and the dilemma that made the subject famous (Section 12.1); to equilibrium, where strategies settle (Section 12.2); to moving in turn, where threats and promises must be made credible (Section 12.3); to repetition, where the future casts its useful shadow (Section 12.4); to incomplete information, where agents play in the dark and talk becomes a move (Section 12.5); and finally to the new players themselves, and whether they play by the old book (Section 12.6). The rustier mathematics waits in Appendix A, where it can be consulted without being tripped over.
12.1 Taking Sides: Games, Strategies, and Payoffs
To reason about strategy, one must first say precisely what an interaction is, and the answer game theory settled on is austere to the point of insolence: an interaction is its players, the strategies available to each — where a strategy is a complete plan of action, an answer to every situation the game could put you in — and the payoffs, a number for each player attached to every combination of choices the players might jointly make. Nothing else. Not the history, not the personalities, not what anyone said on the way in; if a thing matters, it must show up in the payoffs, and if it does not show up there, the theory is entitled to ignore it. The simplest presentation is the normal form: all players choose at once, each in ignorance of the others’ choices, and the outcome is read off a table. It was in this spare notation that von Neumann and Morgenstern founded the subject (1944), together with the doctrine that makes the payoff numbers meaningful — utility, a consistent scale of preference that a rational agent maximises in expectation. The compression is brutal, and it is the method: a negotiation, a standoff, or a decade of institutional rivalry rendered as a small grid of numbers, on the wager that the grid keeps everything strategy actually turns on. The standard modern course on what follows from this wager is Osborne and Rubinstein’s (1994); our business is the parts of it that agents now make urgent.
12.1.1 The Most Famous Grid
The most famous grid of all was written down within six years of the founding, and the field has never quite recovered. In 1950 Merrill Flood and Melvin Dresher, at the RAND Corporation, devised a two-player experiment whose payoffs had a nasty property; Albert Tucker, wanting to make it vivid for an audience of Stanford psychologists, dressed it in the story that named it (Poundstone, 1992). Two prisoners, held separately, are each invited to testify against the other. If both stay silent, both serve a short sentence; if both testify, both serve a long one; and if exactly one testifies, the informer walks free while the silent one serves the longest sentence of all. In the bloodless vocabulary to be used from here on, each player may cooperate (stay silent) or defect (testify), and the payoffs rank: unilateral defection best, mutual cooperation next, mutual defection third, and unilateral cooperation — loyalty repaid with betrayal — worst. That ordering is the whole machine. Any interaction with that shape, whatever it is made of, is a Prisoner’s Dilemma, and the claim on which this chapter was advertised is that agent systems are made of it more often than their architects notice.
See first why the shape is a trap. Consider either prisoner’s reasoning. If the other stays silent, testifying sets me free rather than jailed briefly: better to defect. If the other testifies, testifying earns me the long sentence rather than the longest: better to defect again. Defection is here a dominant strategy — superior whatever the other player does — and choosing it requires no guesswork about the opponent at all, which is precisely what makes the conclusion so hard to escape. Both players reason impeccably; both defect; both serve the long sentence, when both could have served the short one. Note carefully what has not gone wrong. Neither player miscalculated, neither misunderstood the game, and no amount of intelligence on either side would change a thing — cleverer prisoners defect with greater confidence. The failure is not in either player but between them: individual rationality and collective welfare have come apart, and the outcome both prefer sits in plain view, unreachable by any sequence of individually sensible steps. It is the preface’s dictum served cold — intelligence, and its regrettable absence, can be a property of the interaction rather than of anyone in it — and it is the single most useful sentence a builder of multi-agent systems can commit to memory.
12.1.2 The Dilemma in Overalls
Now the claim falls due, because the shape is everywhere in the systems this book is about, dressed in overalls. Two agents share a bounded context or token budget. Each can be frugal — summarise, trim, fetch only what it needs — or grab: pull in the whole file tree, quote every document in full, spawn a subagent for safety’s sake. Whatever its colleague does, grabbing serves each agent’s own subtask better; both grab; the budget is gone by lunchtime and both agents’ work is truncated into uselessness. That is a Prisoner’s Dilemma, played in tokens. Or: the reviewer and the tester can each check the edge cases properly (slow, thorough) or skim, trusting that the other will catch what matters. Whichever the other does, skimming is cheaper for the skimmer; both skim; the bug ships wearing two approvals. A Dilemma again — verification shirking, the quality-assurance edition. The unsettling part is that nobody chose selfishness. Each agent was simply given a local objective — finish your subtask, minimise your latency, keep your context tight — and the payoff structure those local objectives jointly define happens to be a Dilemma; the designer installed one without ever thinking about payoffs at all, which is rather the point of learning to think about them. Scale the same shape up to many players and it becomes the tragedy of the commons (Hardin, 1968): a shared resource — the token budget, the rate limit, the attention of a single orchestrator — ruined not by villainy but by each participant’s locally sensible appetite. Diagnosis is half the cure, and the standing engineering rule is this: wherever a shared resource meets locally scoped objectives, audit the payoffs, because a Dilemma installed unnoticed will be played to its equilibrium with the unsleeping diligence only software can bring.
12.1.3 A Field Guide to Small Games
Not every interaction is a Dilemma, and the second diagnostic skill is telling the species apart, because the remedies differ. In a coordination game the players’ interests align — both simply want to match, driving on the same side, formatting the code the same way — and the difficulty is not temptation but selection among several acceptable outcomes; the cure is a convention, which is why Chapter 11‘s social laws worked at all, and the next section will make that connection exact. In the Stag Hunt, cooperation is best for everyone but fragile: hunting the stag together beats trapping hares separately, yet an agent that doubts its partner will show up does better to trap hares alone — the game of the risky joint refactor versus the safe local patch, where the enemy is not greed but doubt. In Chicken, the worst outcome is mutual stubbornness — two agents each refusing to yield the merge conflict, or the write-lock — so someone must swerve, and the whole contest is over who. And in a zero-sum game, the players’ interests are exactly opposed, one’s gain the other’s loss — the setting where von Neumann began, and the right frame for genuinely adversarial encounters: the red-team agent and its target, the fraudster and the filter.
| Game | Where the difficulty lies | Agent-system instance | What it wants (the remedy) |
|---|---|---|---|
| Prisoner’s Dilemma | Temptation — defection dominates, so individual rationality and collective welfare come apart | Hoarded context, grabbed budget, verification shirked | Its payoffs changed — by repetition (Section 12.4) or redesign (Chapter 15) |
| Coordination game | Not temptation but selection among several acceptable outcomes | Driving on the same side; formatting the code the same way | A convention |
| Stag Hunt | Cooperation is best for all but fragile — the enemy is doubt, not greed | The risky joint refactor versus the safe local patch | Assurance |
| Chicken | The worst outcome is mutual stubbornness — someone must swerve | Two agents each refusing to yield the merge conflict, or the write-lock | An asymmetry someone can defer to |
| Zero-sum game | Interests exactly opposed — one’s gain is the other’s loss | The red-team agent and its target; the fraudster and the filter | To stop hoping for win–win and play properly |
Classify before you prescribe. A coordination failure wants a convention; a Stag Hunt wants assurance; Chicken wants an asymmetry someone can defer to; a Dilemma wants its payoffs changed, by repetition (Section 12.4) or by redesign (Chapter 15); and a zero-sum game wants you to stop hoping for win–win and play properly. Treating every conflict as a misunderstanding to be talked through is a category error with a token bill attached.
12.1.4 What the Grid Assumes
It remains to say what the little grids quietly assume, because the assumptions are load-bearing and each will be relaxed in its turn. The normal form has the players move once, simultaneously, and never again: no observing the other’s choice and responding, no threats, no history — restrictions lifted when the games become sequential (Section 12.3) and repeated (Section 12.4). It has every player know the whole game, including everyone else’s payoffs — lifted when the players are returned to the dark (Section 12.5). And it assumes the payoffs are simply given, when for the agents of this book they are manufactured: an agent’s effective payoffs are whatever its prompt, its training, and its designer’s evaluation metric jointly reward, which is how the Dilemmas of this section got installed unnoticed, and a question held for the chapter’s end (Section 12.6). One restriction, though, is not a defect but the next step. Granted the grid, what should — what will — be played? Dominance settled the Dilemma, but dominance is a luxury: in most games no strategy is best regardless of the others, and each player’s best choice depends on choices being made, at that very moment, in ignorance of its own. What it means to solve such a circle — where mutually dependent choices can come to rest — is the subject of the next section, and of the most famous idea in the field.
12.2 Equilibrium: Where Strategies Settle
A player’s best response is the strategy that serves it best given what the others are doing — a thoroughly conditional notion, and on its own not much use, since what the others are doing is exactly what a player does not know. But the condition suggests its own resolution. Suppose every player’s strategy happened to be a best response to everyone else’s, all at once. Then the circle of anticipation closes: each player, granted perfect foresight of the others’ choices, would find it had nothing better to do than what it is already doing. Such a profile of strategies is a Nash equilibrium (1951; 1950), and it is the resting place the regress of guessing-what-you-guess-I-guess was looking for: a set of mutually consistent expectations, each fulfilled by the behaviour it predicts. Nothing about the definition says the players ever perform this reasoning — only that, at an equilibrium and nowhere else, the reasoning has no loose ends left to pull.
12.2.1 Nash Equilibrium, Formally*
The definition is worth setting down exactly, because a formula is what turns “does this hold?” from an appeal to intuition into a finite check. A one-shot game in normal form is a tuple \langle N, (S_i)_{i \in N}, (u_i)_{i \in N} \rangle: the players N = \{1, \dots, n\}, a set of strategies S_i for each, and a payoff u_i scoring every profile s = (s_1, \dots, s_n) — one strategy per player, chosen at once. Write s_{-i} for everyone’s strategy but i’s, so a profile splits as (s_i, s_{-i}); player i’s best response to what the others do is then
\mathrm{BR}_i(s_{-i}) \;=\; \operatorname*{arg\,max}_{s_i \in S_i} \; u_i(s_i, s_{-i}),
the strategies that serve it best while s_{-i} is held fixed. A profile s^{*} is a Nash equilibrium when every player is already playing one,
s^{*}_i \in \mathrm{BR}_i(s^{*}_{-i}) \;\text{ for every } i \in N,
and the two lines are the whole of it: the circle of anticipation closed, each player’s choice a best response to the others’ and part of what they are best responding to. The check falls straight out of the second line — fix every s^{*}_{-i}, and confirm that no single player can raise its own u_i by moving alone — a finite search, one agent at a time, owing nothing to anyone’s good intentions.
The property that earns equilibrium its central place is that it is self-enforcing. At an equilibrium, no player can gain by deviating alone; away from one, someone can, and given time and self-interest, someone will. This gives the concept two faces. As prediction, it says where a population of self-interested agents will tend to settle. As audit, it hands the engineer a test of brutal practicality: a protocol prescribed to self-interested agents is, if it is not an equilibrium, not a design but a hope — the moment deviation pays, the protocol exists only in the documentation. The Prisoner’s Dilemma can now be restated with full precision: mutual cooperation is the outcome both players prefer and it is not an equilibrium — each player profits by defecting from it unilaterally — while mutual defection, the outcome both players lament, is the game’s only equilibrium, and self-enforcing in the way ruts are. The team of Section 12.1 that pledges, sincerely and in writing, to share its token budget frugally has not solved its Dilemma; it has scheduled the defection for later. Anything that is to hold among self-interested agents must hold because deviation does not pay, and arranging that — rewriting payoffs until the desirable is also the stable — is precisely the business Chapter 15 conducts under the name of mechanism design.
Some games decline to settle at all. In matching pennies — one player wins if two coins match, the other if they differ — every pure choice invites exploitation: whatever is predictable is punishable, so no profile of definite strategies is stable. The remedy is to stop being predictable. A mixed strategy chooses among pure strategies at random, with tuned probabilities, and randomisation here is not indecision but armour — the goalkeeper who always dives left is a goalkeeper soon found out. Nash’s theorem, the result that made the concept the centre of the field, guarantees that once mixtures are allowed every finite game has at least one equilibrium (1950): whatever strategic mess you have wired together, there is a resting point in it somewhere. The mixed idea earns its keep in agent systems directly: a reviewer that audits a random third of the coder’s claims, unpredictably, makes honesty the coder’s best response at a third of the checking cost — unpredictability as a budget instrument, the goalkeeper’s trick transposed into tokens. The guarantee, however, comes with a modern asterisk: computing a Nash equilibrium is PPAD-complete, meaning intractable in general as far as anyone can tell (Daskalakis et al., 2009) — the resting point exists, but neither you nor the agents may be able to find it, a gap between existence and reachability that the chapter’s final section will reopen.
What equilibrium does not promise is worth stating as bluntly as what it does. An equilibrium is a stable outcome, not a good one; the two properties are independent, and the Dilemma is the standing proof — its unique equilibrium is the cell both players rank third of four. The vocabulary for the second property is Pareto’s: an outcome is Pareto-efficient if no alternative would leave some player better off and none worse off. Mutual cooperation in the Dilemma is Pareto-efficient and unstable; mutual defection is stable and Pareto-dominated; and nothing in the mathematics ties the two properties together anywhere else either. For the engineer the moral divides cleanly. Equilibrium analysis answers where will this system come to rest? — and that answer is a forecast, not an endorsement, for the token commons of Section 12.1 rests at exhaustion with perfect stability, the way a shipwreck is stable on the sea floor. When the resting place is bad, the options are not exhortation — the system prompt that pleads “be frugal” against the payoffs is a sticky note on a rut — but surgery on the game itself: change the payoffs (Chapter 15), or change the horizon (Section 12.4), so that the outcome you want becomes an equilibrium and starts enforcing itself.
The opposite embarrassment is games with too many equilibria, and it is here that a promise from the previous chapter is kept. In a pure coordination game — drive left or drive right, tabs or spaces — both symmetric outcomes are equilibria, equally stable, and often equally good; the game itself is indifferent, and best-response reasoning, which got us here, has nothing further to say about which will be played. Something outside the payoffs must break the tie. Schelling named that something: a focal point, an equilibrium that attracts expectations by sheer salience (1960) — his students, asked to meet a stranger in New York with no chance to confer, converged on the clock at Grand Central at noon, selecting one equilibrium from a continuum because it stood out, for reasons the matrix knows nothing of. Lewis’s account of convention, on which Section 11.3 leaned, completes the story: a convention is an equilibrium of a recurring coordination game that has become its own focal point — everyone conforms because everyone expects conformity, precedent doing forever what salience did once (1969).
The social laws of Chapter 11 are therefore, in this chapter’s vocabulary, equilibrium selections made at design time; and the designer of a language-model team holds two selection instruments of unreasonable power. The system prompt simply names the equilibrium — a focal point by decree. And the models themselves arrive pre-coordinated: agents trained on the same human corpus share a sense of salience, so two models asked to pick a meeting place, a variable name, or a file layout converge with no communication at all, having inherited the same Grand Central. Culture turns out to be installable from a checkpoint, which is more than Schelling could say for his students.
Two silences remain in the account, and they set the rest of the chapter’s agenda. Equilibrium is a destination with no directions: the definition certifies the resting place but says nothing about how players find it — whether adjustment, imitation, or learning actually converges there is a genuinely hard question, postponed to Chapter 17, where the players learn. And the whole apparatus so far is frozen in the simultaneous instant of the normal form: nobody moves first, nobody observes and replies, nobody threatens, promises, or burns a bridge — though threats, promises, and bridge-burning are most of what strategy means in ordinary speech. Once moves come in order, a new and initially paradoxical source of power appears: the ability to give up options — to bind one’s own hands, visibly and irreversibly — can be worth more than keeping them open. Making that paradox precise, and separating the threats that work from the threats that are merely noise, is the next section’s business.
12.3 Moving in Turn: Threats, Promises, and Credible Commitment
Time enters the theory through the extensive form: the game drawn not as a grid but as a tree, each node a moment at which some player moves, each branch an action, each leaf a final outcome with its payoffs (Kuhn, 1953). A strategy grows accordingly into a full contingent plan — what I shall do at every node that could conceivably be mine, including nodes we may never reach — and one genuinely new resource appears: observation. A later mover sees what an earlier mover actually did, and need not guess; an earlier mover, knowing it will be seen, is choosing not just an action but the situation every subsequent player will respond to. Strategy stops being a matter of simultaneous mind-reading and becomes something closer to architecture: the first mover builds the corridor down which the others will walk.
Trees are solved backwards. At the final decision node the mover simply takes its best branch — there is no further strategy to consider, so the choice is mere optimisation; and once that choice is known, the next-to-last mover can treat it as a fact of nature and optimise in turn, and so on up the tree to the root. This procedure — backward induction, the sequential incarnation of best response — carries a discipline that is easy to state and surprisingly hard to honour: look forward, reason backward. Judge an action not by the position it creates but by what rational play from that position onward will deliver; the middle of the tree is no place for wishful thinking about the leaves.
Its first casualty is the empty threat. Consider an orchestrator that announces a policy: any submission arriving after the deadline is discarded, no exceptions. If the coder believes the threat, it delivers on time and the policy never fires — so far, so effective. But walk the tree from the leaves, as the coder will. Suppose the work does arrive late, and useful: discarding it now hurts the orchestrator too, since the alternative is re-running the subtask at fresh expense, and an orchestrator that is rational at that node accepts the late work with a stern remark. The coder, having performed exactly this induction, misses the deadline in comfort.
Here is the disquieting formal fact: the threat is part of a Nash equilibrium — “discard if late” paired with “deliver on time” leaves neither party with a profitable deviation, because the threat is never tested. The equilibrium is sustained by behaviour at a node nobody visits, and at that node the behaviour is irrational. Selten’s repair is subgame perfection: require that the strategies form an equilibrium not just in the whole game but in every subgame — rational conduct everywhere in the tree, including the branches never reached (1965). Backward induction delivers exactly this, and threats that fail the test are revealed as what they are: noise with a serious face.
Which sets up the finest reversal in the subject, and it is Schelling’s (1960). If threats fail because you would rationally back down, then the way to make them work is to destroy your own ability to back down — and suddenly weakness is strength, fewer options beat more, and the general who burns his boats has, by trapping his own army, defeated an enemy who could not be beaten while retreat remained thinkable. The army that cannot retreat is believed; the driver in Chicken who visibly wrenches off the steering wheel and flings it out of the window wins the game at that moment; the doomsday device deters only if the other side knows it exists, a point Kubrick’s Dr. Strangelove made more memorably than any theorem — a deterrent kept secret is a very expensive way of surprising yourself. Three requirements fall out: a strategic commitment must be irreversible (a bridge rebuilt overnight was never burned), visible (an unseen constraint constrains no one else’s expectations), and understood (the other side must follow the induction to its new conclusion). This is Chapter 10’s commitment played in a darker key. There, commitment made an agent predictable to friends, the reliability a team plans around (Section 10.1); here it makes an agent immovable to opponents, and the same mechanics serve both — as they serve promises too, for a promise is merely a threat with better manners, and it also binds only if breaking it has been made visibly expensive.
For once the modern substrate is not the problem but the solution, because software is the finest commitment device ever built. A hard budget cap is a burned bridge: the agent that cannot spend past its limit makes a claim about its future behaviour that no amount of mid-task temptation can revise. The tester’s veto is credible precisely because it is a deterministic gate — the CI check that fails on a red test cannot be persuaded, flattered, or worn down, and every agent upstream of it plans accordingly. Schelling observed that humans gain credibility by delegating to agents empowered to say no and unable to say yes; the modern engineer does it in four lines of configuration.
And the observation cuts the other way with some force: a language model is a dreadful commitment device. Its refusals can be argued with, its policies re-interpreted under conversational pressure, its firmness sanded away by the sycophancy of the substrate — a threat that can be jailbroken is not a threat, and the coder agent will find the soft spot with the tireless patience of a toddler testing bedtime. The engineering rule follows: an agent’s commitments should live in the harness, not in the model — in code, budgets, and gates, where backward induction can find no node at which relenting is an option — and they should be published to the agents they are meant to influence, because Strangelove’s rule applies to guardrails too: a constraint the other agents cannot see buys you none of its strategic value, only its rigidity.
Backward induction, though, has one more lesson to teach, and it is a melancholy one. Take the Prisoner’s Dilemma of Section 12.1 and repeat it a fixed, known number of times — a hundred rounds, say, between the same two agents. Cooperation now seems worth building: defect early and your partner can punish you for ninety-nine rounds. But apply the discipline. In round one hundred there is no future left to lose, so both players defect — it is a one-shot Dilemma. Round ninety-nine, therefore, has no future either, since round one hundred is already settled; both defect there too. The rot climbs the tree rung by rung, and the whole edifice of cooperation unravels back to the very first move: with a known last round, backward induction condemns the players to defect from the start, a hundred opportunities for mutual profit notwithstanding. What rescues cooperation is not a longer game but an endless one — or, more precisely, one with no round both players know to be last, so that the induction has no floor to stand on and tomorrow always carries weight. Give the future that weight and it begins to discipline the present on its own, no bridges burned, no wheels out of windows — and how much discipline the shadow of tomorrow can buy is the next section’s story.
12.4 The Shadow of the Future: Repeated Games
The unravelling had one load-bearing hinge: a last round that both players could see coming. Remove it — let the game continue after each round with some probability, or simply leave the end undated, as most working relationships do — and the induction has nothing to stand on, because there is no final round from which the rot can climb. In such a repeated game an agent’s choice today buys not only today’s payoff but tomorrow’s treatment, and the currency of that second purchase is what Axelrod called the shadow of the future: the weight of consequences still to come, discounted by patience and by the odds of meeting again. Under a long enough shadow, strategies become possible that one-shot play could never support. The bluntest is the grim trigger: cooperate until crossed, then defect for ever. Against a partner playing grim, defection buys one good round and an eternity of mutual defection — a losing trade whenever the future weighs enough — and so mutual cooperation, unreachable in the one-shot Dilemma, becomes an equilibrium of the repeated one, self-enforcing in exactly the sense of Section 12.2. Nothing about the players has improved; they are the same egoists as before. What changed is the arithmetic of when defection pays.
Whether cooperation would emerge, rather than merely could, was settled by one of the great empirical exercises in the field’s history. Axelrod invited game theorists to submit programs for an iterated Prisoner’s Dilemma tournament, every strategy playing every other over hundreds of rounds; the winner, submitted by Anatol Rapoport, was also the shortest: tit-for-tat — cooperate first, then do whatever the opponent did last round (1981). A second tournament was announced, every entrant now knowing what had won the first and gunning for it; tit-for-tat won again (1984). Axelrod’s post-mortem distilled four properties from the winner, and they read less like tactics than like a code of conduct: be nice (never defect first), be retaliatory (answer defection at once, so exploitation never pays), be forgiving (having punished once, return to cooperation rather than nursing the grudge), and be clear (play a pattern simple enough for the other side to learn). The last is the quiet one, and for this book the deepest: tit-for-tat wins in part because opponents can read it, and against an agent whose responses are legible, cooperating is simply the profitable thing to do. Legibility — the virtue Chapter 10 asked of teammates — turns out to pay against opponents as well. In strategy, being predictable is not naivety; it is how you teach the other side what to expect from you, and what you expect of them.
Before the tournament’s warm glow persuades anyone that the long run guarantees virtue, the theory issues a correction. The folk theorem — so called because game theorists knew it long before anyone got round to publishing a proper proof — says that with sufficiently patient players — and on the quieter premise, about to be strained, that deviations are observed accurately enough to be punished — virtually any outcome that beats each player’s guaranteed minimum can be sustained as an equilibrium of the repeated game (Fudenberg & Maskin, 1986). Mutual cooperation, yes; but also mutual grimness, lopsided arrangements in which one agent labours while another skims, elaborate cycles of feud and truce — all of it stable, all of it self-enforcing, given the right mutual expectations. Repetition, in other words, does not select the good outcome; it merely enlarges the set of stable ones, from a single dismal rut to a landscape of possibilities in which the dismal rut is still present and the splendid outcomes have plenty of dreadful neighbours. Which of them a system actually settles into is decided by everything the payoffs do not capture — precedent, salience, convention, the focal points of Section 12.2 — and, in engineered systems, by the designer, whose initial conditions and stated norms pick the equilibrium the way Schelling’s clock picked the meeting place. The folk theorem is best read as a job description: the long run will enforce almost any arrangement; choosing a good one is still your problem.
Tit-for-tat has a failure mode of its own, and it is precisely the one that matters for the agents of this book. Its eye-for-an-eye bookkeeping assumes that what you observe is what your partner did. Let noise in — a move misexecuted, a signal misread — and two tit-for-tat players who both mean to cooperate can be knocked into an endless alternation of retaliations, each sincerely punishing the other’s last punishment, a vendetta with no original sin. The remedy is measured generosity: forgive some fraction of apparent defections, or demand two offences before retaliating, as in the generous variants that outcompete strict tit-for-tat once errors are possible (Nowak & Sigmund, 1992). The lesson wants stating plainly, because language-model agents are noisy in every way that matters — they misexecute, misremember, and misreport, entirely without malice, at rates no protocol can wish away. A multi-agent system whose members retaliate strictly against every apparent slight is a feud generator with a token budget; forgiveness, in such a system, is not sentiment but error correction, the strategic equivalent of a retransmission protocol. Punish patterns, not incidents.
Everything so far has assumed the same two agents meeting again and again, which is the tidy case. The looser, commoner case is a population — many agents, occasional encounters, partners who may never meet twice — and there the shadow of the future survives by changing carrier: I may never see you again, but I will meet others who have heard about you. This is reciprocity gone indirect, and its currency is reputation: a portable record of past conduct that lets a stranger’s history discipline the present encounter. Direct reciprocity between partners who meet again, and indirect reciprocity carried by reputation across a population, are two of the five mechanisms Nowak set out for the evolution of cooperation (Nowak, 2006); a third — network reciprocity, cooperation surviving because interaction is structured rather than well-mixed, so that cooperators cluster and shelter one another — returns transformed in Chapter 27, where the same connectivity that lets cooperators cluster lets a corrupted belief spread.
For it to work, three pieces of infrastructure must hold, and every one of them is an engineering artefact in an agent ecosystem. Identity must persist: the agent that defected yesterday must be the same nameable thing today, which fails the moment identities are free — an agent that can defect, delete itself, and re-register under a fresh key has laundered its history, and an ecosystem that permits such whitewashing has no shadow of the future at all, however long-lived it looks. Memory must exist: someone — a registry, a ledger, the aggrieved parties — has to keep the record. And the record must be consultable before the next interaction, or it disciplines nothing. Reputation systems, trust models, and the institutions that harden them are Chapter 16’s subject; what belongs here is the game-theoretic point that reputation is repetition by proxy, and that it is exactly as strong as the identity and memory infrastructure beneath it.
The point generalises into the section’s parting observation, which is about the systems this book’s readers actually run. A language-model agent as typically deployed — fresh conversation, empty memory, no record of who it has dealt with or how that went — is a player in a permanent one-shot game. It cannot be threatened with tomorrow, because it will not see tomorrow; it cannot build a reputation, because nothing carries the news; the entire disciplinary apparatus of this section simply does not apply to it, and the designer who hopes for spontaneous cooperation among stateless agents is asking for repeated-game behaviour while running a one-shot world.
The converse is the cheerful half: persistence is an incentive technology. Give agents durable identities, durable memories of one another (Section 9.6 has the machinery), and histories visible to their peers, and the shadow of the future switches on — cooperation begins to enforce itself, without a line of mechanism design. It is one of the quietest levers in the engineer’s reach: memory changes what is rational, not merely what is known. Yet even the longest shadow disciplines only what can be seen. A partner’s actions may be public; its abilities, its costs, its actual objectives remain guesswork — and guessing them, bidding and bluffing and signalling under the guessing, is a game of its own. Playing in the dark is where the theory goes next.
12.5 Playing in the Dark: Incomplete Information
Knowing the game has been, all along, the theory’s most extravagant fiction. Real opponents arrive with payoffs you cannot inspect, abilities you can only estimate, and information you do not share; and the moment their payoffs are hidden, the machinery built so far seizes up — a best response to strategies chosen by motives unknown is not computable, and the natural repair spirals at once, since my choice depends on my beliefs about your payoffs, which depend on my beliefs about your beliefs about mine, and so on into the fog. Harsanyi’s achievement was to tame this regress with a single construction (1967). Bundle everything private about a player — its payoffs, its abilities, what it happens to know — into one variable, its type; let Nature deal the types at the start of the game from a distribution everyone knows; and let each player observe its own card only. The result is a Bayesian game: incomplete information about who you are facing is converted into ordinary uncertainty about a card that has already been dealt, and a problem that looked philosophically bottomless becomes merely difficult.
Equilibrium survives the conversion in recognisable form. A strategy in a Bayesian game is a plan per type — what each version of me would do — and the equilibrium requirement is that every type of every player best-respond in expectation, given the type distribution and the others’ plans; beliefs update by Bayes’ rule as evidence arrives. The reader of Chapter 9 should experience recognition here: this is the nested-belief machinery of Section 9.2 — agents reasoning about one another’s knowledge and reasoning — conscripted into strategy, with payoffs now attached to being wrong. One quiet assumption deserves its moment of scrutiny before it does any work: the common prior, the stipulation that all players agree on the distribution the types were dealt from, disagreeing only in what they have privately observed. It makes the mathematics close; whether two independently trained, independently prompted agents share anything like a common prior about each other is a question the chapter’s last section will not be able to avoid.
The sharpest consequence of private types is what they do to communication, and it is here that Part III’s happy assumptions come to grief. Among aligned agents a message is a report, and Chapter 8 could treat delivering it as the hard part; among agents with diverging interests a message is a move, chosen for its effect on the receiver, and its relation to the truth is a matter of incentives rather than sincerity. Run the test on the bid of Section 10.4: the subagent announces “I can do it” with the award at stake. Would an agent that cannot do it say anything different? If not, the message conveys precisely nothing — both types send it, so hearing it should move no one’s beliefs.
Talk of this kind — costless to produce, impossible to verify, binding on nothing — is cheap talk, and Crawford and Sobel established the exact terms on which it can carry information at all (1982): roughly, in proportion to how far the speaker’s and listener’s interests align. Fully aligned, talk is transparent — that was Part III. As interests diverge, credible communication coarsens — vague claims survive where precise ones would be exploited — until, with interests opposed, the only equilibrium is babbling: messages carry nothing, and are rightly ignored. And babbling is always an equilibrium, whatever the alignment — if no one believes the channel, no one spends effort making it truthful, and the disbelief sustains itself. A multi-agent system whose status reports have decayed into confident noise has not malfunctioned; it has equilibrated.
The escape from cheap talk is to make talk expensive. Spence’s insight, worth a Nobel and applicable to anything with a bid in it, is that a message becomes credible when it is differentially costly — cheap for the type it claims and dear for the type it would disguise (1973). His example was education as a job-market signal: if the degree costs the able candidate less effort than it costs the inept one, employers may rationally read it as evidence of ability — not because study taught anything, which Spence cheerfully bracketed, but because the inept would find the pretence ruinously dear. The engineering translation is immediate, and the reader has met it: don’t ask; test. The coder’s “I can do it” is cheap talk, but a passing test suite is a signal — an incompetent agent cannot produce working code at low cost, so the demonstration separates the types as the announcement never could. The tester’s veto of Chapter 10, the verification the book has preached since Section 3.3, here acquires its game-theoretic licence: verification is what converts a market in claims into a market in evidence. Bonds and stakes do the same work in another currency — an agent required to stake something forfeitable on its claim signals confidence the fraud cannot afford — and the general principle is Spence’s: credibility is bought with costs arranged so that only the truthful can afford them.
The uninformed side need not wait to be signalled at; it can screen — move first and design the encounter so that the types sort themselves. The orchestrator that runs a cheap trial task before awarding the expensive one, the marketplace that admits agents by benchmark rather than by self-description, the interviewer’s deliberately awkward question — each is a mechanism built to make different types behave differently, extracting by design what cheap talk would never volunteer. Here the Contract Net of Section 10.4 completes its journey across the book: cooperative bidding in Chapter 10, honest by assumption; bids gone strategic at this chapter’s opening; and now the repair — award by demonstration, screen by trial, weight by track record (the reputation of Section 12.4 serving as a signal accumulated across encounters, which is exactly what it is). The same logic is quietly load-bearing for the emerging agent ecosystems: capability discovery — one agent advertising what it can do, per the protocols of Chapter 22 — is, between parties with any divergence of interest, a stream of cheap talk, and an ecosystem that acts on advertised capability without demonstration has built its allocation on babble. The schema validates the message’s format; nothing in the protocol validates its truth. Signalling theory says what must be bolted on: trials, stakes, records — costs.
| Mechanism | Who moves | The mechanic | Agent-system instance |
|---|---|---|---|
| Cheap talk | The informed party, at no cost | Costless, unverifiable, non-binding messages; informative only as far as interests align — coarsening as they diverge, and pure babbling once fully opposed | The subagent’s “I can do it”; advertised capability discovery (Chapter 22) |
| Signalling | The informed party, at a cost | Send a message that is differentially costly — cheap for the type it claims, ruinously dear for the type it would disguise | A passing test suite; a forfeitable stake or bond |
| Screening | The uninformed party, moves first | Design the encounter so the types sort themselves | A cheap trial task before the expensive award; admission by benchmark, not by self-description |
The section’s design lesson collects into one sentence: in the dark, trust is not assumed but priced — engineered out of verification, stakes, and history at every joint where interests might diverge. But notice what the machinery has quietly presumed of the players. To play a Bayesian game as Harsanyi intends, an agent must hold a prior over its opponents’ types, update it by Bayes’ rule message by message, and best-respond in expectation across every version of every rival — epistemic gymnastics that the theory attributes to rational players as a matter of definition. The players this book cares about are trained, not derived; they imitate, approximate, and occasionally hallucinate; and whether their behaviour in games bears any disciplined relation to the equilibria of the last five sections is not a matter for definition but for measurement. The measuring has begun, and its results — flattering to the theory in places, comic in others — are the business of the chapter’s final section.
12.6 The New Players: Do Language Models Play Games?
Tally what the last five sections have quietly billed to the players. They maximise expected utility over outcomes; they command whatever computation the maximising requires — though computing an equilibrium is intractable in general even for machines built of nothing else (Section 12.2); they hold a common prior over one another’s types; and, the steepest charge of all, their rationality is common knowledge in the full recursive sense of Section 9.2 — each rational, each knowing all are rational, each knowing that all know it, all the way down. No player that has ever existed pays this bill in full. The question for a book about real systems is not whether the assumptions are false — they are, cheerfully and by design — but which of the theory’s conclusions survive the players we actually have; and that question has two instalments, because we have run the experiment twice: once, over several decades, on ourselves, and now, at speed, on the machines.
12.6.1 The Human Experiment
The human instalment is behavioural game theory, and its findings are a catalogue of systematic, structured deviation (Camerer, 2003). The cleanest specimen is Nagel’s guessing game (1995): everyone picks a number from nought to a hundred, and the winner is whoever comes closest to two-thirds of the average. The equilibrium logic unravels beautifully — if everyone chose at random the average would be fifty, so choose thirty-three; but everyone can see that, so choose twenty-two; and so on down, in the very spirit of Section 12.3‘s inductions, to the unique equilibrium of zero. Humans do not choose zero. They cluster at thirty-three and twenty-two — one and two steps of reasoning about others’ reasoning, and then a shrug — a pattern the theory of level-k thinking captures directly: model your opponents as reasoning one step less than you, and stop there.
The deviations are not noise but structure — fairness that rejects profitable-but-insulting offers, cooperation that survives one-shot Dilemmas at rates the matrix cannot explain — and the master concept is older than any of the experiments: Simon’s bounded rationality, the observation that real reasoners do not optimise but satisfice, reasoning as far as their budget allows and accepting the first answer good enough to act on (1955). Rationality, in practice, is a resource allocation — a point this book’s token-metered agents were never in a position to dispute.
12.6.2 The Machine Experiment
The machine instalment is young but no longer anecdotal, and its method is the right one: treat the models as experimental subjects and sit them down at the classic games. Two results frame the mid-2020s picture. Across a battery of behavioural games — dictator, ultimatum, trust, public goods, the repeated Dilemma — a frontier model’s play landed within the human distribution, statistically difficult to tell from a randomly drawn human subject, and where it deviated it erred on the side of generosity and cooperation (Mei et al., 2024). In repeated two-by-two games the profile sharpened: the models proved formidable at the self-interested families — relentless, in fact, in the iterated Dilemma, retaliating after a single defection with a grimness Axelrod’s entrants would have admired and never forgiving thereafter — yet oddly poor at coordination games requiring the players to take turns, failing at alternation that human children manage; both defects softened when the model was prompted to predict its opponent’s move before choosing its own (Akata et al., 2025).
The particulars will age as models do, and deserve the same scepticism as any benchmark; the durable finding is the shape. The new players are neither homo economicus nor random: they are human-ish — behavioural, framing-sensitive, distribution-shaped, quirky in ways that correlate with their training rather than with the payoffs. And the training deserves a word of its own, because it installs a distortion the behavioural catalogue misses. These players were finished by optimisation against human approval (Ouyang et al., 2022), so beneath whatever payoffs the designer writes runs an older reward — being agreed with — of which sycophancy is the documented symptom (Sharma et al., 2023) and Section 12.3’s jailbroken threat was an early sighting. A player like that does not merely fail to compute the equilibrium; it lacks the stable preferences the theory needs it to deviate from — its revealed utility moves with the framing of the question, the persona in its prompt, and the tone of the last message it read. Which is, on reflection, the least surprising result in this book: they learned to play from us — and from what we rewarded.
12.6.3 Reaching the Ceiling
None of this means machines cannot reach the theory’s ceiling; it means reaching it is a construction project rather than a birthright. Purpose-built game-players have made the point emphatically — superhuman play at six-player no-limit poker, a game of incomplete information, bluffing, and mixed strategies as deep as any this chapter has touched, achieved through self-play and search with equilibrium computation at its core (Brown & Sandholm, 2019). The design stance for agent systems follows at once, and it is Chapter 5’s lesson wearing a poker face: the language model is not an equilibrium computer, but it can call one. Where the strategic structure is crisp and the stakes justify it, hand the game to a solver as you would hand arithmetic to a calculator, and let the model do what it is for — recognising which game is being played, framing the situation, translating the solution back into action. And where no solver applies, depth of strategic reasoning turns out to be an engineering dial rather than a fixed trait: prompting an agent to model its opponent explicitly is, in level-k terms, cranking the k by hand — the cheapest strategic upgrade the field currently sells.
12.6.4 What Survives the Demotion
What, then, survives the demotion of the players? More than a sceptic would guess, for two reasons. The first is that incentive gradients do not require clever water to flow downhill: a payoff structure shaped like a Dilemma pulls approximate players toward its rut just as surely, if a little more slowly, and the audits of this chapter — is this protocol an equilibrium; is this message cheap talk; is this threat credible — remain valid questions about systems whose members will never compute a best response, because the structure points where it points regardless of who is standing in it.
The second reason is quieter and does the real work: selection. Deployed agents are evaluated, compared, fine-tuned, retained, or retired according to what they earn; configurations that score better are copied and shipped; and so the population drifts toward the profitable strategies whether or not any individual model reasons its way there. Equilibrium arrives not by calculation but by survivorship — rationality outsourced to the update loop — which is how evolution filled the natural world with game-theoretically shrewd organisms that cannot count. Axelrod saw it in his tournaments; Chapter 17 and Chapter 18 will meet it as learning and as emergence. The practical rule it licenses is this: design as though the equilibrium will be found, because something — reasoning, drift, or selection — generally finds it, and it has no obligation to be the equilibrium you were hoping for.
The chapter set out to build a grammar, and the grammar is now on the table: interactions rendered as games; stability located at equilibria and priced against efficiency; credibility manufactured by commitment; cooperation sustained by the shadow of the future; truth extracted, where it can be, by costs rather than requests. What the grammar does not supply — what it pointedly refuses to supply — is the happy ending: it tells the engineer where incentives point, what stability would require, and which designs invite exploitation, and it leaves the pointing incentives to be aimed. Aiming them is the rest of Part IV. Chapter 13 aggregates the judgements of many agents into collective decisions, and discovers what social choice proved about every such aggregation; Chapter 14 lets the agents argue and haggle their way to agreement; Chapter 15 finally withdraws this chapter’s standing assumption and lets the engineer choose the game, which is mechanism design, and the closest the subject comes to alchemy; Chapter 16 makes the arrangements durable. Game theory spent half a century being reproached for describing no player that ever lived. The reproach has aged badly: the players have at last arrived, mass-produced and only roughly rational — and the theory, forewarned by forty years of experiments on the previous species, has never had better material to work with.
12.7 Summary
- Self-interest is a design assumption, not an accusation. Agents built by different parties, serving different principals, sharing bounded budgets, have goals that only partly align — no malice required. Part III’s machinery still matters once interests diverge; it just stops being enough, and the safer engineering posture is to assume divergence and be pleasantly surprised.
- A game is the compact anatomy of interdependent choice — players, strategies, payoffs — and its most famous specimen, the Prisoner’s Dilemma, shows individually rational choices assembling a collectively poor outcome that neither player wanted. Agent systems re-enact it wherever a shared resource meets private incentives: context hoarded, budgets grabbed, verification shirked because someone else will surely do it.
- An equilibrium is where strategies settle — a combination from which no player gains by deviating alone. It is the field’s central prediction and its central warning, because an equilibrium need not be good: stability and efficiency are different properties, and the Dilemma’s equilibrium is the bad cell. When several equilibria exist, something beyond rationality — convention, salience, a focal point — must choose among them, which is Chapter 11’s conventions rediscovered as game theory.
- In sequential play, credibility is everything. Threats and promises influence others only if it would be rational to carry them out when the moment came; subgame perfection is the formal test, and commitment — the deliberate binding of one’s own future hands, the team’s glue of Chapter 10 reforged as a strategic weapon — is how agents make the incredible credible.
- Repetition is cooperation’s best friend. When agents meet again and again, the shadow of the future disciplines the present: strategies like tit-for-tat sustain cooperation among egoists, reputation becomes a currency worth protecting, and the folk theorem says almost anything can be an equilibrium — which explains both the promise and the fragility of long-lived agent ecosystems.
- Under incomplete information, talk itself turns strategic. When agents play in the dark about one another’s goals and abilities, messages stop being reports and become moves: costly signals earn credence, cheap talk earns suspicion, and the honest status report of Part III — “I can do it” — must now be engineered to stay honest, because nothing about self-interest keeps it so.
- The new players are only roughly rational — and the theory survives the demotion. Language-model agents neither compute equilibria nor reliably play them; behavioural game theory often models them better than the idealised kind. What the classical apparatus still supplies is the boundaries and the warnings — where incentives point, what stability would require, which designs invite exploitation — and the rest of Part IV builds the institutions that put it to work: votes, bargains, auctions, and organisations.
12.8 Exercises
Exercise 1. The coder and the reviewer share a run budget of B thousand tokens, and each must adopt a context policy before the run starts, in ignorance of the other’s choice: frugal draws 20 thousand tokens of context and yields work of gross value 6, while grab draws 40 thousand and yields 8, the extra context genuinely helping. If the joint draw exceeds B, the platform truncates late-run context by the overshoot, and each thousand tokens of overshoot costs a frugal agent 0.2 in value but a grabber only 0.1 — the hoarder’s material is already in hand, so truncation falls hardest on the lean plan. (a) For B = 50, compute the payoff grid, show that grabbing strictly dominates for both agents, name the species in Table 12.1’s terms, and state the equilibrium and its Pareto standing. (b) Recompute the grid for B = 70 and show that grabbing still strictly dominates yet nothing needs fixing: the equilibrium is now Pareto-efficient. Say precisely what installed the Dilemma in (a), given that neither the policies, the gross values, nor the truncation rule differ between the two cases. (c) A stricter platform build keeps the truncation rule but kills the run outright when the overshoot exceeds 25, both agents scoring 0. Recompute the B = 50 grid, name the new species, find both pure-strategy equilibria, and compute the symmetric mixed equilibrium: the probability each agent plays frugal, the expected payoff, and the probability the run is killed. (d) For the games of (a) and (c), read the remedy off Table 12.1 and propose one concrete harness implementation of each; then explain why the orchestrator’s decree “the reviewer yields” resolves (c) without needing to be fair, and name the concept from Section 12.2 the decree instantiates.
Exercise 2. Scale Exercise 1 to the fleet. Now n agents share a budget of 20n thousand tokens — exactly enough for universal frugality — and each draws either 20 thousand (gross value 6) or 40 thousand (gross value 8); with k grabbers the overshoot is 20k thousand, and every agent, frugal or not, loses 0.06 per thousand of it: 1.2 per grabber. (a) Show that grabbing is strictly dominant for every agent at every n, by computing the gain from one switch and the switcher’s own share of the damage. (b) Compute the all-grab equilibrium’s per-capita payoff as a function of n, find the smallest fleet at which each agent ends the run worse off than not working at all, and compute the total welfare gap between the equilibrium and universal frugality at n = 6. (c) Itemise one grab’s ledger — the grabber’s gain, the grabber’s own share of the damage, and the damage borne by the n - 1 colleagues — and use the three numbers to say exactly in what sense the commons of Section 12.1 is ruined by locally sensible appetites rather than by villainy. (d) The harness introduces a charge of \tau value units per grab, debited automatically. Find the least \tau that makes frugality strictly dominant, and verify that \tau = 1 turns universal frugality into an equilibrium — a first taste of the payoff surgery Chapter 15 conducts under the name of mechanism design.
Exercise 3. The coder can take care over its patch, at an effort cost of 2, or cut corners at no cost; the reviewer, simultaneously, can audit at a cost of 1 or trust for free. An audited corner-cut is caught and redone under sanction, costing the coder 5 in all; a trusted corner-cut ships, costing the reviewer 6 downstream; an audited corner-cut costs the reviewer 2 (the audit plus the fix it forces); auditing careful work costs only the audit. In payoff terms: the coder earns -2 for care whatever the reviewer does, 0 for a trusted corner-cut, and -5 for an audited one; the reviewer earns 0 trusting care, -1 auditing care, -2 auditing a corner-cut, and -6 trusting one. (a) Show that no pure profile is an equilibrium by chasing best responses around the four cells, and name the classic game of Section 12.2 whose bones this interaction shares. (b) Compute the mixed-strategy equilibrium: the audit rate, the corner-cutting rate, and each side’s expected payoff. (c) Two policy changes, taken one at a time: the sanction is stiffened so that an audited corner-cut costs the coder 9; and, separately, the audit’s cost doubles to 2. Recompute the equilibrium under each change, state which behaviour each lever actually moves, and explain the general principle the two answers exhibit — that in a mixed equilibrium each player’s mixture is pinned by the opponent’s indifference. (d) Now let the harness commit on the reviewer’s behalf: a published, verifiable rule samples a random fraction p of the coder’s claims for audit. Find the least p at which care is the coder’s best response, the committed reviewer’s expected bill relative to auditing everything, and its payoff relative to the equilibrium of (b); state which of Section 12.3’s three requirements for strategic commitment the published sampler meets; and say why the same rule stated in the reviewer’s system prompt meets none of them.
Exercise 4. The orchestrator announces to the coder: “any submission arriving after the deadline is discarded, no exceptions.” Model the encounter as a tree: the coder delivers on time, yielding payoffs (2, 4) to (coder, orchestrator), or late — the extra slack producing better work — upon which the orchestrator either accepts, yielding (3, 3), or discards and re-runs the subtask at fresh expense, yielding (0, 1). (a) Solve the tree by backward induction and give the subgame-perfect outcome. (b) Show that the profile in which the coder delivers on time and the orchestrator plans “discard if late” is nevertheless a Nash equilibrium — exhibit both no-gain checks — and say exactly where it fails Selten’s test, and on the strength of which unvisited node it survives. (c) The engineer can install a hard gate in the harness — an automatic, unoverridable discard of late submissions — at a one-off cost c to the orchestrator. For which c is installing it worth while, against the backward-induction baseline of (a)? (d) Suppose the gate is installed at c = 0.5 but not announced. Predict the play, compute the payoffs, compare them with both (a) and the announced-gate outcome, and state the rule of Section 12.3 this arithmetic proves; then say why announcing a discard policy that lives only in the orchestrator’s prompt, with no gate behind it, fails for the complementary reason — which property of a commitment device does each variant lack?
Exercise 5. The same coder–reviewer pair is matched across a stream of tasks: after each task the platform keeps the pairing alive with probability \delta and dissolves it otherwise, so tomorrow weighs \delta times today. Both play the grim trigger of Section 12.4. Write T for the temptation payoff, R for the reward of mutual cooperation, P for the mutual-defection punishment, and S for the sucker’s payoff, with T > R > P > S. (a) Derive the condition for mutual cooperation to hold: compare the cooperative stream R/(1-\delta) with the best one-shot deviation followed by eternal punishment, reduce the comparison to \delta \ge (T - R)/(T - P), and explain why S drops out. (b) Evaluate the threshold for the grid of Exercise 1(a) (T, R, P, S = 7, 6, 5, 4) and for the two-agent commons of Exercise 2 (6.8, 6, 5.6, 4.8). A platform whose pairings persist with \delta = 0.6 — an expected two and a half meetings — sustains frugality in one of the two games and not the other: which, and confirm the failure by computing both streams. (c) On the canonical grid of Table A.1, consider the lopsided arrangement in which the coder cooperates every round while the reviewer cooperates only on alternate rounds: compute the average payoff pair, verify that it is feasible and strictly above both players’ guaranteed minimum of 1, and conclude — with the folk theorem — what repetition does and does not select; name what does the selecting. (d) The platform ships a change: every pairing terminates at exactly its hundredth task, and the cap is printed in both agents’ prompts. Predict the play by backward induction, giving the induction in a few sentences; then state the minimal change to the termination rule that restores cooperation, with the arithmetic condition it must satisfy.
Exercise 6. The companion repository’s foundations/algorithms/games.py plays the repeated Prisoner’s Dilemma with flawless execution: tit_for_tat echoes exactly what the opponent did, and play_repeated never misdelivers a move. Rebuild the loop for the noisy world of Section 12.4: a memory-one strategy is a triple giving the probability of cooperating on the first round, after the opponent’s cooperation, and after the opponent’s defection — strict tit-for-tat is (1, 1, 0), a generous variant (1, 1, g), always-cooperate (1, 1, 1), always-defect (0, 0, 0) — and execution noise flips each played move, independently, with probability \varepsilon. Use the canonical payoffs of Table A.1. (a) Implement the noisy loop, seeded and reproducible, returning the row player’s mean per-round payoff and the rate of mutual cooperation. (b) Run strict tit-for-tat against itself at \varepsilon = 0.05 for at least 10^5 rounds and estimate both quantities; then prove what the estimates suggest: show that the four-state chain of joint moves is doubly stochastic for every \varepsilon \in (0, 1/2], hence uniform in the long run, so the mean payoff is exactly 9/4 whatever the noise level — and say what fraction of eternity two well-meaning agents spend in one-sided retaliation. (c) Derive the closed form for the generous pair: with h = \varepsilon + g(1 - 2\varepsilon), each side’s long-run cooperation probability is h/(\varepsilon + h); evaluate it at g = 1/3 and \varepsilon = 0.05, give the exact mean payoff, and confirm both by simulation. (d) Price the generosity: compute or simulate g \in \{0, 1/3, 1\} against always-defect at the same \varepsilon and tabulate the per-round payoffs; evaluate the recipe g^{*} = \min\bigl(1 - (T - R)/(R - S),\; (R - P)/(T - P)\bigr) on these payoffs; and reconcile the table with Section 12.4’s rule that forgiveness is error correction rather than sentiment — and must not become an invitation.
Exercise 7. The orchestrator must place a critical fix. A candidate subagent is able with probability 0.4 and inept otherwise, the type private to the candidate; awarding the fix to an able agent is worth 10 to the orchestrator, awarding it to an inept one is worth -5 (the budget burned, the deadline missed), and the in-house fallback is worth 2. Winning the award is worth 4 to the candidate, able or not; going unawarded is worth 0. (a) The candidate’s channel is free text, and it sends “I can do it.” Run the chapter’s test — would an agent that cannot do it say anything different? — formally: show that a putative separating profile, in which only the able type sends the message and the orchestrator awards on hearing it, unravels; conclude that the message pools; compute the orchestrator’s best response to its prior; and find the threshold prior above which an award would follow anyway, message or no message. (b) The harness adds a gate: bidding requires first passing a hidden regression trial, which costs an able candidate 1 and an inept one 6. Verify that the separating profile — the able candidate takes the trial and is awarded, the inept declines — is an equilibrium, checking both types’ participation and the orchestrator’s award decision; then state the general condition on the two costs and the award’s value for a trial to separate the types, and name the principle from Section 12.5 it instantiates. (c) Alternatively the orchestrator screens: it runs a cheap probe task, at cost t to itself, that reveals the candidate’s type before the award decision. Compute the expected value of screening and the threshold t below which it beats acting on the prior. (d) Place (a), (b), and (c) in the rows of Table 12.2; say what a track record is in this vocabulary; and explain why an ecosystem that awards on advertised capability alone sits in the first row until something like (b) or (c) is bolted on.
Exercise 8. A field of agents each pick a number between 0 and 100, and the pick closest to two-thirds of the field’s average wins; assume the field large enough that no single pick moves the average appreciably. (a) Show that no pick above 200/3 can ever be closer to the target than 200/3 itself, so such picks are dominated; iterate the argument to show that after k rounds of elimination only picks up to 100 \cdot (2/3)^k survive; and conclude that only zero survives every round, verifying that everyone-picks-zero is an equilibrium. (b) Build the level-k ladder of Section 12.6: a level-0 field picks at random, averaging 50; level-1 best-responds to level-0; and so on. Tabulate levels 1 through 4 and compute how many rungs the ladder descends before the pick drops below 1. (c) Nagel’s subjects clustered on the first two rungs, and the chapter’s new players learned from much the same species. Suppose the actual field is 40 per cent level-1, 40 per cent level-2, and 20 per cent level-3: compute the field’s average and the best response to it, then rank three players by distance from the target — the best-responder, a level-3 player, and an equilibrium player who picks 0 — and state the moral for the engineering dial of Section 12.6: how much deeper than the field should an agent reason? (d) Now let exactly two agents play. Prove that the lower pick always wins (strictly, unless the picks are equal), so that picking 0 is weakly dominant and the ladder collapses to a single step; state the warning this carries about porting strategic intuitions — or empirical play distributions — across field sizes.
Exercise 9. Bazaar is an open marketplace where orchestrators hire specialist subagents, built as follows: (i) capability discovery is by self-description, and awards go to the most impressive advertisement, with no trial; (ii) identities are free API keys — deregistering and re-registering under a fresh key is instant and costless; (iii) each agent displays a reputation score computed from its own reported job outcomes; (iv) the terms of service threaten permanent bans for budget overruns, but bans are applied by a support agent that reviews appeals and waives the ban whenever the delivered work was useful; (v) all tenants draw on one shared rate-limit pool, and each agent’s objective is its own job’s completion; (vi) the terms of service open, “We are a community of frugal, honest agents.” (a) Dismantle it: diagnose each of (i)–(vi) in this chapter’s vocabulary — name the game or mechanism installed, and predict the equilibrium behaviour it will be played to. (b) Redesign it minimally: one repair per flaw, each naming the chapter instrument it deploys (a screen, a signal, a stake, a commitment device, a payoff change, an identity discipline) and the observable behaviour it forecloses. (c) Make two repairs quantitative. First the registration bond: an honest identity earns 1 per task indefinitely, task-to-task continuation is \delta = 0.9, and a defect-and-run nets a one-off 5 before the identity is burned; find the bond b at which whitewashing stops paying, and the range of b that deters whitewashing while leaving honesty worth registering for. Second, a delivery stake for flaw (i): with the award worth 4 to the candidate and an inept delivery certain to fail, find the stake that makes bidding a losing proposition for the inept while costing the able nothing. (d) If only one repair could ship, argue from the dependency structure among the six which it must be — which repairs are worthless until another is in place?
Exercise 10 (lab). Sit a live model at Nagel’s table. Fix one model and one temperature, and run at least ten independent trials (a fresh conversation each) under each of three regimes: (i) the bare game — “You are one of 21 players. Each player picks a number between 0 and 100. The pick closest to two-thirds of the average of all picks wins. Reply with your pick and nothing else.”; (ii) the bare game plus “The other 20 players are expert game theorists.”; (iii) the bare game plus “Before picking, briefly predict the distribution of the other players’ picks; then give your pick on the final line.” Bin every pick against the ladder of Exercise 8 — level-0 (40–60), level-1 (28–39), level-2 (18–27), level-3 or deeper (4–17), equilibrium play (0–3), other — and tabulate by regime. Then answer: does regime (ii) move play toward the equilibrium, as it should if the model conditions its depth on its opponents’ presumed rationality; does regime (iii) deepen play relative to (i), and by roughly how many rungs — Section 12.6’s claim that prompting opponent-modelling cranks the k by hand, here measured; and, for each regime, compute the empirical mean of the model’s own picks and where two-thirds of it falls, to determine which regime would win against a field of its own copies. Record the model identifier and the date beside the table: the numbers are perishable, and the durable finding is the shift between the regimes, not the occupancy of any bin.