Author |
Topic: HARD: GREEDY PIRATES (Read 41138 times) |
|
Vincenzo
Guest
|
klbarrus has the right answer! This is an old puzzle I've seen before.
|
|
 IP Logged |
|
|
|
Chronos
Full Member
Gender: 
Posts: 288
|
 |
Re: HARD: GREEDY PIRATES
« Reply #26 on: Aug 6th, 2002, 12:11pm » |
 Quote  Modify
|
I think that there's a flaw in the SciAm solution. These pirates are presumably all members of the same crew, and will be pirating together for a while yet. They will probably find more treasures, in time, but they don't know how much, or when, so they don't know who's at risk at any given point.
Since we've established that the pirates are infinitely intelligent, they follow rules (voting on whether to accept proposals), and they value self-preservation above all other things, they will change the rules in such a way that they're not always at risk every time they find a treasure. No, this is not consistent with the usual behavior of pirates, but that's because real pirates are not infinitely intelligent.
|
|
IP Logged |
|
|
|
kul
Guest
|
There is a flaw in sciam solution listed below:
[/i] So in summary, an answer (not the only one as evidenced by the discussion here) that fits with some additional assumptions about pirate behavior is:
P5 = 998 coins
P4 = P2 = 0 coins
P3 = P1 = 1 coin
And you get to that backwards:
2 pirates: P2 = 1000, P1 = 0, accepted with P2's vote
3 pirates: P1 = 1, P2 = 0, P3 = 999; P1 will vote as he gets more than he would if P2 decided
4 pirates: P1 = P3 = 0, P2 = 1, P4 = 999; P2 will agree as he gets more than he would if P3 decided
5 pirates: P1 = P3 = 1, P2 = P4 = 0, P5 = 998; P1 and P3 will agree as they get more than if P4 decided
[i]
The proposal 4 is not valid. P1 and P3 do not agree so it does not have majority. Atleast 3/4 must agree for majority.
|
|
IP Logged |
|
|
|
AlexH
Full Member
Posts: 156
|
|
Re: HARD: GREEDY PIRATES
« Reply #28 on: Aug 10th, 2002, 7:29pm » |
Quote Modify
|
The sciam problem interprets the word "majority" non-strictly (i.e. ">= 50%" instead of ">50%"). This is a non-standard interpretation of the word which presumably derives from their being mathematicians who will tend to say "strictly greater than" when they disallow equality and use "greater than" so as to include equality.
|
|
IP Logged |
|
|
|
Seb
Guest
|
|
Re: HARD: GREEDY PIRATES
« Reply #29 on: Aug 13th, 2002, 7:43am » |
Quote Modify
 Remove
