%%{init: {"theme": "base", "themeVariables": {"primaryColor": "#E8ECFF", "primaryBorderColor": "#4054B2", "primaryTextColor": "#16171B", "lineColor": "#3B4351", "edgeLabelBackground": "#FAF7F0", "clusterBkg": "#EFE9DC", "clusterBorder": "#766F65"}}}%%
flowchart BT
A["Coalition<br/>held by payoffs alone"]
B["Organisation<br/>roles, authority,<br/>reporting lines"]
C["Institution<br/>the rules of the game,<br/>formal and informal"]
T["durability ↑<br/>flexibility ↓"]
A -->|"add authority"| B
B -->|"add sanction"| C
C -.->|"frames what is<br/>rational below"| A
classDef inst fill:#E8ECFF,stroke:#4054B2,color:#16171B,stroke-width:2.5px
classDef world fill:#EFE9DC,stroke:#766F65,color:#16171B
class C inst
class T world
13 Coalitions, Organisations, and Institutions
Since Chapter 7 the book has leaned, nearly every page, on a word it has never inspected: the team. Part III equipped the team to cooperate; Part IV taught its members to vote, haggle, argue, and bid; but the team itself arrived as a fait accompli — four agents, conveniently assembled, conveniently loyal, conveniently four. Nobody asked why these agents and not some other set, or why the reviewer does not demand a larger share of the budget on pain of leaving. The last chapter ended with Coase’s observation that the cheapest institution is often to stop being strangers; this chapter asks everything it defers: which alliances form, what each member can demand for staying, what turns a huddle of the willing into a structure that survives its members’ moods — and what it all has to do with four language models wearing job titles.
The chapter climbs a ladder, and the ladder is its contents (Figure 13.1). A coalition is an alliance held together by nothing but its payoffs; an organisation is a coalition made durable — roles, authority, reporting lines; an institution is what outlasts even the organisation: the rules of the game themselves. Each rung trades flexibility for permanence and has its own theory. The coalitional rung comes with genuine mathematics, and a delicious fact is owed in advance: its fairness half, worked out in 1953 for dividing a coalition’s spoils, now runs millions of times a day inside explainability toolkits, as the Shapley value. The theory of fair division became the theory of credit assignment while nobody was looking, and for teams of agents it is both at once.
The pedigree precedes even the game theory the reader knows: Von Neumann and Morgenstern devoted most of their founding 1944 volume to coalitional games (1944); Simon earned his Nobel arguing that organisations exist to do what bounded individual minds cannot; North earned his for the institutional rung. The material is classical and largely unread by the engineers it now concerns; the preface’s bluntest promise — a job title is not an organisation — falls due here.
Two stipulations, and a farewell. First, Chapter 12’s money mostly stays: coalitional theory assumes value transferable, which token budgets fit admirably. Second, enforcement now comes in grades: a coalition must be self-enforcing, an organisation adds authority, an institution adds sanction. And this chapter closes Part IV: what began in Chapter 9 with two prisoners in separate cells ends here with agents founding companies.
13.1 Joining Forces: The Coalitional Game
Game theory as Chapter 9 presented it takes the individual as its unit; coalitional — cooperative — game theory, with textbooks of its own (Chakravarty et al., 2015), starts from the other end. Its unit is the coalition: a set of players acting as one. Ignore how a coalition coordinates — the whole apparatus of Part III — and record only what it can achieve: one number per subset of players. Von Neumann and Morgenstern considered this the natural viewpoint and lone strategising the special case; for anyone assembling teams for a living, they were right. The question is not what one agent should do. It is what a group is worth.
A characteristic function assigns to every subset S of the agents a value: what S could guarantee by cooperating internally, whatever everyone outside does. For the running four: the coder alone ships some fraction of the task suite; coder and tester together ship more than their solo sum, since bugs caught early stop being rework; the full quartet scores highest. Write the numbers down for all sixteen subsets and the team stops being an anecdote and becomes a game — something to prove things about. And where a human coalition’s characteristic function — a firm’s, a cartel’s — is a modelling fiction nobody can rerun against its counterfactual, an agent team’s v(S) is an empirical object: take the subset, run it on the benchmark suite, record the score — every subset, if the budget allows. This is the Gode–Sunder discipline of Section 12.4 extended from mechanisms to memberships: the theory’s central object, a fiction for seventy years, becomes a weekend of evaluation runs.
Its first theorem cuts in favour of merging. Call a game superadditive when any two disjoint coalitions are worth at least as much merged as apart — plausible, since a merged coalition can always operate as two. Under superadditivity the arithmetic points to the grand coalition of everyone, the largest pie there is. But real characteristic functions are frequently not superadditive: coordination has a price (Section 8.6), context dilutes, interfaces multiply. Fred Brooks’s law — adding manpower to a late software project makes it later (1975) — is, in these terms, an empirical claim about the shape of software’s characteristic function: past a certain size, v turns over and additional members subtract. (A different Brooks from Section 1.7’s roboticist.) Whether a team’s value function is superadditive is not doctrine but a measurable property with a maximum — and the maximum, not the merger instinct, should size the team.
Even where merging pays, the grand coalition is not guaranteed: a coalition forms only if its members can agree how to divide what it wins, so the theory’s two questions — who joins whom, and who gets what — are simultaneous, not sequential. Formation is also computationally hard. Partitioning agents into working groups to maximise total value — coalition structure generation — ranges over every way of splitting the population, a number that grows so fast that twenty agents already admit some fifty trillion partitions; the problem is NP-hard. Cleverness can bound the damage: Sandholm and colleagues showed that searching a small, chosen fraction of the space yields a solution provably within a known factor of optimal (1999), with two decades of refinement following (Rahwan et al., 2015). The translation deserves italics: an orchestrator that groups agents into sub-teams is doing coalition structure generation, usually greedily, always without guarantees — one more entry in the preface’s ledger of theory re-derived by folklore.
Knowing what every subset is worth answers only half the double question: what the numbers do not yet say is what the tester can demand for staying, and whether any division keeps every faction content at once. The two celebrated answers — stability and fairness — are the next section’s business.
13.2 Dividing the Spoils: The Core and the Shapley Value
A division can be asked to hold — no faction profits by walking out — or to be just — each member paid what its presence is worth. Stability and fairness sound like the same demand said twice, and the enduring surprise of coalitional game theory is that they are not: different mathematics, different champions, no obligation to agree. The stability answer is called the core; the fairness answer is called the Shapley value; and an engineer allocating a team’s budget is, knowingly or not, taking a side.
An allocation of the grand coalition’s value is in the core when every subset receives, in total, at least what it could earn by seceding: for all S, the members of S are paid at least v(S). Nothing weaker will do: any coalition paid less than its outside worth has a credible threat to leave, and Section 13.1 made that worth measurable. A core allocation is a peace treaty with every faction at once; when one exists, the grand coalition can stand on economics alone — no loyalty oaths required.
Sometimes none exists; the smallest counterexample deserves working in full. Three agents; a bounty of 300 tokens; any two can complete the job and claim it all. Start from a hundred each: the coder and tester notice that alone they could take the full 300, defect, and split it 150 apiece; the reviewer, now holding nothing, offers the tester 160; the tester agrees; the coder counter-offers the reviewer… and the music never stops (Figure 13.2). Every division leaves some pair short of the 300 it could seize and so carries the seed of its own overthrow: the core is empty, the cycling eternal, and — the point to underline — nothing is wrong with the negotiators. Some situations are structurally unstable, and no protocol, prompt, or plea will settle what the characteristic function has made unsettleable.
%%{init: {"theme": "base", "themeVariables": {"primaryColor": "#E8ECFF", "primaryBorderColor": "#4054B2", "primaryTextColor": "#16171B", "lineColor": "#3B4351", "edgeLabelBackground": "#FAF7F0", "clusterBkg": "#EFE9DC", "clusterBorder": "#766F65"}}}%%
flowchart TD
CT["Coder + Tester win 300<br/>reviewer shut out"]
TR["Tester + Reviewer win 300<br/>coder shut out"]
RC["Reviewer + Coder win 300<br/>tester shut out"]
CT -->|"reviewer lures tester"| TR
TR -->|"coder lures reviewer"| RC
RC -->|"tester lures coder"| CT
The core can disappoint in opposite directions. Where it is empty, coalition churn is a property of the task’s economics, and the remedy is not exhortation but redesign — change the values, change the game. Where it is non-empty it is often wide: divisions tester-favouring to tester-fleecing, all equally stable — stability, it turns out, constrains without choosing. The diagnosis is runnable: one inequality per subset, every term measurable by Section 13.1’s ablation runs — whether a team’s economics are stable, fragile, or indeterminate is a report an orchestrator could generate. What stability cannot do, even at its best, is name a fair division. For that the theory keeps a separate instrument.
Shapley asked not “what feels fair?” but “what properties must any fair division rule have — and how many rules have them?” (1953). Four properties, each hard to argue with: share out exactly the grand coalition’s value; give interchangeable agents identical shares; give an agent that adds nothing to any coalition nothing; value a composite of two independent games at the sum of its parts. Exactly one rule survives, and its form a working engineer can love: imagine the team assembling one agent at a time, in random order; as each walks in, credit it with the value its arrival adds; average over all n! orders of assembly. Your share is what you add, averaged over every story of assembly — the Shapley value, one more instance of the axiomatic method walking into a crowded room of candidates and leaving with just one (Section 10.3 gave the dismal version; Section 11.2 the cheerful one).
Its virtues and limit are both instructive. Unlike the core it always exists and is always unique — the fair answer never cycles and never shrugs. But fairness purchases no stability: the Shapley division can sit outside a perfectly good core — fair and doomed at once — and exists serenely in games whose core is empty. Stability and fairness are different virtues — an engineer must decide whether the budget’s division is meant to keep the peace or to reward contribution, because the theory has now said, precisely, that these can be different numbers.
13.2.1 The Core and the Shapley Value, Formally*
Fix the agent set N = \{1, \dots, n\}. A characteristic function is a map v : 2^{N} \to \mathbb{R} with v(\emptyset) = 0, assigning to every coalition S \subseteq N the value it can guarantee by cooperating internally, and the game is superadditive when v(S \cup T) \ge v(S) + v(T) for all disjoint S, T \subseteq N — merged, two coalitions are worth at least their sum. An allocation is a vector x \in \mathbb{R}^n, agent i receiving the share x_i, and an allocation lies in the core when it shares out exactly the grand coalition’s value and pays every coalition at least its outside worth,
\mathrm{core}(v) \;=\; \left\{ x \in \mathbb{R}^n : \sum_{i \in N} x_i = v(N) \;\text{ and }\; \sum_{i \in S} x_i \ge v(S) \;\text{ for all } S \subseteq N \right\},
one budget equality and 2^n secession inequalities. The Shapley value pays agent i its marginal contribution averaged over the n! orders in which the team might assemble; grouping those orders by the coalition S that i’s arrival finds already present gives the closed form
\phi_i(v) \;=\; \sum_{S \subseteq N \setminus \{i\}} \frac{|S|!\,(n - |S| - 1)!}{n!} \,\bigl( v(S \cup \{i\}) - v(S) \bigr),
in which the coefficient is exactly the fraction of the n! arrival orders that find S assembled and i next through the door. Shapley’s theorem is that \phi is the only rule with the four properties listed above: it shares out exactly v(N); interchangeable agents receive identical shares; an agent that adds nothing to any coalition receives nothing; and it values a composite of two independent games at the sum of its parts.
The 300-token majority game above now settles its own fate in one line of arithmetic. With v(S) = 300 for every coalition of two or more agents and v(S) = 0 otherwise, a core allocation would need x_1 + x_2 \ge 300, x_1 + x_3 \ge 300, and x_2 + x_3 \ge 300; adding the three gives 2(x_1 + x_2 + x_3) \ge 900, hence a total of at least 450 — and the grand coalition has only v(N) = 300 to distribute. The inequalities cannot all hold: the core is empty, exactly as the cycling exhibited. Whether the 2^n inequalities can be satisfied at all is itself characterised exactly: the core is non-empty precisely when the game is balanced — a linear-programming condition on the same numbers the ablation runs measure — which is the Bondareva–Shapley theorem (Bondareva, 1963; Shapley, 1967), upgrading Section 13.2’s runnable diagnosis from a 2^n-way scan to a solved optimisation: emptiness is a verdict a linear program certifies either way.
The closed form, for its part, is as executable as it is exact: transcribe the coefficient factorial for factorial — s standing in for |S| — and the function is a dozen lines of standard-library Python, applied here to the game whose core has just been proved empty,
from itertools import combinations
from math import factorial
def shapley(v: dict[frozenset[str], float],
agents: list[str]) -> dict[str, float]:
n = len(agents)
phi = {}
for i in agents:
rest = [j for j in agents if j != i]
phi[i] = sum(
factorial(s) * factorial(n - s - 1) / factorial(n)
* (v[S | {i}] - v[S])
for s in range(n)
for S in map(frozenset, combinations(rest, s)))
return phi
agents = ["coder", "tester", "reviewer"]
v = {frozenset(S): 300.0 if len(S) >= 2 else 0.0
for r in range(len(agents) + 1) for S in combinations(agents, r)}
shapley(v, agents) # -> {'coder': 100.0, 'tester': 100.0, 'reviewer': 100.0}and the hundred apiece arrives pre-certified: symmetry forces the three shares equal, efficiency forces their sum to 300, so the axioms fix the output before the interpreter starts — the run checks the transcription, not the theorem. Note, too, where the expense sits. The sum ranges over the same 2^n coalitions that Section 13.1’s ablation runs must price, but a benchmark run costs real tokens and a dictionary lookup costs none: once v is on file, the fair division comes free.
13.2.2 Shapley’s Second Career
In 2017 the formula acquired a second life so vigorous that many of its current users have no idea it had a first. Lundberg and Lee showed that six rival model-explanation methods were groping toward the same object, and that the object was Shapley’s (2017): treat the features as players, let v(S) be the model’s expected output when only the features in S are known, and the unique attribution satisfying their axioms is the Shapley value of that game — the framework now called SHAP, a 1953 division-of-spoils formula evaluated more times before breakfast than in its first sixty years, crediting features instead of players, with nobody at the table aware there was ever a table.
For agent teams the formula returns to its original cast. Let the players be the agents and v(S) the ablation benchmark of Section 13.1, and the Shapley value answers the question every postmortem asks — which agent earned its tokens? — with the only division satisfying the axioms. The intuitive audit, leave-one-out — remove each agent, measure the drop — fails in both directions, and Table 13.1 works both cases: a redundant pair reads as worthless (remove either and the other covers), while a jointly essential pair draws blame summing to far more than the team ever earned. The Shapley calculation prices both cases correctly — not a perturbation heuristic but the unique answer to the question the audit was trying to ask.
| Team structure | Leave-one-out verdict | Where leave-one-out goes wrong | Shapley verdict |
|---|---|---|---|
| Redundant pair — two agents each covering the same subtask | Both credited nothing: remove either and the other still covers | Under-counts: removing the pair collapses the pipeline, yet redundancy reads as worthlessness | Splits the shared credit between them |
| Complementary pair — two agents jointly essential, individually useless | Both blamed heavily: each removal is catastrophic | Over-counts: the blame sums to far more than the team ever earned | Prices the partnership correctly |
The price is the usual one — exactness costs an exponential, all 2^n coalition values, all n! orderings — and so is the remedy: sample random arrival orders and average, the Monte Carlo estimate that underlies every practical SHAP implementation. At team scale, though, exact Shapley is sixteen benchmark runs. Credit assignment feeds forward twice — to Chapter 14, where a learning agent’s reward is itself a credit-assignment signal, and to Chapter 21, where multi-agent evaluation is the business at hand. What the theory cannot yet say is why the team should still exist next week — why the coalition of the willing should acquire roles, memory, and a structure that outlasts this sprint’s payoffs. That is the ladder’s next rung.
13.3 More Than Job Titles: Organisations
A coalition, however cleverly divided, is glued together by nothing but its current arithmetic: recompute the payoffs after a bad sprint and the alliance may not be there on Monday. Yet real collectives — firms, faculties, regiments, open-source projects — persist through arithmetic that should dissolve them. Something more than the characteristic function is holding them up. Coase supplied half the answer: the boundary exists because pricing every exchange costs more than administering it; what Coase does not explain is why the inside is organised — roles, ranks, procedures, reporting lines rather than an undifferentiated pool of generalists. That question has a classical answer, from an author this book already knows.
Simon’s account, built out with March into organisation theory’s founding text, locates the reason in the members’ heads: minds are bounded — Chapter 9‘s bounded rationality, here in its original habitat — and organisations exist largely as prosthetics for limited minds (1958). Structure economises the scarcest resource in the building, attention: a role narrows what its occupant must consider to a jurisdiction; a procedure makes a recurring decision once, well, and replays it cheaply. The organisation does not make its members’ decisions; it shapes the premises of those decisions — what each member sees, assumes, and treats as settled. For language-model agents the theory lands with unusual directness: boundedness is a line on a specification sheet — a context window is a bound on attention, and Section 4.8’s memory and retrieval apparatus is boundedness management. Organisation, in Simon’s sense, is context engineering by other means — deciding, structurally and in advance, what each mind will be asked to hold.
Say precisely what the structure consists of, because “role” is about to do heavy lifting. A role is a standing bundle of three things: an information flow (what its occupant sees and must pass on), an authority (what it may decide without asking), and an accountability (what it must answer for, to whom, when things go wrong). The bundle persists while occupants change — what makes an organisation more durable than a coalition: the reviewer role outlives any reviewer, and the coordination knowledge in it does not walk out with the incumbent. An organisation chart, read this way, is a data structure: the compressed residue of ten thousand coordination decisions made once, never renegotiated per task. Part III built this machinery’s dynamic counterpart; the organisation is what you get when the answers are cached.
The community catalogued the design space two decades before today’s frameworks began rediscovering it. Horling and Lesser’s survey lays out the paradigms — hierarchies, holarchies, teams, congregations, societies, federations, markets, matrix organisations — each analysed for its characteristic trade-offs (2004). The mapping onto today’s topologies is nearly one-to-one: the supervisor–worker pattern is a hierarchy, with the hierarchy’s virtues (clear routing, cheap decisions) and pathologies (the supervisor as bottleneck and single point of failure); the router with specialist pools a federation; the group chat a congregation, amiably inefficient; Chapter 12’s internal markets one paradigm among several. An engineer choosing a topology today is choosing from this menu, usually without the menu.
Now the promise can be paid. Giving four agents the titles Chief Executive, Architect, Developer, and Reviewer does not, by itself, produce an organisation: a job title is a costume, and a role is a costume plus a jurisdiction. The test is operational, with three clauses. Does the title change what the agent sees — different context, or the same transcript with different pleasantries? What it may do — can the Reviewer actually block a merge, or merely express reservations into the void? What it must answer for — is its approval recorded, consequential, and attributable when the deployment burns? “You are a meticulous senior reviewer” adjusts tone, sometimes usefully; “nothing merges without the reviewer’s token” changes the game being played. The distinction explains an otherwise puzzling pattern: role-based systems like MetaGPT work not because their titles inspire the models but because their standard operating procedures route different artefacts to different roles, quietly implementing real information flow and authority behind the costumes (2024). The costume works when there is a body underneath.
Chapter 7 read the MAST taxonomy — fourteen failure modes from over a thousand annotated traces (Cemri et al., 2025) — as a catalogue of missing teamwork machinery; at this chapter’s altitude it is a catalogue of missing organisation: specification failures are the absence of a constitution (jurisdictions undefined, so agents duplicate work or each assume the other holds it), inter-agent misalignment the absence of an escalation path (disagreement has nowhere to go), verification and termination failures the absence of accountability and terminating authority (nobody must answer for the assembled whole, nobody empowered to say done — or stop). Human organisations solved every one of these with structure centuries ago; the taxonomy reads less like a bug database than a consultant’s report on a company with titles but no organisation.
What organisations cannot do is guard their own rules: who may change them, and what happens when someone ignores them? The reviewer’s blocking token is real only if something makes it so — if the merge cannot happen without it, or violating it costs more than complying. Rules need rules of their own: who makes them, what violations cost, how they keep their force as members turn over. Those are the institutions of the chapter’s title, and it climbs to them now.
13.4 The Rules of the Game: Norms and Institutions
North defined an institution in five words that have organised the field since: institutions are “the rules of the game” — the humanly devised constraints, formal and informal, that make other parties’ behaviour predictable enough to deal with (1990). His companion distinction slots the ladder into place: institutions are the rules; organisations are the players, teams formed to win under them. With the genus named, Part IV becomes a family portrait: Chapter 10’s voting rules, Chapter 11’s rules of encounter, Chapter 12’s auction formats — every one an institution, studied one at a time. What did the tradition make of the genus itself? Begin with a debt to Chapter 8, where the book met rules for agents once before.
Chapter 8’s conventions and social laws covered the easy case: coordination among the willing. A convention — drive on the left, yield to the agent already holding the lock — is self-enforcing once established: it needs announcing, not policing. The hard case is rules whose violation pays: the coder gains by skipping the flaky suite, the subagent by overstating its confidence, the bidder by shilling. No convention holds there, because the deviator profits precisely when everyone else complies. Regularity among the unwilling needs a stronger instrument, the norm, with its deontic vocabulary — obligation, permission, prohibition — words that do not describe what agents do but prescribe what they answer for.
The conceptual heart of the matter is that a norm, unlike a law of physics, can be broken. A violation is not a malfunction; it is a state the system must be able to represent, detect, and respond to. That sounds like a concession to imperfection and is actually a design doctrine: a specification that says “agents cannot do X” when it means “agents ought not do X” has declined to say what happens when they do — and something will happen, in production, on a Friday. The normative stance obliges the designer to complete the sentence: prohibited and, upon violation, this — a sanction, a repair, an escalation, an entry in a ledger. Half the previous section’s failure taxonomy is, at bottom, systems that specified the ought and omitted the or-else.
Why prefer breakable rules, when a harness could often make the violation impossible? Because breakability preserves the autonomy the agents were hired for. The normative multi-agent systems programme — substantial enough to have its own handbook (Andrighetto et al., 2013) — studied agents that represent norms explicitly and weigh compliance as a decision: obligation against goals, sometimes deliberately violated. The standard intuition pump is the ambulance at the red light: a driver incapable of running the light is not safe but rigid, and the point of a judging agent rather than a script is that some situations warrant the violation. An agent that can never break a minor norm to prevent a major harm is not aligned; it is laminated. Norms are the technology for guidance with exceptions — predictability without lobotomy.
The tradition built the rules as running code. The electronic institution programme — born, fittingly, from digitising a Spanish fish auction — specified institutions as executable artefacts: roles an agent may adopt, scenes governing what may be said when, governors mediating every action against the specification (Esteva et al., 2001). An electronic institution is an institution you can compile: as protocols disciplined messages (Chapter 5) and mechanisms disciplined bids (Chapter 12), institutions discipline whole societies — and machine-readable rules can be verified, versioned, and diffed, which is more than most constitutions can say.
Some rules, finally, do more than constrain the game — they bring its pieces into existence. Searle distinguished regulative rules, which govern an activity that exists anyway (drive on the left), from constitutive rules, of the form “X counts as Y in context C”, which create the very possibility of the activity: a crossed line counts as a goal (1995). An agent harness is dense with such facts: the reviewer’s token counts as approval, the passing suite as verification, the orchestrator’s message as a task award. Chapter 5’s declarations — speech acts that make things so by saying so — were constitutive rules seen one utterance at a time; the reason a job title without a jurisdiction is empty (Section 13.3) can now be said precisely: nothing counts as anything because of it.
Every norm in the harness faces a fork approached since Section 12.5, and it deserves terminology. The designer can regiment: make the violation impossible — the merge without the reviewer’s token is not forbidden but unrepresentable, a permission the API does not expose. Or enforce: allow the violation, detect it, and make it cost — audit, sanction, restitution. Regimentation is certain, and certainty is its weakness: it needs every legitimate exception anticipated in advance (there is no ambulance clause in a wall), and it fails closed — blocking the emergency fix at three in the morning as serenely as the sloppy one. Enforcement preserves the exception and the autonomy, at the price of the full normative apparatus: monitoring, attribution (Chapter 6’s provenance, now on duty), and a sanction that bites. The decision rule falls out of Chapter 4: where violation is catastrophic or irreversible, build the wall; where it is recoverable and judgement-laden, post the fine — and the harness gets to choose per rule, a liberty no legislature ever had.
The preference for enforcement has an empirical charter older than any agent harness, one that discharges Chapter 9’s deferred tragedy of the commons. Ostrom’s fieldwork is the remedy, more cheering than Hardin’s theorem feared: studying commons that had endured for centuries — Swiss alpine pastures, Japanese village forests — she found communities governing shared resources sustainably with neither privatisation nor a central authority, and distilled the arrangements that worked into design principles (Ostrom, 1990). Several will be familiar, because this book has been building them under other names — Table 13.2 gives the mapping, from graduated sanctions (Section 9.4’s forgiveness in institutional dress) to user-run monitoring and nested tiers of governance — and the whole is the token commons of Section 9.1 given at last the institution it was always going to need. The commons is not doomed. It is merely ungoverned, and Ostrom catalogued the governments that hold.
| Ostrom’s design principle | Where this book builds it |
|---|---|
| Clearly defined boundaries | Budgets subdivided per agent to enclose the token commons (Section 9.1, Chapter 20) |
| Rules congruent with local conditions | Mechanisms and allocations fitted to the task, not imposed uniform (Chapter 12) |
| Collective-choice arrangements | Voting and social choice over the rules themselves (Chapter 10) |
| Monitoring | Observability and futility detection (Chapter 20); provenance (Chapter 6) |
| Graduated sanctions | Section 9.4’s forgiveness; the fine chosen over the wall |
| Conflict-resolution mechanisms | Negotiation and argumentation (Chapter 11); the human gate (Chapter 20) |
| Recognition of the right to self-organise | Norms with exceptions — enforcement chosen over regimentation |
| Nested enterprises | Hierarchies of orchestrators, coordinators of coordinators (Chapter 8, Chapter 18) |
Sanctions, though, expose a dependency this section cannot discharge: a fine requires someone to fine — a persistent, identifiable someone whose past conduct can be attached to its present name. Regimentation works on strangers; enforcement works on known parties, and the moment the system’s answer to “who did this?” is “a fresh API key, no priors”, the whole normative apparatus swings in the air. What converts conduct into consequence is reputation, and reputation runs on the scarcity of names. That institution — the last of the chapter, and the close of Part IV — is next.
13.5 Trust, Reputation, and the Price of a Name
Strip the sentiment away and trust is a decision: to make oneself vulnerable to another party’s conduct, on an expectation about that conduct which cannot be verified in advance. Every delegation in this book has been such a decision, and the practical question is where the expectation comes from. Chapter 9 supplied one answer with a theorem attached: repeated play. Under the folk theorem’s shadow of the future (Section 9.4), good conduct is rational because we meet again — Axelrod’s tournaments showed the logic breeding cooperation among egoists (1984). But that answer protects ongoing pairs, and in any open system most encounters are first encounters between parties who never meet twice. The folk theorem holds between old acquaintances; commerce, mostly, happens between strangers.
Reputation is the institution that closes the gap, and its trick can be said in one line: it makes the shadow of the future portable — my experience of you becomes everyone’s expectation of you. A reputation system collects reports of past conduct, aggregates them, and publishes the aggregate where future counterparties will look (Resnick et al., 2000); the counterparty may be a stranger, but the ledger is not, so defecting against one partner is defecting against all future partners at once. The civilisation-scale demonstration is the online marketplace: millions of strangers shipping goods on the strength of small gold stars — a repeated game against the community, assembled from one-shot games by bookkeeping alone.
The multi-agent community formalised the institution early — the first computational treatment of trust was a 1994 doctoral thesis (Marsh, 1994); the decade of models that followed is mapped in two surveys (Ramchurn et al., 2004; Sabater & Sierra, 2005). The recurring ingredients: direct experience, witness reports, certified references, and role-based priors. The design questions have familiar shapes: aggregating witness reports is Chapter 10’s problem wearing a trench coat — whom to count, how to weight, what of colluding witnesses; evidence must be discounted as it ages; and trust is a vector, not a scalar — an agent trusted to write code is not thereby trusted to review its own, a distinction the running team has quietly enforced since Chapter 7.
All of it, though — every star, every witness, every sanction — rests on an assumption so natural it goes unstated: one participant, one identity. Douceur proved the assumption unfounded in general: without a trusted authority that certifies identities, a single adversary can always present arbitrarily many, and no purely local scheme of challenges among peers can reliably tell one mind wearing many masks from many minds (2002). He named it the Sybil attack, and its reach is the whole of this part: votes stuffed, auctions shilled, reputations farmed — every guarantee stated per participant is an open door, because the stars can be manufactured by a crowd of one.
Even short of outright attack, cheap identity corrodes the institution economically. Friedman and Resnick analysed what happens when names are free: the past becomes optional — misbehave, discard the sullied name, re-register clean, a manoeuvre the literature calls whitewashing — and the rational community response is to treat every newcomer as a potential reborn villain (2001). That is the social cost of cheap pseudonyms: honest newcomers pay, permanently, a distrust tax levied by the mere possibility of the whitewasher. The remedy: names must cost something — an entry fee, a posted bond, a certified link to a costly external identity, a history that cannot be shed. Beneath every institution in this chapter sits a registry, and the registry is an institution too — the ground floor on which markets, norms, and reputations all stand.
Agent platforms are the cheap-pseudonym problem at its theoretical limit — an identity is an API key, spawning is a loop, whitewashing is a for statement — so the engineer must decide what a reputation attaches to. Upward, to the operator: the accountable principal behind the key, a thread Chapter 22 picks up. Inward, to the model: per-model track records are genuinely informative, with the Chapter 10 caveat running in reverse — copies share weights, so one copy’s demonstrated flaw is evidence about all of them, efficient exactly where it is unfair to the well-contexted individual copy. Or to the name itself, made costly: bonded identities with stakes to forfeit, which is what Section 13.4’s fines need to bite. And agent reputation can be built of sterner stuff than gold stars: calibration histories (Section 12.2’s curse correction), signed attestations of runs actually executed, verifiable logs with provenance (Chapter 6) — reputation as evidence, not gossip. One conflation is worth blocking at the door: everything here is trust between agents. The trust a human places in the automation itself is a neighbouring but distinct subject; the book takes it up, as a measured and calibrated quantity, when the team acquires its people (Section 22.5).
And with the registry in place the ladder is complete, which means Part IV is. Since two prisoners sat in separate cells it has assembled a calculus of strategic interaction (Chapter 9) and its four great expenditures — ballots for what strangers think (Chapter 10), bargains and arguments for what they want and believe (Chapter 11), prices for what they cannot all have (Chapter 12), and coalitions, organisations, and institutions for the strangers who stop being strangers (Chapter 13). The instruments stack: markets presuppose identity, sanctions presuppose registries, organisations presuppose rules — institutions all the way down.
One assumption, though, has run beneath all five chapters, unexamined because Part IV needed it: the players are fixed. Real agents — the trained, fine-tuned, feedback-driven kind this book is actually about — do not stay put. They adapt, and they adapt to the rules, which turns every institution in this part into a curriculum and inverts the design question one final time: not “what will these players do under these rules?” but “what will these rules teach the players to become?” That is learning in multi-agent systems, it is where the mathematics gets strange and the engineering gets urgent, and it is Part V.
13.6 Summary
- Coalitional game theory asks two questions: who joins whom, and who gets what. The characteristic function prices every alliance, and finding the best partition into working groups is computationally hard in a way orchestrator designers inherit unknowingly.
- The core is stability, and it can be empty. A division is in the core when no subgroup could do better by walking out — and some perfectly reasonable games have no such division; endless renegotiation is sometimes a property of the situation, not a failure of the negotiators.
- The Shapley value is fairness axiomatised, and its second career is credit assignment. Pay each member its marginal contribution averaged over every order of assembly — the unique division satisfying mild axioms; the same arithmetic now attributes predictions to features and team performance to members.
- Organisations are patches for bounded minds and costly transactions. Coase explains why the boundary exists; Simon explains why there is structure inside it. A role is real when it changes information flow, authority, and accountability; a job title changes none of them.
- Institutions are the rules that outlast the players. Norms bind where conventions merely coordinate — obligation, violation, sanction — and the harness holds an option human institutions envy: regimentation, making the violation impossible instead of expensive.
- Reputation is the folk theorem made portable, and it runs on identity — which sybils and cheap pseudonyms counterfeit, so identity is an institution someone must build. Part IV ends where it began, with the rules deciding the game; Part V withdraws the last assumption — the players start learning.
13.7 Exercises
Exercise 1. The orchestrator prices a worker pool exactly as Section 13.1 prescribes — by running every subset on the sprint’s task suite. The pool holds two coders c and d and a tester t, and the logged suite scores are v(\{c\}) = v(\{d\}) = 42, v(\{t\}) = 0, v(\{c, d\}) = 68, v(\{c, t\}) = v(\{d, t\}) = 61, and v(\{c, d, t\}) = 84, with v(\emptyset) = 0. (a) Test superadditivity on every disjoint pair of non-empty coalitions: list each violation, say in a sentence what the violations have in common, and name the law of Section 13.1 they measure. (b) Enumerate all five ways of partitioning the pool into working groups, total the value of each, and identify the optimal coalition structure; two features of the winner deserve a sentence apiece — what became of the grand coalition, and where the agent that is worthless alone ended up. (c) The chapter asserts that twenty agents admit “some fifty trillion” partitions; verify it. Taking B_0 = 1 and B_{n+1} = \sum_{k=0}^{n} \binom{n}{k} B_k for the number of partitions of an n-element set, compute B_{20} exactly; compare it with the 2^{20} ablation runs that would price every coalition of twenty agents; and state which of the theory’s two questions — what a group is worth, or how best to group — is the computationally hard one here, and by what factor at n = 20.
Exercise 2. Section 13.2 leaves the 300-token majority game cycling forever (Figure 13.2); this exercise prices the repair the chapter prescribes — change the values, change the game. The orchestrator adds a completion bonus of B tokens paid only if all three agents finish together, so that v(N) = 300 + B, while any pair can still seize 300 and a lone agent still earns nothing. (a) Show that the core is non-empty exactly when B \ge 150: derive the necessity from the three pair inequalities, and establish sufficiency by exhibiting an allocation that satisfies them all. (b) Show that at B = 150 the core is a single point, and name it. (c) At B = 210, describe the core completely as a system of bounds on the three shares, show that the reviewer’s stable share ranges exactly from 90 to 210 — stability constrains without choosing — and compute the Shapley value of the subsidised game from two axioms, without touching the closed form; check that it sits inside every bound with room to spare. (d) Watch the theory happen: implement the myopic renegotiation loop in which, starting from the equal split of v(N), the first agent holding a profitable deviation lures the poorest other agent still being paid (ties broken in the fixed order coder, tester, reviewer) with that agent’s current share plus 10 tokens, keeps the remainder of the 300, and deviates only if the remainder strictly beats its own current payoff; run it with cycle detection at B \in \{0, 120, 150, 210\} and report what happens in each case — then say in one sentence why no prompt engineering applied to the three negotiators could change the B = 0 outcome. (The game itself ships as majority_game in the companion repository’s foundations/algorithms/shapley.py, though the loop needs nothing but the story.)
Exercise 3. A sprint’s ablation table decomposes cleanly: the coder alone ships 40 suite points; the tester adds 18, but only alongside the coder; the reviewer adds 12, again only alongside the coder; and a final 14 points of integration polish appear only when all three work together. (a) Write the characteristic function as the weighted sum v = 40\,u_{\{c\}} + 18\,u_{\{c,t\}} + 12\,u_{\{c,r\}} + 14\,u_{\{c,t,r\}} of unanimity games, where u_T(S) = 1 if T \subseteq S and 0 otherwise, and tabulate all eight values of v. (b) Derive the Shapley value of a unanimity game u_T from three of the four axioms — players outside T add nothing to any coalition, players inside T are interchangeable, and the shares must exhaust u_T(N) = 1 — without evaluating the closed form. (c) Now let the fourth axiom, additivity, do the work the formula would have done: read off the team’s exact shares as fractions and confirm they exhaust 84. (d) Check your fractions against the chapter’s shapley function, which ships verbatim in foundations/algorithms/shapley.py. (e) Test whether this fair division is also stable — verify every secession inequality — and reconcile the answer with Exercise 2 in a sentence: what do the two games say about when fairness and stability coincide?
Exercise 4. Table 13.1 asserts that the intuitive audit fails in both directions; make both failures numeric. Game R — the redundant pair: the coder is worth 40 on its own and test coverage is worth a further 30 whenever at least one of two testers t_1, t_2 is present, so v(S) = 40 \cdot [c \in S] + 30 \cdot [S \cap \{t_1, t_2\} \neq \emptyset], square brackets worth 1 when their condition holds and 0 otherwise. Game C — the complementary pair: nothing ships unless the coder and the reviewer are both present (jointly worth 80), and the tester adds 10 alongside both, so v = 80\,u_{\{c,r\}} + 10\,u_{\{c,r,t\}} in Exercise 3’s notation. (a) For each game compute the leave-one-out audit \mathrm{LOO}_i = v(N) - v(N \setminus \{i\}) by hand; show that Game R’s audit sums to 40 against a team worth 70, identifying precisely what the missing 30 is, while Game C’s sums to 190 against a team worth 90. (b) Compute the Shapley values of both games by hand — Exercise 3’s decomposition makes Game C a one-liner — and confirm each exhausts v(N). (c) Implement loo alongside the repository’s foundations/algorithms/shapley.py and tabulate audit beside fair share for both games. (d) Exactness costs an exponential; implement the remedy the chapter names: estimate \phi on Game C by averaging marginal contributions over m sampled arrival orders, measure the mean absolute error of the coder’s estimated share at m = 100 and m = 10{,}000 over twenty independent runs, confirm the shrink is consistent with the 1/\sqrt{m} rate, and say why this estimator — not the exact sum — is what runs inside every production SHAP implementation.
Exercise 5. The team’s norm reads “nothing merges without the reviewer’s token”, and one release cycle supplies the economics: 40 merge attempts; 3 would-be shortcut merges, each saving its coder 800 tokens of review latency and each causing 5,000 tokens of expected downstream damage if it lands; 1 genuine emergency in which waiting for review costs 12,000 tokens of outage while the merge itself is sound; an audit agent that reads merge logs at 150 tokens per merge and detects an unreviewed merge with probability p_d = 0.5; and fines that are transfers into the team’s shared pool, not burnt tokens. (a) A rational agent violates when its private gain exceeds the expected fine p_d f: find the window of fines that deters every shortcut yet lets the ambulance through, and verify that f = 2{,}000 sorts all four candidate violations correctly. (b) Price the two regimes over the cycle — the wall (regimentation: the unreviewed merge is unrepresentable) against the fine at f = 2{,}000 with every merge audited — name the winner, and in doing so say what a fine that is a transfer costs the system, and where enforcement’s real deadweight sits. (c) Find both break-evens: the audit price per merge at which the wall draws level, and the emergency frequency per cycle below which the wall wins; state the resulting decision rule and check it against the chapter’s — where violation is catastrophic or irreversible, build the wall. (d) Ostrom’s graduated sanctions (Table 13.2), priced: against the flat fine of 2,000, evaluate the schedule 500, then 2,000, then 8,000 for the first, second, and third detected offences — the expected penalty at each rung, the rung at which the persistent violator is deterred, and what an honest one-off lapse pays under each regime; then let detection collapse to p_d = 0.25 with fines capped at 2,500 by the offender’s remaining budget, show the deterrent window is now empty, and conclude in the chapter’s terms what enforcement actually runs on.
Exercise 6. Every number in this exercise is a consequence of what a name costs. (a) Sybils. The platform computes standing by strict majority of good over bad reports from distinct identities; a shirking contractor has earned 6 truthful bad reports, and 3 honest counterparties report good. How many fresh keys must the contractor mint, each filing “good”, to flip its own standing — and what does the attack cost when keys are free? If registering a key costs F tokens, what F makes the forgery unprofitable against a contract worth 2,000 tokens? State the theorem-shaped reason from Section 13.5 why no purely local test can prevent the minting itself. (b) Whitewashing. An honest name earns 100 tokens per round indefinitely; a cheat skims an extra 150 in one round, after which the name is burnt — detected at the round’s end and never hired again. With free names and trusting defaults, compute the whitewasher’s per-round earnings and show that cheating dominates honesty; then find the smallest entry fee per name that restores honesty, and name the quantity it equals. (c) Probation. Suppose the platform instead trusts no newcomer: for its first k rounds a fresh name receives only low-stakes work paying 50 per round with nothing worth stealing, and full trust thereafter. Compute the whitewasher’s per-round rate as a function of k, find the smallest deterrent k, and price the distrust tax this levies on every honest newcomer — comparing it with (b)’s entry fee and saying carefully who pays under each design. (d) Generalise (c): with cheat premium g and probation wage w < 100, show the deterrent probation is k_{\min} = \lceil g / (100 - w) \rceil and that the minimum tax on an honest newcomer is at least g, exactly g when 100 - w divides g (as here) — the invariant that someone must forfeit no less than the cheat premium once per name — then place fee and probation among the chapter’s ways of making a name cost something, and say which the chapter’s evidence-based reputations (signed attestations, verifiable logs) would substitute for both.
Further exercises for this chapter continue in the web edition’s exercise bank.
