Epistemic logic and the problem of common knowledge

With the two generals, Cheryl's birthday, hidden surprises, blue-eyed islanders, pirate treasure division, philosopher's ruling council, coordination paradox, Fitch's paradox, Cheryl's rational gifts

Three logicians walk into the Logic Bar.

Waiter Do you all want beer?

First logician I don't know.

Second logician I don't know.

Third logician Yes.

Hilarious! ... did you get it?

To explain a joke is seldom funny, of course, but kindly humor me. The joke turns on epistemic logic, the logic of knowledge, for the waiter had asked whether they all want beer, you see, and so the logicians were answering not only for themselves but also regarding what they knew about whether the others wanted beer. Because the first logician said, "I don't know," it must have been that she wanted beer, but didn't know if everyone wanted beer. If she herself had not wanted beer, then she would have said simply "no," since she would have known that they didn't all want beer; but it would have been wrong for her to say "yes" merely because she herself wanted beer, not knowing about the others, since the question is whether they all want beer. Similarly, we can tell that the second logician must want beer, since otherwise he would have said "no," but he doesn't know whether the third logician also wants beer. Finally, the third logician, reasoning just as we have, knows that the other two want beer, and since evidently he also wants beer he says "Yes," since he now knows they all want beer.

In this chapter we shall have a series of fun epistemic logic puzzles, many of which will lead us to further serious issues in epistemic logic.

The two-generals problem

Let us begin with a classic problem in epistemic logic known as the two-generals problem. Two red generals and their armies are situated on mountains overlooking a valley between them.

They want to coordinate a joint attack on the blue army in the valley, but they are separated by the terrain and they must coordinate the precise details and timing of the attack in advance. If both attack simultaneously, they will succeed; but if either should delay or attack alone, they will both fail. Meanwhile, the communication channels are difficult and unreliable.

The first red general dispatches a messenger through the dangerous blue valley:

We attack at dawn; agreed?

The message gets through! The second red general replies,

Yes, at dawn! Please confirm.

He needs confirmation, you see, since otherwise he might think that the first general would think that the original message had not made it. So the first general confirms,

Received your message! Ready to go at dawn...provided we know you get this message.

This confirmation also needs confirmation, since otherwise, the first general wouldn't know that the second general had received the necessary confirmation, and he would therefore call off the plan. So the second red general verifies that indeed he received it.

Got it! We're definitely on, once we know you have received this.

And so on, back and forth. The brave messengers make it through each time against the odds. At each stage of the process, however, the generals need confirmation that their message was received, in order that they would know that the other general will undertake the plan, since otherwise, they would have grounds for thinking that they would be attacking alone, a dangerous possibility.

How much confirmation suffices? Can the two generals ever become fully confident in the coordination of their joint plan?

Interlude