|
1 is alone: 1 gets 1000
1 and 2: tie = 2 dies because his proposal was not accepted by a majority
1, 2 and 3: 2 votes in favor of anything to avoid death, 3 gets 1000
1,2,3 and 4: offers 1 coin each to 1 and 2, who vote in favor (if not, they would get nothing), 4 gets 998
1,2,3,4 and 5: offers 2 coins to 1 or 2, and 1 coin to 3, 5 gets 998
5's proposal:
5 votes for his proposal, of course (1,0)
4 votes against any proposal that gives him <998 (1,1)
3 would get nothing if 5's proposal was not accepted, so accepts the 1 coin offer (2,1)
2 would get 1 coin if 5's proposal was not accepted, so must be given 1 extra coin for his vote (3,1)
1 since his vote is not needed, he is given nothing (3,2)
5's prize: 1000 - 1 coin to 3 - 2 coins to 2(or 1) = 997
5: 997
4: 0
3: 1
2: 2
1: 0
|
|
IP Logged |
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: HARD: GREEDY PIRATES
« Reply #30 on: Oct 25th, 2002, 6:27pm » |
Quote Modify
|
While I came up with the same answer as most everyone else, I also considered a different interpretation of the problem, which I have found MUCH harder! Suppose that "accepting" a proposal does not mean it is acted on immediately?
Let me state the problem in full: The 5 pirates are splitting 1000 coins by the following procedure:
Each of the pirates, starting with 5 and ending with 1, makes a proposal. If the proposal is rejected, the pirate is thrown overboard. If it is accepted, it becomes the "current" proposal, replacing the previously current proposal. This continues until all 5 have made a proposal. At that time whichever proposal is current (that of the lowest numbered pirate still living) is the one carried out.
As with the original problem, a true majority is necessary for a proposal to be accepted.
To make things definite, assume the pirates follow the motivations as Eric Yeh explains them:
First, the pirates want to survive. Second, they want as much gold as possible. Third, given an equal amount of gold each way, they would prefer to see their mates die.
I believe I know what happens with 3 pirates, but putting in a 4th one, much less a 5th, changes everything! Anyone got an answer to this one?
Another possible variation: What if the proposals are not restricted to who gets how many coins? (They are still restricted to what is implied in the puzzle - no wild suggestions!) With this in place in the original puzzle, I believe 5 can get away with 999 coins!
|
| « Last Edit: Oct 25th, 2002, 7:14pm by Icarus » |
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
James Fingas
Uberpuzzler
Gender:
Posts: 949
|
|
Re: HARD: GREEDY PIRATES
« Reply #31 on: Oct 28th, 2002, 12:37pm » |
Quote Modify
|
That is an amazingly difficult puzzle. Good work!
With three people, I think I see what the answer is: they all survive, and #1 and #2 get 500 coins each. Very complicated!
I think we should add another attribute to the pirates: they like to screw their mates over. For instance, if #2 leaves #1 the option of giving either him or #3 some coins, then #1 will purposely give #3 the coins, just to screw over #2. This may reduce the number of ambiguous cases, and reduce our reliance on probability.
Just a thought!
|
|
IP Logged |
Doc, I'm addicted to advice! What should I do?
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: HARD: GREEDY PIRATES
« Reply #32 on: Oct 28th, 2002, 3:43pm » |
Quote Modify
|
Sounds like a good idea to me, though the other way could be interesting too.
About my other variation, which strikes me as being unclear. The particular idea I had was that the pirates could propose that some of the others be killed. For instance, pirate 5 could propose "lets throw 3 and 4 overboard, and I take all the gold!". If this sort of proposal is allowed, then 5 can get away with 999 coins (under the original puzzle) rather than 997.
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
James Fingas
Uberpuzzler
Gender:
Posts: 949
|
|
Re: HARD: GREEDY PIRATES
« Reply #33 on: Oct 29th, 2002, 7:59am » |
Quote Modify
|
Icarus,
I think I should take back my suggestion. What is important is not how the pirates act, but what they know for sure about the other pirates. An element of randomness can actually help the pirates in certain circumstances.
We must define what happens when a pirate who has gold coins assigned to him gets thrown overboard. It would make things simple to assume that his coins go with him, but of course, that's not how pirates work  , so we must assume that after a proposal is finally accepted, if any people who were thrown overboard were assigned treasure, then the treasure is divvied up according to the same rules, but obviously with fewer people. Now I should add that pirates shouldn't be allowed to assign money to somebody after they've been thrown overboard, but of course, they can throw somebody overboard even after they've been assigned money.
After a lot of brain-bashing, thinking about the four-pirates case to your extension, and assuming my new rules on how money is reshuffled when a money-holder is thrown overboard, I am dissappointed to say that here is what happens (AFAIK):
4 proposes anything
2 and 3 vote no, 4 gets tossed
money is distributed 500,500,0, same as in the 3-pirate case.
There are a lot of possibilities, but basically, either 3 is going to get nothing, or 4 is going to get nothing. Both 3 and 4 know this, and since 3 can control which of them gets nothing, then 4 would kill him given half a chance, becase 3 is going to give 4 nothing. 4 would rather 3 die, given that 4 will get nothing either way. Knowing that, 3 must kill 4 or be killed himself.
There is another possible tactic for 3, in which he placates pirate 1, himself, and pirate 4 by proposing the same amount of money for himself and 4. However, for an intricate set of reasons, this just doesn't work.
I even considered cases where 2 tries to kill off 1 and grab money for himself, but it turns out that 1 can never be thrown overboard, and 2 can never get more than 500 coins if 1 is there, so 2 will try to vote off both 3 and 4, thus getting his maximum of 500 coins.
1 is open to the possibility of 3 or 4 surviving, but that doesn't make a difference here.
|
|
IP Logged |
Doc, I'm addicted to advice! What should I do?
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: HARD: GREEDY PIRATES
« Reply #34 on: Oct 29th, 2002, 4:23pm » |
Quote Modify
|
James, what you were saying seems to pretty much follow my thoughts (though I haven't run into a case where a dead pirate was getting coins. Every case like that I saw was eliminated before things got that far), but I am confused by this line
Quote:| ...so 2 will try to vote off both 3 and 4, thus getting his maximum of 500 coins. |
|
Pirate 2 does not want both 3 and 4 dead. If they are gone, he will never survive his proposal, as 1 has no reason to agree with it then!
To make sure we are in agreement, here is my analysis of the 3 pirate case:
Pirates 1 and 2 both know that they need three pirates alive at their proposals (unless 1 can manage to kill both the other two before his turn). Otherwise, the other surviving pirate will vote them down, and they will die. So 2 must vote for 3's proposal, and because it passes, 1 will have to vote for 2's proposal.
Knowing this, and realizing that all he is going to get out of the deal is a good chuckle, pirate 3 proposes that the money be used to buy a sex change for pirate 2, who agrees through gritted teeth. Pirate 1 is unable to stop laughing long enough to vote, but the proposal passes anyway.
Pirate 2 knows that whatever he proposes will pass, since 1 must vote for it. He also knows that 1 will have to buy either his or pirate 3's vote by improving on what his own proposal gives. Obviously it is in 2's advantage for 1 to try to buy his vote, not 3's. So 2 must make buying him cheaper than buying 3, but otherwise as expensive as possible. He proposes that he take 499 gold, and 3 get the remaining 501.
Pirate 1 agrees. (Pirate 3 does not, but is outvoted.)
Pirate 1's best choice is therefore to propose 500 coins for 2 and himself. 2 agrees.
The result: 500 coins for 1, 500 coins for 2, a life on the run from a vengeful 2 for pirate 3.
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
James Fingas
Uberpuzzler
Gender:
Posts: 949
|
|
Re: HARD: GREEDY PIRATES
« Reply #35 on: Oct 31st, 2002, 9:00am » |
Quote Modify
|
Icarus,
You're right, #2 wants to kill #3 or #4, not #3 and #4.
As for the dead pirate's money, the problem is found in this scenario:
Step 1:
#3 decides that #4 should live, and #1 does too (you'll see why #3 makes this decision shortly).
Step 2:
#3 proposes 0,4,498,498. #1 Likes this, as it will give him 501 coins (assuming #2 dies). #2 doesn't like it, because he'll die, and he won't get 500 coins. #3 and #4 like it, because it gives them a chance to get money. They both realize that this is better than getting nothing. Here's the problem though: If the dead #2's money gets split up by another round, then #4 must make sure that #1 is there in that round, or #4 will die too! Therefore, #1 can propose 1000,0,0 if #2 dies, and #4 must vote for it, or die in the next round!
See what I mean? If #2's money were thrown overboard with him, then there wouldn't be a second round, and #1 would have to pay off one of #3 and #4, making this their optimal strategy!
|
|
IP Logged |
Doc, I'm addicted to advice! What should I do?
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: HARD: GREEDY PIRATES
« Reply #36 on: Oct 31st, 2002, 9:54pm » |
Quote Modify
|
I understand your point that if there were to be a second round, 1 has the chance to grab it all in the first. My concept is that there is no provision for later rounds, because the actuality of a second round will never occur. With or without the chance to blackmail 4, 1 is not going to propose giving money to the dead 2, and 1 can always come up with a winning proposal (I think).
It appears we have another variation: One variation for no second round, and another with a never-used provision for a second round, which none-the-less has a profound effect on the first round.
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
James Fingas
Uberpuzzler
Gender:
Posts: 949
|
|
Re: HARD: GREEDY PIRATES
« Reply #37 on: Nov 1st, 2002, 8:10am » |
Quote Modify
|
Icarus,
I came to the same conclusion about 1. He will never be killed (unless there's just one other person).
Making the provision for a second round does seriously change the first round, but I don't see how you could get around it. I mean, the money has got to go somewhere, and the pirates sure aren't going to throw it overboard ... how unpirately! And if the money's not going overboard, you can bet the pirates are thinking about where that money would go ... this understandably affects their decisions.
Yes, pirate 1 won't get thrown overboard. But the measures that pirate 1 is forced to take to ensure he's not thrown overboard are commensurate with what happens to the money. If it's divided evenly, pirate 1 has to pay everybody off evenly. If it's given to a specified person, pirate 1 has to pay that person off. If it's given to a random person, pirate 1 has to pay everybody off according to their expectations of getting money if pirate 1 dies. If it goes to nobody, then pirate 1 doesn't have to pay anybody off.
In short, any method we use to distribute the money will affect the pirates' decisions, despite the fact that pirate 1 will ensure it's never used.
|
|
IP Logged |
Doc, I'm addicted to advice! What should I do?
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: HARD: GREEDY PIRATES
« Reply #38 on: Nov 1st, 2002, 3:53pm » |
Quote Modify
|
Okay, I see your point. (How are you finding time to follow all these threads at once?  I haven't had time to even examine your responses on the infinite coin flips, and the only reason I can keep up on Trianglia II is because it's my puzzle and I followed similar reasoning paths two or three years ago! I won't tell whether or not they worked yet!) Pirates 3 and 4 can only evaluate whether 1's proposal is better or worse for them if they know what happens should 1 die. I was overlooking this, and having them compare to what 2 had offered them. I gotta take more time - I keep making these goofs!
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
James Fingas
Uberpuzzler
Gender:
Posts: 949
|
|
Re: HARD: GREEDY PIRATES
« Reply #39 on: Nov 4th, 2002, 1:50pm » |
Quote Modify
|
It was quite a while 'til I came to that realization as well. The thing that really tipped me off was that I wondered if 2,3, and 4 could conspire to knock off #1, and as I was going through the logic, I realized that it applied strongly to my previous solution (which was wrong as a result).
As for keeping up with all the threads--here's my 5-step plan for success in the W.Wu forums:
1) Ignore other people's posts if they're longer than 4 lines. They're probably wrong anyways.
2) Never make sure that your solution is correct--that second 50% of certainty takes at least twice long as the first 50%, and you know what would happen if you posted the right solution? You'd shut other people out of finding the right solution for themselves!
3) Since being an Uberpuzzler is all about quantity of posts, make that your primary objective. Leave important considerations out of your posts, so that you can "fill in the details" later. The more sketchy (or just plain wrong) your posts are, the more posts you score!
4) If a problem is very confusing, then chances are your solution will be very confusing too. The more confusing your solution is, the less likely people are to work through it, and the less likely people are to try to develop their own. Your solution becomes gospel because everybody is afraid. Conclusion: post BS, and make it complicated. Nobody can tell the difference anyways.
5) Vague and handwavy solutions are actually more convincing that rigorously defined solutions that consider all the border cases. They're also faster to make up. Go for handwavy!
|
|
IP Logged |
Doc, I'm addicted to advice! What should I do?
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: HARD: GREEDY PIRATES
« Reply #40 on: Nov 4th, 2002, 5:45pm » |
Quote Modify
|
Sorry, but I didn't read all your post. After I read rule 1, I had to stop! 
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
UofLis#1
Newbie
I need a Hot girlfriend and a good riddle
Gender:
Posts: 5
|
|
Re: HARD: GREEDY PIRATES
« Reply #41 on: Mar 10th, 2003, 3:11pm » |
Quote Modify
|
This si a hard riddle  . But i have an idea of how to solve it. its probely not right but here goes.
1,2,3 and three pirates being the majority and alos the higher ranking officers- team together. So any proposal pirates 4 and 5 will be rejected because they are blood thirsty and greedy. So what i am saying is that 5 and 4 pirates cant say anything that will save their lives and also get money in the process.
after 4 and 5 die 1 and 2 turn their backs on three (in the hopes that they will split the money fifty-fifty) So any proposal 3 makes he will die.
Either 1 and 2 split the gold or 1 being greedy and BLOOD thirsy decides to kill 2 or they have a duel. and fight it out. in the end i believe 1 will get all the gold or half.
you dont have to tell me right away this answer sucks i know that. i am just contributating 
-Ford
|
|
IP Logged |
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: HARD: GREEDY PIRATES
« Reply #42 on: Mar 10th, 2003, 6:48pm » |
Quote Modify
|
You need to look at it starting with only two pirates. What will happen? (Assume that in any dual the lower numbered pirate always wins - the puzzle says that if the proposal is turned down, the proposer goes overboard. No exceptions.)
Pirate 1 gets all the gold, and gets to kill pirate 2, if he just says no. Pirate 2 has nothing he can offer pirate 1 that beats this. So Pirate 2 is a dead man if there are only two pirates.
With three pirates - Pirate 2 knows that if Pirate 3 dies, it is the two pirate case then, and he is a dead man too. So it does not matter what 3 proposes as long as the proposal doesn't include killing pirate 2, pirate 2 will vote in favor - it's his only hope to live. Pirate 3 knows this, so he can propose whatever he wants other than killing 2.
If you now look at pirate 4, and realize that to get their votes he has to offer at least two of pirates 1,2,3 a better deal than they would get by killing him, you can figure out what proposal he will make. Then add in pirate 5, and realize he also needs only to improve on the offer of pirate 4 for two of the other pirates to get their vote, and once again, you can figure out his best offer as well.
Since the puzzle places no restrictions on what is proposed, Pirate 5 can get away with 999 gold pieces.
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
Oleander Malcontent
Guest
|
|
Re: HARD: GREEDY PIRATES
« Reply #43 on: Mar 24th, 2003, 3:05pm » |
Quote Modify
Remove
|
I have just read the problem, and I'm too lazy to look through the thread yet, but here's a possible solution:
assumption: the problem states that the money is to be divided according to rank. it looks like a requirement that higher rank ==> more money.
*so pirate 5 proposes that 1 & 2 be KILLED. 3,4,5 all agree, eager to eliminate the biggest earners.
* 4 goes next, and propses to kill 3 (the only bigger-earner left). 5 agrees since this means more money for him too. 4 knew that 5 would be left, so his proposal had to include a fair split (according to rank.. something like 60%/40% or whatever 5 is willing to agree to)
|
|
IP Logged |
|
|
|
rmsgrey
Guest
|
|
Re: HARD: GREEDY PIRATES
« Reply #44 on: Apr 12th, 2003, 11:36am » |
Quote Modify
Remove
|
on Oct 31st, 2002, 9:00am, James Fingas wrote:Icarus,
You're right, #2 wants to kill #3 or #4, not #3 and #4.
As for the dead pirate's money, the problem is found in this scenario:
Step 1:
#3 decides that #4 should live, and #1 does too (you'll see why #3 makes this decision shortly).
Step 2:
#3 proposes 0,4,498,498. #1 Likes this, as it will give him 501 coins (assuming #2 dies). #2 doesn't like it, because he'll die, and he won't get 500 coins. #3 and #4 like it, because it gives them a chance to get money. They both realize that this is better than getting nothing. Here's the problem though: If the dead #2's money gets split up by another round, then #4 must make sure that #1 is there in that round, or #4 will die too! Therefore, #1 can propose 1000,0,0 if #2 dies, and #4 must vote for it, or die in the next round!
See what I mean? If #2's money were thrown overboard with him, then there wouldn't be a second round, and #1 would have to pay off one of #3 and #4, making this their optimal strategy! |
|
Wouldn't actually happen - #2 offers 0,2,499,499 forcing #1 to offer 497,3,500,0 or 497,3,0,500 - either way, expected payoff for #3, #4 is better than if #2 gets rejected so only #1 is unhappy with that proposal.
In general for the 4 pirate problem, if #4 survives, #1 and #2 both vote #3 overboard - whatever #3 offers except 0,0,500,500, #2 can offer #3 and #4 min(333,#3's current take+1,#4's current take+1), himself max(332,remainder) and #1 gets the odd 2 if it comes up. #1 and #2 both always get less than 500 out of it, but their offers are forced through by #3 and #4, one of whom will get 1 better than the alternative (NB this requires bloodlust to be worth less than 0.5 gold per kill). As a result, #3 will always vote the plank for #4 in self preservation, so #4 has to convince #1 and #2 both to keep him and ditch #3 instead - the only way he can do that is with a sufficiently entertaining proposal (pay for a sec change for #3 perhaps) - obviously including a reversion clause for #3's inevitable demise. End result either 500,500,0,X or 500,500,X,0.
Anyone solved the 5 pirate proposal passing problem yet?
|
|
IP Logged |
|
|
|
James Fingas
Uberpuzzler
Gender:
Posts: 949
|
|
Re: HARD: GREEDY PIRATES
« Reply #45 on: Apr 17th, 2003, 1:42pm » |
Quote Modify
|
on Apr 12th, 2003, 11:36am, rmsgrey wrote:
Wouldn't actually happen - #2 offers 0,2,499,499 forcing #1 to offer 497,3,500,0 or 497,3,0,500 - either way, expected payoff for #3, #4 is better than if #2 gets rejected so only #1 is unhappy with that proposal.
In general for the 4 pirate problem, if #4 survives, #1 and #2 both vote #3 overboard - whatever #3 offers except 0,0,500,500, #2 can offer #3 and #4 min(333,#3's current take+1,#4's current take+1), himself max(332,remainder) and #1 gets the odd 2 if it comes up. #1 and #2 both always get less than 500 out of it, but their offers are forced through by #3 and #4, one of whom will get 1 better than the alternative (NB this requires bloodlust to be worth less than 0.5 gold per kill). As a result, #3 will always vote the plank for #4 in self preservation, so #4 has to convince #1 and #2 both to keep him and ditch #3 instead - the only way he can do that is with a sufficiently entertaining proposal (pay for a sec change for #3 perhaps) - obviously including a reversion clause for #3's inevitable demise. End result either 500,500,0,X or 500,500,X,0.
Anyone solved the 5 pirate proposal passing problem yet? |
|
I agree that the result for the 4-pirate case is [500,500,0,X] or [500,500,X,0]. I think it's a little more complicated than you say (ie. if #4 survives, the expected payout is [750.5,248.5,0,1]), but that's not good enough for #2 or #3, so they vote to kill him instead.
However, I think I have found the solution to the 5-pirate proposal-passing problem. The logic behind it is very in-depth, so the best way for me to explain how it works is to just state it, and let you ask questions. So please, give an alternate proposal for any pirate, or give an alternate payoff interpretation, and I'll try to defend my answer.
Before I give you my answer, I have to explain some assumptions. I am assuming that the rules of the bidding go like this:
1) Starting with pirate #5, each pirate makes a proposal. All pirates vote on the proposal (including the one making the proposal). If more than half of them vote to keep the proposal, it becomes the "current proposal". If fewer than half of them vote to keep the proposal, the proposal dies along with the pirate. (this is standard). The pirate cannot propose that money be given to an already-dead pirate, nor that money be thrown overboard, destroyed, or sub-divided into chunks smaller than 1 gold coin.
2) After all pirates have had a chance to make a proposal, the "current proposal" becomes binding. The money is paid out. If the proposal assigns money to a pirate that is dead now, then that money is divvied up by another round of bidding. For instance, for three pirates, if pirate #2 proposes [500,500,0], and that proposal is accepted, then pirate #1 can successfully propose [1000,0,0], because if pirate #1 dies, 500 gold coins are left for a second round in which pirate #3 will die (as there are only two people).
3) If a pirate must divvy up money between two other pirates, then he divvies it up randomly, according to a uniform distribution. If a pirate must choose one of two other pirates to recieve some money, he gives an even chance to each pirate. All pirates know this.
All right, now we're ready for the solution!
The sequence of proposals goes like this:
Pirate 5 makes a proposal, but its content does not matter at all. If pirate 5 dies, then it reduces to the 4-pirate case, in which case the expected payout is [500,500,0,X,X]. If pirate 5 lives, then the expected payout will be [532,267,100.5,50.25,50.25], which all pirates but #2 prefer.
Pirate 4 makes a proposal, of the following form: [0,0,0,T,1000-T], with T <= 250. If the proposal is accepted, the payout is as above, but if the proposal is rejected, then the payout is of the following form: [1000-R,R-1,0,X,1], with R <= 499. Pirates #3-#5 prefer the payout if #4 lives.
If pirate 3 dies, then the payout will be [1000-T,T-1,X,0,1]. Therefore, he proposes either [0,0,400,400,200] or [0,0,400,200,400]. In the case that he proposes [0,0,400,400,200], the payout is either [532,267,201,0,0] or [532,267,0,201,0], and if he proposes [0,0,400,200,400], the payout is either [532,267,201,0,0] or [532,267,0,0,201]. Therefore, either #1 and #4 will object, or #1 and #5 will object. However, the proposal will be carried by the remaining members. From here on in, I will assume that he proposed [0,0,400,400,200].
If pirate #2 dies, then the payout will be [398,X,401,0,201] or [398,X,0,401,201]. Thus, pirate #2 makes one of the following proposals: [0,266,200,267,267] or [0,266,267,200,267]. The expected payouts are [532,267,201,0,0] and [532,267,0,201,0] respectively, so he will get votes from #1, #2, and either #3 or #4 (since their expectation is 401/2 otherwise). I will assume he proposes [0,266,200,267,267] from now on.
If pirate #1 were to die, the payout would be [X,266,200,267,267], so he just has to beat the lowest two entries. He proposes [532,267,201,0,0], which is accepted.
The bidding is complete. Note that there is always a 50% chance of pirate #3 winning the 201 gold pieces, and if he doesn't, then it will be given to either pirate #4 or #5 (pirate #3 gets to choose). Therefore, the final expected payout is [532,267,100.5,50.25,50.25].
|
|
IP Logged |
Doc, I'm addicted to advice! What should I do?
|
|
|
rmsgrey
Uberpuzzler
   
