Wednesday, December 5, 2012

Common Knowlege is Even Rarer Than Common Sense

(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.
Another 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!

It 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.
An 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.

One 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.
So 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.
Rather 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 escape them.
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 real-world institutions.
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 again, command?”
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 error-correcting code.
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 channels.
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.
Once 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.
If 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 hang up.

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.
Why 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.

No comments:

Post a Comment