Two generals must attack together, but can communicate only by messengers who may be lost; how can they...

[ Editor: the Oracle's reply to the penpal version: ]

Your question is reminiscent of some "impossibility" theorems in the
study of communication between networked computers.  My initial
reaction is that the answer is "no," based on my experience studying
similar questions.

For example, refer to IEEE Computer magazine, vol 25 number 6 (June
1992), in which the cover story discusses the "consensus" problem.
Your problem is essentially for the two of you to reach a consensus
that the first message was received, i.e., that you can both say "it
was received" in confident knowledge that the other person is saying
the same thing.  But consensus is known to be impossible when your
only means of communication is unreliable (as yours clearly is), even
if the computers (or people) sending the messages are themselves
totally reliable.

The last time such a problem was posed [ Editor: on rec.puzzles ], it
started a lively discussion, though most of the discussion centered
around means for allowing one person to confirm directly that the other
person received the message, that is, several people tried to modify
the physical model to change the underlying assumptions of message
reliability.

-- David A. Karr <karr@cs.cornell.edu>

[ Editor: a reply to Kerbl's two-armies version: ]

There have been 2 reasonable responses to this thread so far (IMHO).  One
showing that if the obvious approach for communicating is used, then it is
impossible.  Another being a probabilistic approach which says basically,
if enough pigeons are sent, the likelihood of successfully communicating
approaches unity.  If the problem were thought of another way, however,
I think there is a third reasonable solution.

Ignoring the agreed upon time of the attack (which both parties know even
if they aren't sure the other army knows they know after the first successful
message is sent), treat both generals as perfect logicians.

General A considers the following cases:

i)   If we attack and B attacks we win outright.
ii)  If we attack and B does not attack, we lose immediately, but B
     loses also (if the meaning of the quoted middle paragraph is understood).
iii) If we do not attack and B does, B loses immediately and we lose
     soon thereafter.
iv)  If we do not attack and B does not attack, we both lose the war.

Since the only possible way to prevent ultimate defeat is to attack, General
A concludes, "We must attack."  Similarly for General B.  Both generals can
rest easily if they are convinced that their opposite number is also logical
and the two armies will win the battle.  This follows one of the basic
tenets [Editor: "tenants" in the original] of competitive games: "Play as though victory is possible."  In fact,
an analog to this can occur when playing "silent" Diplomacy.

-- Matt <mroozee@math.uci.edu>

Ted Lewis wrote:

> In his book, Dennis Shasha takes great care to point out that the carrier
> pigeons can get lost or be killed by birds of prey, so there is no certainty
> that they will arrive at their intended destination. His answer is that no
> number of acknowledgements and counteracknowledgements are sufficient. There
> will never be an attack. He explains it as follows:
>
> Initially, one army knows a fact that the other doesn't know (namely that they
> will attack at 0800 if confirmed by the other army).
>
> Suppose that at some point one of the two armies, say X, knows something that
> the other one, call it Y, must know in order to attack. So, X sends a carrier
> pigeon. When Y receives the message, X still cannot attack, because Y knows
> something that X must know in order to attack (namely, X must know that Y has
> received the message). The argument now repeats itself with the roles of X and Y
> reversed.
>
> Dennis Shasha follows this up with another problem:
>
> "Suppose that the armies have scouts on top of the ridge who light a beacon
> for a few seconds each time a carrier pigeon successfully makes trip from one
> general to the other. Suppose that both generals can see the beacon.
>
> "How many successful carrier pigeon flights are required then?"

I think the answer to this puzzle is one of three things, based on what
assumptions you are using:

1)  It is unsolvable, as described above, assuming that the point is to
arrive to a place where each of the 2 generals is 100% sure that the other
is going to attack, (and in an earlier post, the "there can be no least
number of messages argument")

2)  The solution is to send messages saying when I stop sending these, you
will know that I have received your message, thereby minimizing the risk to
each army, as described in an earlier post by Thomas Brooks, (The
assumption here is that it isn't necessary for them each to be 100% sure,
only 99%) or

3)  (and I forget who posted this...) That both Generals should stop
sending messages, sit down, and reason it out: Since it was stated in the
original puzzle that if they don't attack soon, they will lose the war, and
they had each already agreed upon a time, it is to their mutual advantage
to attack, even with the uncertainty that the other will attack, since all
is lost if they do not.  The assumption being that each General realizes
that the degree to which each is sure that the other is going to attack is
irrelevant, considering there is no chance of winning the war if either of
them stays behind.

My attempt to sum things up...

-- Keith Lloyd <klloyd@page.kodak.com>

[ Editor: no answer to Shasha's beacon question was found in the
collected postings. ]