%%{init: {"theme": "base", "themeVariables": {"primaryColor": "#E8ECFF", "primaryBorderColor": "#4054B2", "primaryTextColor": "#16171B", "lineColor": "#3B4351", "actorBkg": "#E8ECFF", "actorBorder": "#4054B2", "actorTextColor": "#16171B", "signalColor": "#3B4351", "signalTextColor": "#16171B", "noteBkgColor": "#F7E6B5", "noteBorderColor": "#8A5A00", "noteTextColor": "#16171B", "activationBkgColor": "#EFE9DC", "activationBorderColor": "#766F65", "labelBoxBkgColor": "#EFE9DC", "labelBoxBorderColor": "#766F65", "labelTextColor": "#16171B", "loopTextColor": "#16171B"}}}%%
sequenceDiagram
autonumber
participant A as General A
participant B as General B
A->>B: "attack at dawn"
B->>A: "ack"
A->>B: "ack of the ack"
B--xA: "ack of that ack" --- lost ✗
Note over A,B: each acknowledgement adds one rung<br/>of mutual knowledge --- and the last<br/>messenger can always be lost
6 Knowledge, Belief, and Common Ground
Chapter 5 was about getting a message across; this one is about what the message lands in. However faithfully delivered, a message changes nothing until it meets the epistemic state of its receiver — and the precarious, partly overlapping, frequently mistaken thing that sender and receiver come to hold between them is this chapter’s subject. A roomful of agents is not merely a roomful of message queues; it is a roomful of beliefs, each agent confident of a slightly different and occasionally false account of the world, the task, and what the others are thinking. The classical literatures — Hintikka’s epistemic logic, the theory of what a group knows, belief revision, theory of mind — all reappear, renamed and frequently reinvented, the moment a system contains more than one agent with more than one view of the facts.
The governing distinction is between information an agent has and information the agents share — and, cutting across it, between belief and knowledge. The first is the engine of everything multi-agent: knowledge is distributed, and the system’s intelligence depends on whether the fragments can be brought into alignment. The second is the standing hazard. What sits in an agent’s context window, its memory, its retrieved documents (Section 4.14), is belief: a claim the agent will act upon, which may nonetheless be false, stale, planted, or sincerely mistaken — and nothing inside the agent can tell it apart from knowledge, because a false belief and a true one feel, from within, exactly alike. This chapter is about the knowing itself; what a team does with it — cooperate (Chapter 7), coordinate (Chapter 8), reason strategically (Chapter 9) — is the chapters that follow.
6.1 Knowing, Believing, and the Difference That Matters
The orchestrator holds the specification; the coder holds the half-written diff it has not yet shown anyone; the tester holds a stack trace from a run the others did not see. Each acts, confidently, on its own private account of the task, and the accounts do not agree. This section supplies the vocabulary for talking precisely about such private accounts, and the agent-builder who lacks it will keep mistaking belief for knowledge at considerable expense.
Take the operational fact first. An agent acts on whatever it currently takes to be the case — the contents of its context window, its memory, the documents it has retrieved (Section 4.14). Call this its belief: a proposition the agent will reason and act upon as though true, whether or not it is. Knowledge is the stronger thing, and the tradition running from Plato’s Theaetetus onward analysed it as justified true belief. Gettier (1963) famously punctured the analysis, and epistemologists have been patching the definition ever since; the agent-builder need not adjudicate that quarrel, for what matters is the part nobody disputes: knowledge entails truth, and belief does not. The agent has beliefs; whether any of them rises to knowledge depends on the world and on the warrant, neither of which it can read off the belief itself.
To reason about this with precision, logicians made knows a formal operator. Hintikka (1962) took the modal logic whose box had meant necessarily and reread it as the agent knows that — epistemic logic. Its semantics, borrowed from Kripke’s (1963) possible-worlds apparatus, is worth carrying about as a picture. An agent entertains a set of possible worlds — every way the world might be, for all it can tell — and knows p exactly when p holds in all of them. Knowing is thus the elimination of possibilities: to learn something is to strike out the worlds inconsistent with it. Ignorance, symmetrically, is worlds left standing: the coder that cannot tell whether the build is green entertains a pair of surviving worlds no observation has yet told apart.
The picture reduces the crucial difference between knowledge and belief to a single line of the logic. Knowledge is veridical: the axiom K\varphi \rightarrow \varphi — if an agent knows p, then p — holds. Belief carries no such guarantee: B\varphi \rightarrow \varphi is not an axiom, because a believer’s actual world may sit outside the set it entertains — it may have struck out the truth by mistake. That is the entire difference (Table 6.1), and exactly the difference that bites.1 A language model’s confident assertion expresses, at best, a belief: nothing in the machinery that produces it guarantees that the actual world is among those in view. A true belief and a false one emerge in the identical fluent prose; the hallucination of Section 2.3 is simply a belief mistaken for knowledge, one that felt no different from the inside. No agent can tell the two apart by introspection — so the burden of telling them apart must be discharged outside its confidence.
| Dimension | Knowledge (K) | Belief (B) |
|---|---|---|
| What it is | Justified true belief — believed, true, and suitably warranted | A proposition the agent reasons and acts upon as though true, whether or not it is |
| Entails truth? | ✓ | ✗ |
| Veridicality axiom | K\varphi \rightarrow \varphi holds | B\varphi \rightarrow \varphi is not an axiom |
| The actual world | Always among the worlds the agent considers possible | May sit outside the set the agent entertains — the truth struck out by mistake |
| A language model’s confident assertion | Never guaranteed to be this | At most this — and felt, from the inside, identical to knowledge |
So far, one mind. Admit the others and knowledge becomes distributed: scattered in fragments, no one of which is the whole. Fagin, Halpern, Moses, and Vardi (1995) give the group’s latent knowledge its own name — distributed knowledge, what the team would know if every member pooled what it held. In the possible-worlds picture it is the intersection of everyone’s surviving worlds, and it routinely exceeds the knowledge of any member. The orchestrator knows the specification forbids a schema change; the coder knows its diff performs one; the tester knows a migration test has just gone red. No single agent knows the system is about to ship a bug — yet the knowledge is there, distributed across the three, waiting to be assembled.
This is the optimistic reading of why one builds a multi-agent system at all: the team can know more than any agent it is made of. The pessimistic reading is most of the rest of this book: distributed knowledge is latent, and making it actual requires communication, which Chapter 5 showed to be neither free nor lossless.
The discipline these distinctions recommend is among the most useful a multi-agent engineer can adopt, and the least often followed. Treat everything an agent holds as belief — defeasible, fallible, owing its credence to some source — and reserve knowledge for propositions checked against the world. The coder’s cheerful “tests pass” (Section 5.1) is a belief offered for adoption; it becomes knowledge only once the tests are actually run, and an orchestrator that banks it as knowledge on the strength of the coder’s tone has confused the two operators. Three questions follow, taken in turn: how fragments of distributed belief become genuinely shared (Section 6.2); how to change a belief the world contradicts (Section 6.4); and how much credence a belief deserves given where it came from (Section 6.5).
6.2 What Everybody Knows: Common Knowledge and Common Ground
The orchestrator’s knowing the release plan and the coder’s knowing it too is mere mutual knowledge — two private beliefs that happen to coincide — and not nearly enough to coordinate on. For the two to act on the plan together, each must also know that the other knows it; and each must know that the other knows that they know it; and the regress does not politely stop. The limit of this tower — everyone knows p, everyone knows that everyone knows p, and so on without end — is common knowledge, the epistemic state watertight coordination — action in guaranteed lockstep — quietly demands; coordination that tolerates an occasional miss can get by on less. The notion is David Lewis’s (1969), introduced to explain how conventions hold: we drive on the left, or agree that “done” shall mean “the tests pass”, not because each of us has adopted the rule but because the rule’s being shared is itself out in the open, known to be known.
The tower must climb so high because coordination is a problem of matched expectations, undone by doubt at any level. Two agents converging on a rendezvous — a branch to build from, a schema both will assume — each choose on what they expect the other to do, which depends on what the other expects them to do, and so on up; where the choice has more than one workable answer, nothing pins down which both will pick except the mutually evident knowledge that this is the one. Lewis’s insight is that coordination runs on knowledge about knowledge: withhold it and a team of perfectly well-informed agents can still fail to move in concert, each privately ready and none quite certain of the rest.
Here the distributed-systems theorists arrive with bad news: in any setting where communication can fail, common knowledge cannot be achieved at all. The classic illustration is the coordinated attack problem — two generals on facing hilltops must charge at the same dawn or be beaten separately, and may communicate only by messengers who might be captured crossing the valley. The first general sends “attack at dawn”; he dare not charge until he knows it arrived, so he needs an acknowledgement; the second dare not charge until she knows her acknowledgement arrived; and no finite exchange of messengers ever completes the tower (Figure 6.1).
Halpern and Moses (1990) turned this folklore into a theorem: in a system where messages may be lost — or merely delayed by an unbounded amount — common knowledge can never be attained, full stop. The gap between arbitrarily high mutual knowledge and genuine common knowledge is precisely the gap that coordination, in the worst case, needs closed.
6.2.1 Common Knowledge, Formally*
The generals’ unfinished ladder is worth writing out, because the notation makes both the tower and the impossibility exact. Write K_i\varphi for agent i knows \varphi — the knowledge operator of Section 6.1, now subscripted. For a group G \subseteq N of the agents N = \{1, \dots, n\}, everyone in G knows \varphi is the plain conjunction
E_G\varphi \;=\; \bigwedge_{i \in G} K_i\varphi,
and the tower rises by iteration — E_G^{1}\varphi = E_G\varphi and E_G^{k+1}\varphi = E_G\bigl(E_G^{k}\varphi\bigr), everyone knowing that everyone knows, k storeys up. Common knowledge is the whole tower held at once,
C_G\varphi \;=\; \varphi \wedge E_G\varphi \wedge E_G^{2}\varphi \wedge E_G^{3}\varphi \wedge \cdots,
an infinite conjunction: no finite list of things checked off gets you there. The standard treatment (Fagin et al., 1995) prefers an equivalent and more revealing characterisation, common knowledge as a fixed point,
C_G\varphi \;\leftrightarrow\; E_G\bigl(\varphi \wedge C_G\varphi\bigr),
the epistemic state that reproduces itself under everyone knows: \varphi holds, everyone knows it holds, and everyone knows that this very state obtains.
In this vocabulary the theorem of Halpern and Moses becomes a one-sentence affair: each acknowledged message lifts the group from E_G^{k}\varphi to E_G^{k+1}\varphi, but after any finite exchange some agent still cannot exclude that the last message miscarried, so some conjunct of the infinite tower fails and the fixed point is never entered. The generals’ predicament is a property of the object they are pursuing: C_G\varphi does not sit at the top of any finite ladder.
If that were the end of the story, no two agents — and no two people — could coordinate on anything, which they plainly do. The resolution: perfect common knowledge is not actually required; a good-enough approximation is, built not in a single certifying handshake but by accumulation. Clark and Brennan (1991) named the approximation common ground — the stock of beliefs, references, and assumptions two parties treat as mutually held — and the activity of building it grounding. Conversation grounds incrementally: the parties look for positive evidence that a contribution was understood — an acknowledgement, a relevant reply, a correct next move — before banking it as common. “Done.” / “Got it, merging.” is a grounding exchange in miniature: the second turn converts a private utterance into shared ground. Where the evidence is missing or wrong, the parties repair — “which staging database?” — before anything is built on the flaw. Table 6.2 sets common ground beside the three formal notions it approximates and outperforms.
| Notion | What it names | Formal / structural form | How it is (or is not) reached |
|---|---|---|---|
| Distributed knowledge | What the group would know if every member pooled its fragment | Intersection of all members’ surviving possible worlds; routinely exceeds what any one member knows | Latent until made actual by communication (Chapter 5) |
| Mutual knowledge (everyone knows) | Each member privately knows \varphi, the beliefs merely coinciding | E_G\varphi = \bigwedge_{i \in G} K_i\varphi | Readily reached, yet not nearly enough to coordinate on |
| Common knowledge | Everyone knows \varphi, everyone knows that everyone knows, and so on without end | The infinite tower \varphi \wedge E_G\varphi \wedge E_G^{2}\varphi \wedge \cdots; a self-reproducing fixed point | Strictly unattainable through a channel that can fail (Halpern–Moses) |
| Common ground | The stock of beliefs, references, and assumptions two parties treat as mutually held | A working approximation to common knowledge, not a fixed point | Built incrementally by grounding; good enough, never perfect |
Grounding, crucially, is not free. Every acknowledgement, every read-back, every “did you mean the integration tests or the unit tests?” is effort spent, and the principle of least collaborative effort (Clark & Wilkes-Gibbs, 1986) is that participants ground only to the precision the task demands and no further, because over-confirming wastes as surely as under-confirming endangers.
For language-model agents the currency is tokens and latency. Ground heavily where a misunderstanding is expensive — an irreversible action (Section 4.7), a schema both sides must share — and lightly where a mistake is cheap to catch and cheaper to undo. A read-back before dispatch buys common ground for a few hundred tokens; whether that is a bargain depends entirely on what a misunderstanding would have cost. A serviceable rule of thumb: ground to explicit confirmation before any action you cannot cheaply undo (Section 4.7), and travel lighter everywhere else.
The failure mode to fear, then, is the agent that assumes common ground it has not paid for: the fire-and-forget dispatch that presumes its directive landed as intended, the worker that reports “done” and presumes the word means to its supervisor what it meant to itself. No protocol, however chatty, drives the residual uncertainty to zero — the coordinated-attack result guarantees as much — so dependable multi-agent systems treat shared state as something to be continually reconciled rather than once and for all established. Notice, finally, that grounding silently asks each party to model what the other already knows and what it still lacks: common ground is built by two agents each reasoning about the contents of the other’s mind — the faculty the next section is about.
6.3 Reasoning About Other Minds
To give a useful reply, or to judge that one has been understood, an agent must track not merely the world but the other agent’s picture of the world — holding beliefs about beliefs, its own about the world and another’s, kept carefully apart. Psychologists call this capacity a theory of mind: the attribution of unobservable mental states — beliefs, desires, intentions — to others, in order to explain and anticipate what they will do. The phrase is Premack and Woodruff’s (1978), who asked whether a chimpanzee had one; the question turned out to be hard for chimpanzees, subtle for children, and decidedly unsettled for language models.
The sharp test of the faculty is the false-belief task (Wimmer & Perner, 1983), best known in its child-friendly Sally–Anne restaging (Baron-Cohen et al., 1985) (Figure 6.2). Sally puts her marble in a basket and leaves the room; Anne, unobserved, moves it to a box; Sally returns — and the subject is asked where Sally will look. To answer “the basket” is to pass, and passing requires predicting Sally’s action from her belief rather than from the fact. It is precisely the belief-versus-knowledge distinction of Section 6.1, turned outward: a system that cannot represent another agent’s belief as possibly false will collapse it into the facts, predict that Sally walks straight to the box, and be wrong. A surprising amount of social prediction turns on not making that collapse.
For a multi-agent system this is no parlour trick but a daily operational necessity, already implicit in Section 6.2’s grounding. Deciding what to say is itself a theory-of-mind computation: the Gricean maxims of Section 5.5 — supply what the hearer needs, not what it already has — presuppose a running model of what the hearer knows, and an agent lacking one will either belabour the obvious or omit the essential. Noticing that a peer is about to act on a false belief — the coder building against a schema the orchestrator quietly changed two steps ago — is the false-belief task in working clothes; delegation is calibrated by the same faculty. Common ground, seen this way, simply is a theory of mind maintained over time — a running ledger of what the others do and do not yet hold.
The faculty also nests, and the nesting is where the difficulty lives. I model your beliefs; but your beliefs include a model of mine, which includes a model of yours — the regress of Section 6.2, folded inside a single agent’s head. Human reasoners are reliable for the lower orders and grow unsteady some floors up; machines can be prompted higher, but reliability thins with altitude, and most useful coordination is settled on the lower floors. Where the nesting meets conflicting interests — where modelling what you believe is the prelude to outmanoeuvring you — theory of mind shades into strategic reasoning, the business of Chapter 9. Perspective-taking is recursive in principle and sharply bounded in practice, and a system designed as though its agents model one another to unlimited depth has been designed for an agent that does not exist.
Whether a language model possesses any of this, as against impersonating it convincingly, remains genuinely open. Kosinski (2024) ran the classic false-belief tasks across a succession of models and found performance rising with scale — the strongest solving about three-quarters — arguing that a theory-of-mind-like capacity may have emerged as a by-product of learning to predict language. Ullman (2023) showed that trivial alterations leaving the underlying logic untouched — making the container transparent, say — send the same models off a performance cliff, exactly as one would expect of template-matching rather than reasoning about minds. The results are less contradictory than complementary: the models have learned something that travels with the familiar phrasing, and just as plainly lack the robust, perturbation-proof competence the phrasing was devised to detect. For the engineer, what matters is behaviour under distribution shift, and there the evidence counsels caution.
The design lesson follows directly. Assume the perspective-taking is real enough to be useful and brittle enough to fail silently — agents earnestly informing one another of what both already know; hand-offs presuming context never received; and, most dangerous, the peer labouring unnoticed under a false belief for the last six steps. The remedy is the one this chapter keeps arriving at: where it matters, do not leave others’ beliefs to be inferred but make them explicit — post the shared state, name what has changed (Section 6.6). And note the edge that turns sharp later: an agent skilled enough at modelling others to help them is, by the same skill, equipped to mislead them — persuasion, manipulation, and defence are Chapter 9’s and Section 20.9’s. One thread remains: to notice a false belief — a peer’s or one’s own — is to say a belief must be changed, corrected against the world without toppling everything that leans upon it.
6.4 Changing One’s Mind: Belief Revision
An agent has just found one of its beliefs to be false — its own, or a peer’s. Discovery is the easy part; what to do about it is not. The naive picture of learning is monotonic: facts accumulate, the pile only grows. Real reasoning is not like that: learning that the build is broken retracts the conclusion that the release can ship; learning that Anne moved the marble retracts all one had inferred about the basket. Conclusions that looked settled are withdrawn the moment the ground beneath them shifts — non-monotonicity, the reason a belief, unlike a theorem, is always held on sufferance. The difficulty lies not in adding the new fact but in deciding what of the old must give way, without pulling down more than necessary. That problem has a name — belief revision — and a theory.
The theory is owed to Alchourrón, Gärdenfors, and Makinson (1985), whose initials it now wears: the AGM account of theory change, distinguishing three operations upon a body of belief. Expansion merely adds a new belief consistent with what is already held — the easy, monotonic case. Contraction gives a belief up, retracting it together with whatever support now dangles. Revision is the hard one: the arrival of a belief that contradicts the current set, and so demands that some of the old be surrendered first. The question revision poses — what to give up? — has no purely logical answer, because many different retractions would each restore consistency. AGM’s governing principle, sharpened by Gärdenfors (1988), is minimal change: give up as little as possible, and when forced to choose, surrender the beliefs you hold least firmly. That ranking is epistemic entrenchment, and it does the real work: it decides which of two colliding beliefs survives.
What makes revision genuinely awkward is that a belief almost never sits alone: it was inferred from others and supports others in turn, so retracting it can strand a whole subtree of conclusions that quietly leaned on it. The classical AI response was to mechanise the web: Doyle’s truth maintenance system (1979) — a reason maintenance system, more accurately — records, for each belief, the justification that holds it up; when something is retracted, it follows the justifications and recomputes what still stands, so that the agent’s beliefs stay a coherent whole rather than a midden of assertions some of which have quietly expired. Notice what this requires: to revise well, a system must record not merely what it believes but why. We shall find in Section 6.5 that this is the very bookkeeping that trust requires, reached from the other side.
Bring all this to a contemporary agent and observe that almost none of the machinery is present. An agent’s context window is, in effect, a cache of beliefs about the world, and a cache has exactly the failing the old programmer’s joke immortalises, that the two hard problems in computing are cache invalidation and naming things. The world moves; the cache does not notice: a document true last week is served up with no mark of its staleness, and a fact established early in a long task lingers, unrevised, long after it has ceased to hold.
Worse, retraction in a context window is not deletion. Telling a model “ignore what I said about the schema” does not remove the earlier assertion — it appends a second one on top, and both now sit in the tokens, leaving the model to adjudicate between them by the unreliable lights of primacy and recency rather than by entrenchment. A language model does not natively perform AGM revision; left to itself it tends to accumulate belief rather than revise it — precisely the wrong default in a world that keeps changing underneath it.
The multi-agent setting raises the stakes by making revision a thing that must propagate. When the orchestrator learns the schema has changed, the belief to be revised is scattered across every agent that was told, or inferred, the old one. Each must revise, or it carries on acting upon a fact retracted everywhere but in its own context — the false belief of Section 6.3, now self-inflicted and distributed. Without something to play the truth-maintenance role across the team — recording who was told what, and broadcasting the retraction — the system slides into incoherence: some agents on the new belief, some on the old, all confident, none aware of the split. This is cache invalidation promoted to a distributed problem, among the consistency hazards Chapter 8 takes up directly.
The discipline, then, is to build the bookkeeping that classical systems took for granted. Track why each belief is held, so that a retraction can find its dependents. Prefer re-deriving a belief from an authoritative source to the append-only correction the tokens never truly honour. Treat the context as a cache with an invalidation policy, not a log that only grows. And for beliefs the whole team shares, make the update explicit and broadcast (Section 6.6). One question remains open: minimal-change revision turns on entrenchment, and entrenchment, in any real system, is mostly a matter of where a belief came from — a reading from the production database outranks a guess from a flaky tool. What sets the ranking is provenance, the subject of the next section.
6.5 Provenance, Trust, and Whom to Believe
Weighing a belief by its source means first recording that source: the chain of sources and derivations that produced the claim. That record is its provenance. The database community, which has worried at this longest, distinguishes the why of a datum, the inputs that justified it, from the where, the source it was copied from (Buneman et al., 2001); both are exactly what Section 6.4’s justifications were, seen now as a property to be stored rather than an inference to be run. A bare proposition is only half a belief; the other half is its pedigree, and an agent that files claims without their sources has thrown away precisely what it needs to weigh them, and to revise them later.
Why the pedigree matters so much is the unwelcome discovery of Section 5.5: an assertion cannot certify itself. A message reading “the migration succeeded” carries no mark setting the truth apart from the lie, the sycophantic guess, and the confident fabrication — all arrive in the same fluent, untroubled prose. If the string cannot tell you whether to believe it, the only remaining purchase is outside the string: where it came from, and how that source has fared before. The receiver’s question is not the unanswerable “is this true?” but the tractable “who is telling me, and on what standing?”
Weighing sources by their standing is, of course, trust, and — the reader will not topple from their chair to learn it — the multi-agent systems community formalised trust decades before there existed an agent fluent enough to lie persuasively. Marsh (1994) gave computational trust its first sustained treatment, and a research programme followed, surveyed by Ramchurn and colleagues (2004): trust as a quantified expectation that a source will deliver what is needed, revised by experience. The literature draws a distinction the agent-builder should keep close, because on the wire the two failures look identical: trust in competence — is the source able, is it accurate? — and trust in honesty — is it even trying to tell me the truth? A tool that is sincere but buggy and an agent that is capable but deceptive both emit confident falsehoods, and a system that conflates the two will misdiagnose every one of them.
When an agent must judge a source it has never dealt with, it falls back on what others report of it — reputation, trust borrowed from the experience of the group (Sabater & Sierra, 2005): socially aggregated provenance, importing entrenchment about a stranger from the testimony of those who have met it. It is also, predictably, gameable — by collusion, by whitewashing a soiled identity, by manufacturing flattering testimony at scale — and the defences belong with Chapter 13’s trust and institution machinery. Whom to believe has a private answer, from one’s own dealings, and a social one, from everyone else’s; a serious system wants both.
The contemporary substrate makes all of this harder: it flattens provenance. Once a retrieved document, a tool’s output, or a peer’s claim is pasted into the context window, it becomes simply more tokens — indistinguishable from the system’s own instructions and from established fact. This is not only why models will cheerfully fuse a guess and a fact into a single seamless paragraph; it is the root of prompt injection (Section 5.5; Section 20.9), in which text that arrived as data is obeyed as instruction: the confused deputy of the security textbooks, wearing a language model’s credulity. And fluency is not provenance: the polish of the prose is uncorrelated with the reliability of whoever stands behind it. A model left to keep track of its own sources will not; the harness must keep track for it.
The defence is to carry provenance out of band, where the model cannot dissolve it. Tag each belief, structurally, with its source and standing; keep trusted instructions and untrusted inputs on separate footings; and when claims conflict, resolve by weight of source — supplying, at last, the entrenchment Section 6.4 was missing. Treat trust as earned and revisable; a confident tone is evidence of nothing. The deep apparatus is Chapter 13’s, and the adversarial edge Section 20.9’s. With provenance in place the chapter’s five obligations are assembled (Table 6.3); none of them maintains itself, and the closing section is about the plumbing that does.
| Epistemic object (section) | Classical source | How the substrate breaks it | The engineering remedy |
|---|---|---|---|
| Distributed knowledge (Section 6.1) | Hintikka’s epistemic logic; Fagin et al. on distributed knowledge | Stays latent — scattered across private contexts, actualised only by lossy communication | Pool the fragments; treat every claim as belief until checked against the world |
| Common ground (Section 6.2) | Lewis’s common knowledge; Clark and Brennan’s grounding | Common knowledge is unattainable over a fallible channel; teams assume ground never paid for | Ground incrementally, on evidence; confirm before any action you cannot cheaply undo |
| Other minds (Section 6.3) | Theory of mind; the false-belief (Sally–Anne) task | Model-held perspective-taking is brittle under distribution shift and fails silently | Make others’ beliefs explicit — post the shared state rather than infer it |
| Belief revision (Section 6.4) | AGM theory change; Doyle’s truth-maintenance systems | The context accumulates rather than revises; retractions append, and must still propagate team-wide | Record why a belief is held; treat context as a cache to invalidate; broadcast retractions |
| Provenance and trust (Section 6.5) | Computational trust (Marsh); reputation systems; database provenance | Flattens provenance, so data reads as instruction — the root of prompt injection | Carry provenance out of band; weigh by the source’s standing, never by confident tone |
6.7 Summary
- Belief is not knowledge, and an agent cannot tell which it has. What sits in context, memory, or retrieved documents is belief — actionable, and possibly false, stale, or planted; from the inside the two are indistinguishable, so an agent’s confidence certifies nothing.
- Knowledge is distributed. What a system knows is not what any one agent knows; epistemic logic gives the vocabulary for saying precisely who knows what, and where the gaps are.
- Common knowledge is what guaranteed coordination demands, and it is strictly unattainable. The coordinated-attack result shows the regress can never be finished through an unreliable channel; real agents settle for common ground, built incrementally and paid for by the layer.
- Agents must model other minds. What to say, what to withhold, and what an interlocutor has misunderstood all require a theory of mind — present in language models unevenly, and brittle under distribution shift.
- Changing one’s mind is a discipline, not a reflex. AGM belief revision and the truth-maintenance systems formalised what a multi-agent system re-encounters as stale context, cache invalidation, and mid-task propagation.
- Provenance is part of the belief, and shared belief has to live somewhere. Track the source, weight by trust, resist the collapse of an agent said so into it is so — and remember that shared state, the blackboard’s heir, moves the problem rather than dissolving it (Chapter 8, Chapter 20).
6.8 Exercises
Exercise 1. A task’s state turns on two propositions: g, “the build is green”, and s, “the schema has been migrated”. Write the four possible worlds as w_1, where both hold; w_2, where only g holds; w_3, where only s holds; and w_4, where neither does. The actual world is w_3. The tester (agent 1) has just run the suite but knows nothing of the migration: it cannot tell w_1 from w_2, nor w_3 from w_4. The coder (agent 2) performed the migration but has not run the tests: it cannot tell w_1 from w_3, nor w_2 from w_4. (a) Using the elimination-of-possibilities reading of Section 6.1, decide which of K_1 \neg g, K_2 s, K_1 s and K_2 \neg g hold at w_3, exhibiting the surviving worlds in each case. (b) Show that neither agent knows \neg g \wedge s — the fact that a red build now coexists with the new schema — and compute the pair’s distributed knowledge at w_3 as the intersection of their surviving worlds. What does the team know, in the pooled sense, that neither member knows alone? (c) The orchestrator, told “tests pass” two turns ago, entertains exactly \{w_1, w_2\}. Explain why its state is belief rather than knowledge: name the axiom that fails, and the structural feature of its world set that makes it fail. (d) The tester now reports “the build is red” to the orchestrator. Show that the strike-out-the-inconsistent-worlds update of Section 6.1 leaves the orchestrator entertaining no worlds at all, and name the operation of Section 6.4 that this collision calls for instead.
Exercise 2. An orchestrator can ground a hand-off with a read-back exchange — “so, to confirm: …” — costing g tokens, which cuts the probability of a misunderstanding from p to q; a misunderstanding that goes uncaught costs C tokens of redone work. Three hand-offs are on its desk: (i) the brief for a database cutover, with p = 0.08, q = 0.01, C = 60{,}000; (ii) a request to rename a local variable, with p = 0.10, q = 0.02, C = 800; (iii) instructions for formatting a report section, with p = 0.30, q = 0.05, C = 1{,}500. In every case g = 400. (a) Derive the general condition under which grounding lowers the expected cost; then compute the expected cost with and without grounding for each hand-off, and say which of the three to ground. (b) For hand-off (iii), find the break-even redo cost C^{*} above which the read-back pays for itself. (c) It emerges that hand-off (i)’s cutover would drop a customer table with no restore path. Show what happens to the decision of (a) as C grows without bound, and derive from it the chapter’s rule of thumb about grounding and irreversible actions (Section 4.7) rather than quoting it. (d) Reconcile your answers with the principle of least collaborative effort: why is the hand-off with the highest misunderstanding probability the one not worth grounding?
Exercise 3. Five coder agents, numbered 1 to 5, each own a branch, and a permissions quirk lets every agent see the CI status of the other four branches but never of its own. Branches 1, 2, and 3 are failing. At 09:00 the orchestrator posts “at least one branch is failing” to a channel all five read simultaneously — and that all read it, that all reason flawlessly, and that the following protocol is obeyed, are common knowledge. The protocol: time passes in synchronous rounds, any agent that knows its own branch is failing must declare so in that round, and every declaration and every silence is visible to all. Write \varphi for “at least one branch is failing” and G for the five agents. (a) Trace rounds one to three: explain the silences in rounds one and two, why agents 1, 2 and 3 all declare in round three, and what agents 4 and 5 learn from those declarations. (b) Every agent could already see at least two failing branches, so the announcement told no agent anything new about the branches. Show what it did change: verify that before the announcement E_G^{2}\varphi holds but E_G^{3}\varphi fails, by exhibiting the chain of nested doubt — the world agent 1 cannot exclude, the world agent 2 cannot exclude within it, and the world at which the chain bottoms out. (c) Prove by induction on k that with k failing branches the protocol produces its first declarations in round k, all k owners at once, and point to the step of the proof that consumes the announcement’s being common knowledge. (d) Suppose the orchestrator had instead sent the same sentence to each agent in a private message, all five delivered. Identify the exact step of your induction that now fails, and locate the failure at a specific world in (b)’s chain of doubt.
Exercise 4. A reviewer agent holds six beliefs. b_1: “schema v1 is live”, read from a configuration file at step 2. b_2: “the users table has a column email”, derived from b_1. b_3: “the diff’s query is valid”, derived from b_2. b_4: “the diff is safe to merge”, derived from b_3 and b_5. b_5: “the unit tests pass”, reported by the tester at step 5. b_6: “the release can proceed”, derived from b_4. The reviewer messaged b_2 to the coder at step 6. At step 9 a new item arrives: the migration log shows that schema v2 — which renames email to contact_email — went live at step 7. (a) Classify the change the newcomer demands as expansion, contraction, or revision, and say why. (b) Under the entrenchment ordering migration log > tester’s report > configuration-file read > derived beliefs, perform the revision as a truth-maintenance system would: give the retraction cascade in order, and state which beliefs are left standing. (c) Exhibit a different set of retractions that also restores consistency, and explain why logic alone cannot choose between it and yours — and what does choose. (d) Suppose the retraction is instead implemented by appending “ignore what I said about the schema” to the reviewer’s context. Name two distinct failure modes from Section 6.4 this invites; then say what the bookkeeping must have recorded for the revision to reach the coder, and what happens to the team’s state if it did not.
Exercise 5. Two sources conflict over \varphi = “the staging database is safe to reset”. Tool A, a schema inspector, has been right on 9 of its last 12 claims; agent B, a coder, on 17 of its last 20. A asserts \varphi; B asserts \neg\varphi. Treat each track record as that source’s reliability, take the sources’ errors to be independent, and give \varphi a prior of one half. (a) Compute the posterior probability of \varphi given the two reports, and say which claim a provenance-weighted store should bank. (b) The reset, it turns out, would destroy rows that expose a fault in code B itself wrote — and on the ten past claims touching its own code, B has been right three times. Recompute the posterior with that record and show that the ranking flips. What does the flip say about summarising a source in a single scalar, and which of the chapter’s two dimensions of trust — competence and honesty — does each of B’s records measure? (c) Return to the reliabilities of (a). A third agent C, with a record of 17 of 20, also asserts \neg\varphi. Compute the posterior twice: once treating C’s report as independent, and once on the discovery that C merely relays what B told it. What does the difference imply for reputation — trust borrowed from the experience of the group — and for the price of manufactured corroboration?
Exercise 6. Implement, in standard-library Python, a model checker for the epistemic logic of Section 6.2.1. A model is a set of named worlds, a valuation giving the atoms true at each world, and, for each agent, a partition of the worlds into indistinguishability cells; formulas are atoms, negation, conjunction, K_i, E_G, and C_G. (a) Implement evaluation, computing C_G\varphi at a world w as the truth of \varphi at every world reachable from w in one or more steps through any group member’s cells, and say in a sentence or two why that reachability computation is the fixed-point characterisation of Section 6.2.1 made algorithmic. Implement also the public-announcement update, which strikes from the model every world where the announced formula fails. (b) Encode the model of Exercise 1 and confirm your hand answers to its parts (a) and (b) mechanically. (c) Encode the branch-status scenario of Exercise 3 for three agents with branches 1 and 2 failing, and drive it round by round: check that before the broadcast E_G\varphi holds and E_G^{2}\varphi fails; that after the broadcast C_G\varphi holds; that round one passes in silence — announce that silence — whereupon both failing agents declare in round two; and that announcing the declarations lets agent 3 conclude its own branch is clean. (d) Scale to the five-agent instance of Exercise 3 and confirm mechanically that E_G^{2}\varphi holds and E_G^{3}\varphi fails before the broadcast.
Further exercises for this chapter continue in the web edition’s exercise bank.
For readers keeping formal accounts: with positive and negative introspection the knowledge operator satisfies the modal system S5; trade veridicality for mere consistency and belief’s ledger is KD45 (Fagin et al., 1995). The introspection axioms matter: Section 6.4 presumes an agent that can tell what it currently believes — for a language model, exactly the metacognitive access Section 3.13 declined to certify.↩︎