Author |
Topic: ~war~ (Read 2272 times) |
|
m|ndless
Newbie
Posts: 8
|
i need help with something...
here goes... it is war time, the kingdom of Narnia and Panzion are allies against a common, powerful enemy--- the kingdom of Las Varas... the allies sandwich their enemy, like this :
N-LV-P
alone, narnia and panzion cannot defeat las varas but when the allies fight together, they can easily crush las varas...
so one day, the commander of narnia decides he wants to attack las varas at noon, the next day.
so the question is, how can the commander of narnia inform the commander of panzion about his decision, so that they can close in on the enemy together?
(assume this war takes place a long long time ago... where technology is lacking ; no phones, internet and
you-know-whatever-fits-in-this-category)
|
|
 IP Logged |
|
|
|
Neelix
Newbie
Posts: 3
|
 |
Re: ~war~
« Reply #1 on: Aug 7th, 2003, 5:05am » |
 Quote  Modify
|
This example is used a lot to show that you can never go from "everybody knows" to "common knowledge" in logic.
The thing is that either general wanting to attack has to send his messenger through the enemy camp and can never be sure it arrives. Even if he asks for a confirmation of his message, then he cannot be sure that the other general knows that the confirmation arrives.
There is absolutely no way that both generals know 100% sure that they are both attacking on the time they set.
|
|
IP Logged |
|
|
|
James Fingas
Uberpuzzler
Gender: 
Posts: 949
|
|
Re: ~war~
« Reply #2 on: Aug 7th, 2003, 10:15am » |
Quote Modify
|
In order for this to be a true stalemate, though, it is necessary that both N and P will not attack unless they are sure the other one will attack, and furthermore, that they know that this is common knowledge. If they've never met face to face to discuss this, then they wouldn't know that. In fact, even if they have, they can never be sure that the leadership of the other nation hasn't changed.
If one of them will commit to an attack without being 100% certain that the other will attack, then the attack can progress (by just sending a messenger to the other nation).
Furthermore, if one of them thinks the other will commit to an attack without being 100% certain that he will attack, then the attack can progress (by sending a messenger then receiving a confirmation).
If one of them thinks that the other thinks that he will commit to an attack without being 100% certain that the other will attack, then the attack can progress (by sending a messenger then receiving a confirmation, then sending back another confirmation). In this case, you could use deception to form the basis for the attack:
Send the message "We are going to attack at noon, with or without you." (but tell the messenger to bring back confirmation that they are going to attack too). Assuming you believe that they believe that, then the attack can progress.
This can be extended to any depth of logic. The stalemate only arises when both N and P know that the other knows that they know that the other knows that ... that neither of them will conduct an attack without the other.
This ignores possible man-in-the middle attacks, which I'm assuming can be prevented using the royal seals of the N and P kingdoms.
|
|
IP Logged |
Doc, I'm addicted to advice! What should I do?
|
|
|
all
Guest
|
so... there's no way the allies can be sure of winning?
|
|
IP Logged |
|
|
|
m|ndless
Newbie
Posts: 8
|
|
Re: ~war~
« Reply #4 on: Aug 7th, 2003, 7:45pm » |
Quote Modify
|
so, there's absolutely no way the allies can be sure of winning? anyone out there?
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: ~war~
« Reply #5 on: Aug 8th, 2003, 1:30am » |
Quote Modify
|
It depends how far apart they are.
If they are close enough together to see fire, or smoke signals they can use that to create common knowledge.
Or if one side can see the other clearly enough they could just say, "if you attack we'll also attack"
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
James Fingas
Uberpuzzler
Gender:
Posts: 949
|
|
Re: ~war~
« Reply #6 on: Aug 8th, 2003, 8:05am » |
Quote Modify
|
Common knowledge is a very special sort of knowledge. I don't think smoke signals would be good enough, since you can't be sure that your ally is watching and understanding. And shouting also is probably not good enough either, unless you are completely sure that the other person can hear the shouting, and that they know that you know that they can hear it, etc.
In fact, face-to-face communication can't usually create common knowledge either. For instance: are you sure the other person understood exactly what you meant to say? Are you sure they're going to remember it right? Are you sure they're not an imposter? Are you sure that they're sure you didn't make a mistake in what you said? Do they know that you're sure about all these things?
Basically, to make something common knowledge between N and P, it must be common knowledge that the communication is received, understood, and witnessed by both parties. So to gain common knowledge in the strictest sense, you need to already have some (albeit different) common knowledge.
Therefore, common knowledge is impossible. The two armies will never attack if they both demand common knowledge.
But supposing that N and P are smart, they must realize this, and know that no real-life decision is ever based on common knowledge. Therefore, they must be willing to make any and all decisions--including the decision to attack LV--without common knowledge. They require only a minimum degree of certainty about what will happen, which is certainly attainable in this case.
Towr's suggestions, while I don't think they create common knowledge, can create a high degree of certainty, which I think should be sufficient for smart kingdoms N and P. Furthermore, if even one of N and P thinks that the other might be smart enough to not require common knowledge, then the attack can proceed.
|
|
IP Logged |
Doc, I'm addicted to advice! What should I do?
|
|
|
m|ndless
Newbie
Posts: 8
|
|
Re: ~war~
« Reply #7 on: Aug 9th, 2003, 12:02am » |
Quote Modify
|
well... suppose, they aren't as smart and one decides he cannot wait for the other to get smart, how then? he would attack and all would be lost. i've been stuck on this for a long time and i guess i just wasn't convinced with the explanation... is there anythin more enlightening? it'd be appreciated.
|
| « Last Edit: Aug 9th, 2003, 12:02am by m|ndless » |
IP Logged |
|
|
|
Ares
Guest
|
I have two methods of getting around the problem.
Method One: You send a messenger across to suggest a war. He stays there while one of their men brings a message back tentatively accepting. You keep sending messengers back and forth. Eventually your entire army will be over there and you'll have their entire army here. At this point you have no qualms about attacking without knowing for sure that they will attack, because it will be their soldiers you're sending into battle.
Method Two: You send a couple soldiers back and forth to confirm that they're willing to go to war. Then you don't give them a choice. Tell the enemy that you just got a message that the other nation has decided to attack at noon. (You were, of course, horrified at their bellicosity).
And each of your messengers that's now over there have orders to start shooting their guns at noon to make sure the war starts as planned. Of course, you always still have the option of not attacking; you'll only lose a couple men when the war starts over there.
|
|
IP Logged |
|
|
|
maryl
Guest
|
I would suggest that the commander of Narnia send a messenger to instruct the commander of Panzion to surround LV at either the north or south while his forces surround LV at the opposite direction leaving them meeting in the middle.
|
|
IP Logged |
|
|
|
m|ndless
Newbie
Posts: 8
|
|
Re: ~war~
« Reply #10 on: Aug 17th, 2003, 2:30am » |
Quote Modify
|
well... since the enemy kingdom is in the middle... wouldnt the messengers first have to pass them... how'd this be then done?
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: ~war~
« Reply #11 on: Aug 17th, 2003, 6:57am » |
Quote Modify
|
That is indeed the problem, some messengers will almost certainly get through, but some or maybe most will be caught. So you can't be sure they actually got through untill you get confirmation. And your ally can't be sure you got their confirmation and thus can't be sure that you know they got your message
|
| « Last Edit: Aug 17th, 2003, 7:01am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
maryl
Guest
|
Well, they used to disguise their messengers and send them into the enemy camp as spies, and especially since LV is a large nation, it would be difficult to recognize a spy. You could send two men to cover each other's back, have one go on to the ally's camp-deliver the message and return confirmation to the other who would notify the source. If something happens with either of these two men, send more until the message gets through.
I don't think there is 100% certainty with anything but actual numbers.
Another possibility is a mole inside the enemy camp.
|
|
IP Logged |
|
|
|
m|ndless
Newbie
Posts: 8
|
|
Re: ~war~
« Reply #13 on: Aug 18th, 2003, 4:04am » |
Quote Modify
|
and so... what's left to be concluded is, still, this cannot be truly, convincingly, without doubt solved?
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: ~war~
« Reply #14 on: Aug 18th, 2003, 7:59am » |
Quote Modify
|
well.. that depends..
Doubt is a very human emotion. Even when there is reason to doubt one might not.
I'd say that ones you've send enough messengers and got enough in return that you can be pretty sure your first messenger arrived safely.
If you've send 6 messengers and got 6 back from your ally, then you can be sure that they received your 6 messengers, and you know that they know you received at least 5 of theirs.
From their point of view they got 6 messengers and know that 5 of theirs safely arrived. So they know that you know that they got at least 5 of your messengers.
So maybe you could just keep sending messengers to and for and say, "when we each received at least X messengers we will attack"
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
James Fingas
Uberpuzzler
Gender:
Posts: 949
|
|
Re: ~war~
« Reply #15 on: Aug 18th, 2003, 8:15am » |
Quote Modify
|
That removes none of the doubt from the problem. Think of the problem as a state machine, with just two state bits, N and P. When N is false, Narnia has not decided to attack yet. When P is false, Panzion has not decided to attack yet.
Now we create a condition that will set N true:
1) When Narnia receives the sixth messenger, set N true.
2) When Panzion receives the sixth messenger, set P true.
The problem statement, however, says that whatever other conditions we make, N cannot be true unless we know that P is (or will be) true, and P cannot be true unless N is (or will be) true.
So without some sort of simultanous action that can set N and P true together, the best we can get is some point where all other conditions for turning N true are met, except that P is not yet true, and all conditions for turning P true are met, except that N is not true. It is even possible that both Narnia and Panzion know this. However, the paradox arises because there is no way of ensuring that Panzion will find out that N has become true. If we set N true, we run the risk of P never being set true.
|
|
IP Logged |
Doc, I'm addicted to advice! What should I do?
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: ~war~
« Reply #16 on: Aug 18th, 2003, 8:21am » |
Quote Modify
|
I don't think I agree..
If each side send ten messengers and only in response to an arriving messenger (except for whoever starts). Then at the end both sides know they got at least, say two messengers, and that the other also knows that.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
James Fingas
Uberpuzzler
Gender:
Posts: 949
|
|
Re: ~war~
« Reply #17 on: Aug 18th, 2003, 9:27am » |
Quote Modify
|
Yeah, but if the condition is to decide to wage war as soon as you get two messengers, the first person to get two messengers can't yet decide to wage war. He has to wait until he knows the other side got two messengers. But the other side knows he's waiting, etc.
|
|
IP Logged |
Doc, I'm addicted to advice! What should I do?
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: ~war~
« Reply #18 on: Aug 18th, 2003, 11:03am » |
Quote Modify
|
that's why _that_ is not the stopping condition.. You get way past that, so it isn't an issue.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
James Fingas
Uberpuzzler
Gender:
Posts: 949
|
|
Re: ~war~
« Reply #19 on: Aug 18th, 2003, 1:50pm » |
Quote Modify
|
But that applies to any stopping condition you pick. Even if the condition is getting 100 messengers, you still are trying to get one side to decide to go to war when they know the other side hasn't decided yet.
|
|
IP Logged |
Doc, I'm addicted to advice! What should I do?
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: ~war~
« Reply #20 on: Aug 18th, 2003, 2:30pm » |
Quote Modify
|
There wouldn't be a stoppingcriterion as to when to stop sending messengers. Sending messengers or not sending them is hardly interesting. You want to know if both sides agree to attack.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
maryl
Guest
|
Ok, so I take it you guys want to solve this from a mathematical point of view, and not strategic.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: ~war~
« Reply #22 on: Aug 19th, 2003, 3:16am » |
Quote Modify
|
Strategies for getting a messenger across are certainly important, because it speeds the proces up. But if you want more certainty you'll need a message transfer protocol.
You could send a file with FTP, or hypertext with HTTP, but both of those are only made to satisfy one side. The server can't be sure the client got the whole message.
On the other hand, if you know the other side will send messengers(packets) untill he has the whole message(file/html-document), then you can be pretty darn sure he got it once you stop getting messengers(packets) requesting for more.
|
| « Last Edit: Aug 19th, 2003, 3:17am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
James Fingas
Uberpuzzler
Gender:
Posts: 949
|
|
Re: ~war~
« Reply #23 on: Aug 19th, 2003, 11:38am » |
Quote Modify
|
Or the enemy could be capturing all the messengers. This sort of reminds me of the prisoners and lightbulb question--you're trying to ensure that something has happened with 100% certainty. But in the prisoner situation, only one entity has to be completely certain. Here, both allies must be completely certain. Hmm ... I will think about whether we can rephrase the prisoner/lightbulb question with this paradox in it.
How about this:
"Two prisoners are going to jail. Each day in jail, the guard will flip a coin to deterine which prisoner he will visit. Both prisoners will be released from jail on date XX if both the prisoners talk to the guard and say 'the other prisoner will talk to you before date XX.', and their statements are both correct. However, their scheme must not allowed to have any chance of failure, no matter how remote. How can the prisoners get released?"
I am only trying to point out that the paradox as stated is completely valid. There is no way for both to be 100% certain that the other will attack, given that both know the other must be 100% certain that they will attack before they will attack.
|
| « Last Edit: Aug 19th, 2003, 11:47am by James Fingas » |
IP Logged |
Doc, I'm addicted to advice! What should I do?
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: ~war~
« Reply #24 on: Aug 19th, 2003, 1:16pm » |
Quote Modify
|
I don't think the prisoner situation is analogous to this problem..
There isn't necessarily any need for infinite confirmation. It in part depends on the preconceptions the different parties have, and the logic system they reason with.
In some systems common knowledge is intrinsicly impossible, even when two people stand next to each other, just because they may not understand each other. That's of course a cop-out way to 'solve' this problem, the least you can assume about the system is that they can understand each other. I think there may be other valid preconditions that are reasonable and help to solve this problem.
Though I'll have to work on it a little to find a proper (non-cop-out) model.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print
Remove