Gender:
Posts: 2872
|
|
Re: HARD: GREEDY PIRATES
« Reply #46 on: Apr 22nd, 2003, 10:43am » |
Quote Modify
|
Whoops - looking back over my solution to 4 pirates passing, I notice I got my expressions for #2's hypothetical offers wrong - they should be max(333,min(#3's current take+1,#4's current take+1)) and min(332,remainder) respectively.
I'm curious as to how "750.5,248.5,0,1" is arrived at for expected pay-out if #4 survives. Particularly since that seems to be inconsistent with the possibility of 500,500,X,0. I suspect the key lies in the handling of the surplus gold in case of corpses. I think my assumption has to be that the surplus gold gets discarded - maybe it gets put into the ship's repair and maintenance fund? I think there are only 3 possible cases for handling corpses - 1) any surplus gold goes back in the kitty for another round; 2) any surplus gold gets disposed of in some other way; 3) all proposals include provisions for redistributing surplus gold - which for smart pirates is equivalent to: no proposal can directly assign gold to lower numbered pirates (for a proposal to take effect, everyone of lower number has to be dead) which can make it hard to let people bribe you.
I don't think there's any particular problem with arbitrarily choosing one of the three conventions - the pirates are smart enough to realise that self-preservation requires all of them to follow the rules even to the extent of throwing drowned men their shares...
|
|
IP Logged |
|
|
|
James Fingas
Uberpuzzler
Gender:
Posts: 949
|
|
Re: HARD: GREEDY PIRATES
« Reply #47 on: Apr 22nd, 2003, 1:45pm » |
Quote Modify
|
rmsgrey,
For gold assigned to corpses, I am assuming they would divide that gold up using another round of proposals. This is essential to all my answers.
[750.5,248.5,0,1] is arrived at roughly like this:
Pirate 4's proposal doesn't matter, but he lives anyways (bad judgement by pirate #3?). If pirate #3 dies at this point, we get payoffs [500,500,X,0], but if pirate #3 proposes [0,0,499,501], then he can survive. The reasoning goes like this:
Pirate #3 proposes [0,0,499,501], and it's accepted. If pirate #2 were to die, the payout would be [500,X,500,0]. Pirate #2 therefore has to beat this. He proposes [0,498,503,0], so that pirate #1 can propose [501,499,0,1]. This is the only way that #3 can survive. His proposal cannot assign any gold to either pirate #1 or pirate #2, because it leads to the [332,334,0,335]/[332,334,335,0] ending, which pirates #1 and #2 don't like. If he assigns more gold to himself than to pirate #4, then pirate #4 will get nothing in the end, and if he assigns gold equally to himself and pirate #4, then pirate #1 will only get 500 gold, which he is not satisfied with.
However, he can assign any amount of gold, R, to himself, and 1000-R to pirate #4. This doesn't change his payoff or #4's payoff, but changes the amounts #1 and #2 get. When pirate #3 offers [0,0,R,1000-R], the payoff is [1000-R,R-1,0,1]. The average value of R over the range [0,499] is 249.5, leading to the expectation [750.5,248.5,0,1].
|
|
IP Logged |
Doc, I'm addicted to advice! What should I do?
|
|
|
rmsgrey
Uberpuzzler
Gender:
Posts: 2872
|
|
Re: HARD: GREEDY PIRATES
« Reply #48 on: Apr 23rd, 2003, 12:08pm » |
Quote Modify
|
Okay, I think I follow - though I'm interested to note that a couple of your proposals feature 1001 coins total 
But, if #4 survives and #3 offers [0,0,499,501] and is accepted, #2 can offer [996,0,3,1] leading to [X,498,501,1] if accepted and [500,X,500,0] if rejected (assuming redistribution of corpses gold). Therefore #3 gets axed if he suggests it and [500,500,X,0] results.
|
|
IP Logged |
|
|
|
James Fingas
Uberpuzzler
Gender:
Posts: 949
|
|
Re: HARD: GREEDY PIRATES
« Reply #49 on: Apr 25th, 2003, 12:53pm » |
Quote Modify
|
on Apr 23rd, 2003, 12:08pm, rmsgrey wrote:Okay, I think I follow - though I'm interested to note that a couple of your proposals feature 1001 coins total
But, if #4 survives and #3 offers [0,0,499,501] and is accepted, #2 can offer [996,0,3,1] leading to [X,498,501,1] if accepted and [500,X,500,0] if rejected (assuming redistribution of corpses gold). Therefore #3 gets axed if he suggests it and [500,500,X,0] results. |
|
Sorry about that! Where I said [332,334,335,0], I meant [332,333,335,0], etc.
I don't think your analysis is correct. Pirate #1 can never be killed. if pirate #2 offers [996,0,3,1] to pirate #1, then the payoffs pirate #1 calculates are [X,498,501,1], so pirate #1 would offer [499,499,0,2] instead. However, when pirate #2 proposes this, pirates #1 and #3 would both vote it down in favour of [500,X,500,0]. Therefore, even though this proposal would give #2 more gold, he won't propose it because it would be defeated.
To simplify things, I never bother having #2 assign any gold to #1. #1's not going to die anyways, and it seems simpler to have #2 offer [0,498,501,1] directly than to have him offer [996,0,3,1].
|
|
IP Logged |
Doc, I'm addicted to advice! What should I do?
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print