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.
10 comments
Comments feed for this article
June 30, 2010 at 12:00 am
Niko
Why does a pigeon always take one or two days, but a scout takes a random amount of time? Not to mention that vulnerability could have changed by the time the scout and pigeon made their journeys. The story is silly, even if the math makes sense.
June 30, 2010 at 3:02 am
michael webster
Is this different in any way from the Surprise Examination Paradox?
June 30, 2010 at 5:31 am
Soumendu
Why cannot “you” simply stamp the date of sending the pigeon on itself, and attack after two days?
June 30, 2010 at 5:45 am
Common knowledge | The Incidental Economist
[…] Yesterday, over at the Cheap Talk blog, Jeff Ely put up a post with an interesting problem that hinges on the concept (Cheap Talk is a good blog for lovers of game […]
June 30, 2010 at 10:58 am
Glenn Cassidy
Agree in advance that the attack will occur on date k if vulnerability is confirmed. Also agree that the pigeon will not be sent any later than date k-3. Then the sender knows that the pigeon will have been received by date k-1, and the receiver knows that the sender knows this, etc. Then, on date k, each knows that the other is attacking.
This could be further modified to shift the attack date to k+2 if the k-3 send date constraint is not satisfied. E.g., if the sender learns on date k-2 of the enemy’s vulnerability, then the sender will wait until date k-1 to send to ensure the message is received on date k or k+1. If the receiver knows that the sender will not send on date k-2, then receipt on date k would imply the message was sent on date k-1 and, by the agreement, attack would occur on date k+2. This rule can be infinitely shifted forward to date k+2n, with cutoff date of k+2n-3 for sending the message.
June 30, 2010 at 1:20 pm
jeff
nice, yes. i was implicitly assuming that the pigeon was sent immediately and that was not part of the advance planning. by the way, steiner and stewart were studying a model where the messages are sent automatically and they were making a different point with it. the story here is mine (and its admittedly not a great one.)
June 30, 2010 at 1:57 pm
Matt
My initial thought was a slightly simplified formulation of Glenn’s strategy. Let “red days” and “blue days” alternate. You only dispatch a pigeon on red days — if you determine that the enemy is vulnerable on a blue day, you wait one day before sending the pigeon. Then the person receiving the pigeon knows exactly when it was sent (the last red day) and also knows when to attack (either the current day, or the next red day if the current day isn’t red). When you send a pigeon, you can safely attack 2 days later.
In general, if the delay d (in days) satisfies a <= d <= b, then the same strategy works if red days occur every a-b+1 days, and the rest are blue.
Of course, as Soumendu mentioned, you could also just circumvent the logic puzzle and date-stamp the messenger…
July 3, 2010 at 8:00 am
Convention, common knowledge et « falsh-mob « « Rationalité Limitée
[…] pour quelque chose d’être common knowledge) mais en plus débouche sur des paradoxes. Cet amusant billet de Jeff Ely expose l’un d’entre eux. Je connaissais une variante un peu plus simple dont l’idée […]
July 28, 2011 at 6:30 am
Hondo69
Us smoke signals instead of pigeons.
February 29, 2012 at 8:16 am
jamie rishaw (@libJamiE)
Holy crap, just send a text message(SMS).
Reading, parsing and putting myself in the “first person” position of this almost made my head explode.
And trust me, my head is elastic enough for my own ego bursts. This is just crazy.
:-p