(Originally posted by Pat in 2/2012)
Logicians occasionally talk of something called “common knowledge”,
in which given two people, A and B, and a proposition X, A knows X, B
knows X, A knows that B knows X, B knows that A knows X, “and so on”, as
they are wont to say. Unfortunately, that “and so on” includes quite
literally an infinite series of knowledge claims. Given that the capacity of the human brain is large but finite, this poses a rather serious problem.
A number of interesting theorems can be proved regarding common knowledge; of particular note is the Aumann Agreement Theorem,
which proves that if A and B share common knowledge of each other's
beliefs and A and B are perfectly rational, then A and B agree on every
belief. That is, great minds think alike—insofar as people are rational, they can never agree to disagree.
case involves the theory of mutual consent; one (“strong”) definition
of mutual consent involves common knowledge of consent, such that A and B
only really share mutual consent if A knows that B knows that A knows
that B consents, “and so on”.
But the non-finiteness of common
knowledge raises some very serious problems here. We already knew we
weren't perfectly rational—but now it seems we aren't even capable of
common knowledge, and perhaps not even capable of mutual consent!
gets worse: Consider the task of conveying a signal across a lossy
channel (and in real life, all channels are to some degree lossy). If I
want to send you a string of data, I presumably want to know that you
received it properly. But in order to tell me you received it, you'll
need to send me back another signal, which is subject to the same risks
of data loss as the original signal. I could send you a response
confirming receipt, but the problem persists—ad infinitum. It begins to seem like we need “common knowledge” of the signal, but then our brains need to be infinite!
One possible solution (which, oddly, I've never heard anyone seriously propose) would be to say that common knowledge is a convergent infinite
series, such that the infinite number of terms sums to a finite value
in terms of memory space and processing power. Suppose it takes half as
much space in A's brain for A to know that B knows X than it does for A
to know X; then, it would only take twice as much space to have “common
knowledge” as to have private knowledge.
Unfortunately, this is
quite implausible; as you can probably already feel from the awkwardness
of trying to process a statement like “A knows that B knows that A
knows that B knows that X”, raising the order of intentionality invariably involves an increase in the memory requirements, and a monotonic increasing infinite series can never be convergent.
alternative that might work better is to use a definition of
“knowledge” (and hence of “belief”) that doesn't actually require
cognitive processing. So for instance, we can say that I “believe” that
the third-nearest star to the eighteenth-largest black hole in the Milky
Way is not made of cheese, even though I'm quite sure I've never even
contemplated the notion before. In the relevant sense, I did not come to believe this merely because I happened to think of it; I already believed it and merely in some sense activated that
pre-existing belief. Yet it's quite clear that I can have infinitely
many “beliefs” in this sense, since as long as the universe is infinite
you can slot in a countable number of black holes, distance choices, and
galaxies in the above “belief”. In a similar fashion, I can have
infinitely many “beliefs” about the logical consequences of propositions
that I hold to be true, such as my “belief” that the 2^227th
prime number is not divisible by 2^14. I “believe” in this sense that
there is not a unicorn in my basement, and not three unicorns, and not,
for all n in N, n unicorns. I also “believe” that
there is not a yeti, a square triangle, or a black hole in my basement.
And you can keep on adding things that I “believe” as long as you
like—in theory until the Sun explodes.
The problem here, it seems to me, is that knowledge of knowledge of knowledge does not appear to follow logically from mere knowledge of knowledge. (And certainly, knowledge of knowledge definitely does not follow,
even causally, let alone logically, from knowledge.) So then we'd need
some method of generating knowledge which also generates knowledge of
knowledge and knowledge of knowledge of knowledge, and we'd have to know
that we had this. Hence, “common knowledge” would involve beliefs of
the sort above, where I know what the consequences of carrying out the
processing would be, but can't actually carry out the processing for all
the cases because there are infinitely many. This may be possible, but
it needs to be considered much more carefully than I've ever seen
“common knowledge” considered. How does saying “I'm sorry; it's my
fault” or “All of you can see at least one dirty face” (to use the
examples presented in the SEP entry on common knowledge) provide that kind
of information? Usually it's simply assumed as an axiom that K(A)
implies K(K(A)), but I can guarantee you right this minute that you know
things you don't know you know. Intriguingly, I could probably bring
them to your attention and thereby make you know that you know... so
maybe they are this sort of “inactivated belief”?
In any case, I think there's a much easier solution.
general technique I would like to see used much more in economics,
cognitive science, and other behavioral sciences is what I would call
“achieving the impossible”, that is, asking how in practice a problem can actually be solved by real-world behaviors, even if it can be mathematically proven that in principle the problem is “impossible” on an unrestricted domain.
for instance, instead of worrying about the Problem of Induction
because in some logically possible universes induction would
systematically fail, we should focus on the fact that in our own
universe induction has a fantastically good track record of accuracy—a
track record that quite simply no other method can get even close to
matching. Rather than wondering whether the sky might really be bleen, we should be focusing on the obvious fact that it is blue.
than wondering whether some fantastical Martian psychopath would
systematically violate our assumptions about morality, we should be
working on solving real-world problems that are already almost
universally agreed to be bad, like poverty, war, and disease. Could some
theoretical being possibly exist which might think that genocide is
good? Maybe—but I am not that being, and I really don't see why I should
care what it thinks.
Similarly, rather than fretting over the
Halting Problem as it applies to all possible computer programs, we
should (and indeed most computer programmers do) focus on the usual
causes of infinite loops in computer programs, and devising tools to
A similar, but not identical, case, involves the
situation when the “impossible” isn't actually proven impossible—it's
only proven impossible by the overly narrow methods proposed. Taking the
cube root of 2 is a mathematically trivial task—your cell phone can do
it—as long as you don't restrict yourself to an ideal compass and
straight-edge. It's impossible to write down all the digits of
pi, but once you've written down the first fifty or so you already have
plenty for any possible real-world application—you could literally
determine the precise number of atoms in a proposed Dyson Sphere.
To use a more important example of this latter, Arrow's Impossibility Theorem
really should be called the Range Voting Theorem, because all of its
requirements are satisfied by range voting if “unrestricted domain” is
loosened just a tiny bit so that voters are allowed to express cardinal
differences between candidates rather than mere preferences. If you've
ever thought to yourself something like, “Mitt Romney is a little better
than Newt Gingrich, but Newt is a lot better than Rick Santorum, and
Obama is way better than all of them” or “I like chocolate and vanilla
about the same, chocolate a bit more, but I like them both much better
than strawberry”, you are implicitly using the kind of utility
calculation that Arrow apparently thinks humans are incapable of doing.
Frankly I'm not sure if we ever judge preferences that aren't based
on some sense of cardinal utility; I have trouble imagining a case
where I would prefer A to B but wouldn't have at least some vague idea
of how different I felt them to be.
Returning to the issue
of common knowledge, instead of panicking because “true common
knowledge” appears to be impossible, we should be asking how this sort
of communication and mutual-knowledge problem can be resolved in
So let's consider a real-world
communication problem. Suppose I am a military commander trying to
organize a deployment by radio. I know that radios can be jammed (or
otherwise fail due to weather conditions, etc.), but there's simply no
time to meet all of my lieutenants in person. (Indeed, even then, we
could point out that there is a chance they would mishear or
misunderstand the orders as delivered in person.)
How can this difficult coordination problem be solved? Well, it pretty much has been,
and the methods used are standard operating procedure in all NATO
militaries. “Alpha tango two two niner. I repeat, alpha tango two two
niner.” “Roger that, solid copy.”
First, there is the use of error-correcting codes.
The data in “Alpha tango two two niner, I repeat, alpha tango two two
niner” is considerably more redundant than “A T two-twenty-nine”, and
indeed takes longer to say as a result. This redundancy is a strength,
not a weakness; it allows a portion of the signal to be lost without
losing the vital information. If you heard a message even as garbled as
“-pha -ngo two two --- peat al- ta--- two -er”, you could actually piece
together the whole message.
But you probably wouldn't, which
brings me to the second part, the reply: “Roger that, solid copy.” You'd
only say this if the message sounded right—that is to say, that if the message you received had the right form and structure and didn't appear to be missing anything.
How would you know? Couldn't a Cartesian Demon be deceiving you? In principle, yes. But in practice, there's a very simple method: Listen to the ambient noise. If
the ambient noise is continuous and consistent with the environment you
expect your commander to be in, you can thereby conclude that the
message is probably complete (or nearly complete), and so you can
respond with “Roger that, solid copy.” If the ambient noise had sounded
garbled, you would respond differently, with “Negative, bad copy. Say
Why use the ambient noise? Because it is not redundant—indeed,
it is highly dependent on precise fidelity. This is why it is useful to
you; if the ambient noise comes through well, you know that the actual
message is almost guaranteed to be accurate, since it is encoded in a
much more redundant way.
Hence, the solution to this coordination problem is to use an error-correcting code for the data you need, and an error-prone code
for extra data you don't actually need. This may seem a bit
counter-intuitive—why use an error-prone code? It's precisely because
you want to detect any errors that may arise. Once the error-prone code
is passed through without loss, you can safely send the real signal in
This doesn't solve the problem of signals
being overheard by the enemy; how can we do that? Again, we have a
method in practice: Encryption. It's not perfect—there's always
a chance of the encryption being broken—but it can be made almost
arbitrarily good by using more complex and more secure encryption.
Indeed, every time you type in a URL that begins with https:// you are
placing your trust in the power of encrypted signals over lossy
Once the commander hears “Roger that, solid copy”, the communication ends. There's
no reply-reply, “Solid copy your solid copy”; there's certainly no
reply-reply-reply “Solid copy your solid copy of my solid copy.” There
simply isn't any attempt to achieve what the logicians call “common knowledge”; and this is because there doesn't need to be.
the commander hears back (with good ambient noise of course) “Solid
copy”, the communication can end. The commander knows that the
lieutenant knows the orders; the lieutenant knows the orders. The
lieutenant doesn't need to fret over whether he knows that the commander
knows that he knows the orders.
Why not? I can think of at least
three reasons: One, the lieutenant is the one carrying out the orders,
so he's the one who actually needs to know. Two, the commander came up
with the orders in the first place, so he damn well better know them.
And three—perhaps most significant for our general model of knowledge—the commander could say something if he didn't.
the commander heard back, “Rog--- at, -- id -opy.”, he would know that
the radio channel was good in one direction—the command-to-lieutenant
direction, since the most likely thing the lieutenant was trying to say
was “Roger that, solid copy.” But he also knows that there is some
unreliability in the channel in the opposite direction, and if this is
important, he can come back with “Bad copy, lieutenant. Say again?”
Hence, the absence of a signal can be a signal. If the lieutenant doesn't hear
any kind of reply to his “solid copy”, he can reasonably infer that
this is because the message was received correctly. He then won't
respond, and the commander won't respond to his non-response. The
escalating size of signals responding to signals leading to a divergent
series is truncated, because now all but a small number of signals
require zero memory space.
I've encountered a rather humorous
failure mode of this generally effective system, which is when two young
lovers who are very insecure about their relationship end up in a long
succession of “I love you” “No, I love you” “No I love you more” and so
on. Each fears that a null signal will not be taken as a valid
signal, and as a result the conversation goes on not until common
knowledge is achieved, but instead until they finally give up out of
embarrassment and exhaustion. Frankly, I suspect that it is the most
insecure of relationships which function this way; two people who were
really committed to each other would have no problem with null signals,
and might literally say something like “Love you.” “Roger that.” and
What this means is that with mature norms of
communication in place, we simply don't bother with the logician's
“common knowledge”. I know X, I make sure you know X, you respond so
that I know you know... and... well... that's pretty much it. I
know you know I know is really about as far as it ever gets. I could
imagine certain scenarios where we might go as far as knowing you know I
know you know, but any further and I can barely hold the concept in my
brain, much less come up with a scenario where it would be useful.
does this work? In a word: Probability. You can always come up with
possible cases where these methods wouldn't work—a lucky guess on the
encryption, a null signal due to a sudden loss of communication, ambient
noise that glitches in precisely the right way to sound like ambient
noise is supposed to, and so on—but the methods used will make these
outcomes extremely unlikely, and in practice typically so unlikely they
aren't worth worrying about.
In fact, this is the underlying current of all the “achieve the impossible” problems—you can't devise any possible system for guaranteeing success, so instead you hunker down and devise a method for maximizing the probability of success. You accept error in order to make less error.
Hence, I find Pinker's argument that euphemisms produce mutual knowledge without common knowledge deeply unconvincing. Of course you can't produce common knowledge—that's infinite. You couldn't produce it with direct speech either! Moreover,
are you really failing to produce “I know you know I know” by saying,
say “Come up to my room for coffee” instead of “Let's have sex”? Some of
Pinker's other suggestions—that it prevents punishment if you have
misjudged the situation, or that it is perceived as “uncertain” rather
than “certain” in a qualitatively different way—strike me as more
plausible. Also, Pinker wants to make indirect speech rational, and I'm
frankly not sure that it is. Especially once a euphemism becomes
established, it ceases to be effective, and so new euphemisms must be
coined. Hence “senior citizen” is no longer as acceptable as it once
was, and “colored people” is downright unacceptable, even though they
were both coined with the express purpose of being socially acceptable
euphemisms (for “old” and “Black” respectively). “Homosexual” used to be
the standard term (as did “Negro”!), but now anyone who uses it sounds
anachronistic if not homophobic. There's something inherently unstable
about indirect speech; indeed in many cases it seems outright deceptive.
Instead of actually facing up to the fact that aging is a bad thing
(not to be confused with living a long time, which is a good
thing—immortals live a long time but do not age) and Black people and
homosexuals are unfairly disadvantaged in American society, we make up
different ways of saying things in order to feel better. Instead of
actually, you know, finding ways to eliminate racism, we instead try to
make ourselves less uncomfortable with it by coming up with new words
for the people harmed by it. Maybe euphemisms are sometimes rational
(perhaps in precisely the cases where deception is justifiable, for
instance); but I find it quite ridiculous that the
mutual-knowledge/common-knowledge distinction justifies their wide use.