It’s a variation on the old coordinated attack problem or Rubinstein’s electronic mail game.  But this one is much simpler and even more surprising.  It is due to my colleague Jakub Steiner and his co-author Colin Stewart.

Two generals, you and me, have to coordinate an attack on the enemy.  An attack will succeed only if we both attack at the same time and if the enemy is vulnerable.

From my position I can directly observe whether the enemy is vulnerable.  You on the other hand must send a scout and he will return at some random time. We agree that once you learn that the enemy is vulnerable, you will send a pigeon to me confirming that an attack should commence.  It will take your pigeon either one day or two to complete the trip.

Suppose that indeed the enemy is vulnerable, I observe that is the case, and on day n your pigeon arrives informing me that you know it too.  I am supposed to attack.  But will I?

Since you sent a pigeon I know that you know that the enemy is vulnerable.  But what day did you send your pigeon?  It could be either n-1 or n-2.  Suppose it was n-1, i.e. the pigeon arrived in one day.  Then you don’t know for sure that the pigeon has arrived yet.  So you don’t know that I know that you know that the enemy is vulnerable.  And that means you can’t be certain that I will attack so you will not attack.  And now since I cannot rule out that you sent the pigeon on day n-1, and if that was indeed the date you sent it you will not attack, then I will not attack either.

Thus, an attack will not occur the day I receive the pigeon.  In a certain sense this is obvious because only I know what day I receive the pigeon.  But the surprising thing is that there is no system we can use to decide the date of an attack and have it be successful.

Suppose that we have decided on some system and according to that system I am supposed to attack on date k.  What must be true for me to actually be willing to follow through?  First, I must expect you to be attacking too.  And since you will only attack if you know that the enemy is vulnerable, I will only attack if I have received your pigeon confirming that you know.

But that is not enough.  You will only attack if you know that I will attack and we just argued that this requires that I know that you know that the enemy is vulnerable.  So you will attack only if you know that I have received your pigeon.  You can only be sure of this 2 days after you sent it.  And since I need to be sure you will attack, I will only attack if I received the pigeon yesterday or earlier so that I am sure that you sent it at least 2 days ago and are therefore sure that I have already received it.

But that is still not enough.  Since we have just argued that I will only attack if I received your pigeon at least 1 day ago, you can only be certain that I will attack if you sent your pigeon at least 3 days ago.  And that is therefore necessary for you to be prepared to attack.  But now since I will attack only if I am certain that you will attack, I need to be certain that you sent your pigeon at least 3 days ago and that requires that I received your pigeon at least 2 days ago (and not only yesterday.)

This goes on.  In order for me to attack I must know that you know that I know, etc. etc. that the enemy is vulnerable.  And each additional iteration of this requires that the pigeon be sent one day earlier than the previous iteration. Eventually we run out of earlier days because today is day k.  This means that I will not attack because I cannot be sure that you are sure that (iterate k times) that the enemy is vulnerable.