wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        general >> wanted >> ~war~
        
(Message started by: m|ndless on Aug 7^th, 2003, 4:38am)

Title: ~war~
Post by m|ndless on Aug 7^th, 2003, 4:38am

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)

Title: Re: ~war~
Post by Neelix on Aug 7^th, 2003, 5:05am

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.

Title: Re: ~war~
Post by James Fingas on Aug 7^th, 2003, 10:15am

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.

Title: Re: ~war~
Post by all on Aug 7^th, 2003, 7:40pm

so... there's no way the allies can be sure of winning?

Title: Re: ~war~
Post by m|ndless on Aug 7^th, 2003, 7:45pm

so, there's absolutely no way the allies can be sure of winning? anyone out there?

Title: Re: ~war~
Post by towr on Aug 8^th, 2003, 1:30am

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"

Title: Re: ~war~
Post by James Fingas on Aug 8^th, 2003, 8:05am

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.

Title: Re: ~war~
Post by m|ndless on Aug 9^th, 2003, 12:02am

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.

Title: Re: ~war~
Post by Ares on Aug 9^th, 2003, 5:47pm

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.

Title: Re: ~war~
Post by maryl on Aug 10^th, 2003, 9:01am

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.

Title: Re: ~war~
Post by m|ndless on Aug 17^th, 2003, 2:30am

well... since the enemy kingdom is in the middle... wouldnt the messengers first have to pass them... how'd this be then done?

Title: Re: ~war~
Post by towr on Aug 17^th, 2003, 6:57am

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

Title: Re: ~war~
Post by maryl on Aug 17^th, 2003, 8:38am

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.

Title: Re: ~war~
Post by m|ndless on Aug 18^th, 2003, 4:04am

and so... what's left to be concluded is, still, this cannot be truly, convincingly, without doubt solved?

Title: Re: ~war~
Post by towr on Aug 18^th, 2003, 7:59am

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"

Title: Re: ~war~
Post by James Fingas on Aug 18^th, 2003, 8:15am

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.

Title: Re: ~war~
Post by towr on Aug 18^th, 2003, 8:21am

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.

Title: Re: ~war~
Post by James Fingas on Aug 18^th, 2003, 9:27am

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.

Title: Re: ~war~
Post by towr on Aug 18^th, 2003, 11:03am

that's why _that_ is not the stopping condition.. You get way past that, so it isn't an issue.

Title: Re: ~war~
Post by James Fingas on Aug 18^th, 2003, 1:50pm

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.

Title: Re: ~war~
Post by towr on Aug 18^th, 2003, 2:30pm

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.

Title: Re: ~war~
Post by maryl on Aug 18^th, 2003, 6:09pm

Ok, so I take it you guys want to solve this from a mathematical point of view, and not strategic.

Title: Re: ~war~
Post by towr on Aug 19^th, 2003, 3:16am

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.

Title: Re: ~war~
Post by James Fingas on Aug 19^th, 2003, 11:38am

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.

Title: Re: ~war~
Post by towr on Aug 19^th, 2003, 1:16pm

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.

Title: Re: ~war~
Post by maryl on Aug 19^th, 2003, 5:18pm

Ha, how about carrier pigeons?

Title: Re: ~war~
Post by towr on Aug 20^th, 2003, 12:57am

yum, roast pigeon..

Also, they only fly back home, so you still have to carry them to your ally, so they can then fly home to you when they are released (unless they make someone dinner first..)
On the other hand I think they're less likely to be caught than an ordinary messenger, and they're much faster.

Title: Re: ~war~
Post by maryl on Aug 21^st, 2003, 6:18pm

Well, war has never been a very logical thing to figure out.

Title: Re: ~war~
Post by Zoel on Jan 24^th, 2004, 11:25am

What if instead of having the presence of the messenger as the reason for a strike, we could use the absence?
From a first glance, it would seem like this means war and suicide as soon as one messenger gets killed, but it might not be.
At the very least, if we grant one day for a messenger to get back and forth, under this scheme, N will bail out P no later then one day late or visa-versa

Title: Re: ~war~
Post by John_Gaughan on Jan 24^th, 2004, 9:44pm

Don't mock pigeons. They have the potential to carry more bandwidth than the internet in certain circumstances:

Nick Andreef's pigeons are faster than the internet, but no match for falcons. (http://www.stuff.co.nz/stuff/waikatotimes/0,2106,2756987a6004,00.html)

Title: Re: ~war~
Post by m|ndless on Jan 27^th, 2004, 3:33am

now nations dont go to war without first knowin each other... so what if the enemy sends the pigeons? wouldnt that mess it up entirely? and good one john ;D

Title: Re: ~war~
Post by Zoel on Jan 28^th, 2004, 6:52pm

Would I be entirly in error to suggest a swollow instead?

THe other thing I thought of was what is on the other two sides of the country in the middle. Really tall mountains and especially furocious seas can all be overcome given some determination.
Or is this a rather small world where n and p are literally on opposite sides of the globe. In that case, they might be best off trying to dig a whole through the middle and dropping people through it

Title: Re: ~war~
Post by Eigenray on Jan 28^th, 2004, 9:24pm

What do you mean, African or European?

Title: Re: ~war~
Post by Zoel on Jan 29^th, 2004, 7:11pm

http://www.style.org/unladenswallow/

That aside, I would think we go with a Europian Swollow for purely asthetic reasons.
After all, we started out talking about Narnia, which is vastly closer in terms of climate to Europe then to Africa. One might worry that an African bird would catch a cold in a climate like that....
But Las Varas sounds like somewhere an African bird might be better off, so it all comes down to which one got baked in a pie recently.

Title: Re: ~war~
Post by raven on Feb 28^th, 2004, 11:48pm

Okay, you’re taking the wrong approach… Say you are the commander of N, the only direct contact you have is with LV, not P. So the only thing you can be certain of is if LV takes an action, not P. You send an ambassador to LV and convince them to ally with you (N) against P. When they are finally convinced you will be in their midst with your army and on the front lines of P-land. P will have to go to war being directly assaulted by LV and when the fighting starts you can double cross LV and attack from behind and amongst the LV army. This ensures that P is fighting LV and they will be grateful for your obvious help in their defense.

Title: Re: ~war~
Post by towr on Feb 29^th, 2004, 7:51am

You're assuming LV won't double-cross you first.

Title: Re: ~war~
Post by raven on Feb 29^th, 2004, 10:45am

True towr, since it was already stated at the beginning that LV was the common enemy of N and P. The trick is to find a way to make (manipulate) LV into being the messenger for N and P, since it's the only common link they have. You know you will be going to war with LV ultimately and so it isn't a problem if they double cross you, so long as it happens after they've already attacked P.