wu :: forums
« wu :: forums - HARD: GREEDY PIRATES »

Welcome, Guest. Please Login or Register.
Mar 28th, 2024, 4:06pm

RIDDLES SITE WRITE MATH! Home Home Help Help Search Search Members Members Login Login Register Register
   wu :: forums
   riddles
   hard
(Moderators: ThudnBlunder, william wu, Eigenray, Grimbal, SMQ, towr, Icarus)
   HARD: GREEDY PIRATES
« Previous topic | Next topic »
Pages: 1 2 3 4 5  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print
   Author  Topic: HARD: GREEDY PIRATES  (Read 41073 times)
rmsgrey
Uberpuzzler
*****





134688278 134688278   rmsgrey   rmsgrey


Gender: male
Posts: 2872
Re: HARD: GREEDY PIRATES  
« Reply #50 on: May 8th, 2003, 6:34pm »
Quote Quote Modify Modify

I'm not convinced #1 never dies - all #2 needs to do is offer #3 #1's share (less half what he offers #1 - leading to #3 getting all of #1's share in the end) and #4 what he'd get anyway, and that would beat the offer where all 4 survive - #2 gets the same as he would without the offer or better, plus a corpse. #4 gets the same or better plus a corpse. #3 gets better plus a corpse. #1 has to have a pretty convincing offer up his sleeve to trump that. It's been a while since I thought about this problem, and my internet access is pretty light at the moment, so I'm not going to go any deeper right now.
IP Logged
James Fingas
Uberpuzzler
*****





   
Email

Gender: male
Posts: 949
Re: HARD: GREEDY PIRATES  
« Reply #51 on: May 9th, 2003, 1:30pm »
Quote Quote Modify Modify

rmsgrey,
 
No matter what #2 offers himself, #3, and #4, #1 can always offer more. You say "offer #4 what he would get anyway", but in fact #1 will always offer more than #2 did, in order to buy off #4. Unless we consider #2's offer, we cannot know what the pirates would get.
 
What if pirate #2 proposed [0,A,B,C]. Consider the payouts if #1 were to die: [X,A,B,C]. To survive, pirate #1 just has to offer two of the other three pirates more than they are already getting. He will always choose the two smallest values of A,B, and C, so he pays out min(A,B,C)+1 + mid(A,B,C)+1 to the two appropriate people and keeps the rest. Alternatively, he is paying out 1000-max(A,B,C)+2, which has a maximum value when max(A,B,C) is a minimum, that is to say, when max(A,B,C)=334. Therefore, he will always survive, and always get at least 334-2 gold coins.  
 
Pirate #1 can survive when there are any number of pirates, right up to hundreds. The critical point is when, by eliminating the N/2 highest paid pirates, he doesn't get enough money to pay an extra one gold to the lowest N/2 paid pirates (so the highest ones have to have only one gold each). This happens when there are 1002 pirates or more (he takes one gold each from 500 pirates, but has to give one gold each to 501 pirates). But I think other pirates would get killed before we got to the first one, so we'd likely need to start with a whole lot of pirates to end up with 1002 when we get to #1. I, for one, am not going to attempt to analyze it...
IP Logged

Doc, I'm addicted to advice! What should I do?
rmsgrey
Uberpuzzler
*****





134688278 134688278   rmsgrey   rmsgrey


Gender: male
Posts: 2872
Re: HARD: GREEDY PIRATES  
« Reply #52 on: May 13th, 2003, 12:43pm »
Quote Quote Modify Modify

James Fingas:
 
I think I've found a serious hole in your analysis of the 4-pirates, #4 survives case (serious because of its implications for the 5-pirate case)
 
Whatever #3 offers ([0,0,R,1000-R]), R<500 the payout if #2 dies is [1000-R-1,X,R+1,0] For #2 to survive, he has to make an offer which gives expected returns for #4 and one of #1,#3 better than that. For R<=166 [0,332,334,334] is optimal for #2 giving expected payout of [332,333,167.5,167.5]. For 166<=R<200, an offer by #2 of [0,1000-4R-4,2R+2,2R+2] leading to an expected payout of [2R,1000-4R-3,R+1.5,R+1.5] which again suits #2 better than getting R-1
 
This means that from an accepted offer of [0,0,R,1000-R] by #3, the expected outcomes are as follows:
R<=166 [332,333,167.5,167.5]
166<R<200 [2R,1000-4R-3,R+1.5,R+1.5]
200<=R<500 [1000-R,R-1,0,1]
 
This competes against [500,500,X,0] if #3 is rejected, so #1,#2 reject #3 for R<200 giving final expectation if #4 survives of:
[650.5,348.5,0,1]. So #4 still gets thrown overboard whatever he proposes, but...
 
In the 5 pirate analysis, an offer by #4 of [0,0,0,T,1000-T] with T<=166 leads to [332,333,X,167.5,167.5] if #3 is rejected - which beats the 5 survivor case for #2,#4,#5 and for 166<T<200, the expected result if #4 dies is [2T,1000-4T-3,X,T+1.5,T+1.5] which is preferable for #2 if T<183 so if #4 offers [0,0,0,182,818] then the expected payout for #3 being rejected looks like [364,269,X,183.5,183.5] which is preferable for #2,#4 and #5 to the 5 survivor case, but only preferable for #4,#5 to the case where #5 gets axed so unless there's a better answer by #3 to [0,0,0,182,818] by #4 than the 400/400/200 split it looks like the 5 pirate case actually ends up at [500,500,0,X,X]. Of course, this pattern can't extend beyond the 6-pirate case (hypothetically [500,500,0,X,X,X] though I haven't even started on a proof yet) since if it applies to 6 pirates, with 7, #4-7 will accept #7's to avoid them all dying...
 
As an aside, are there any circumstances (aside from the first proposal of the round which is always irrelevant except possibly for comedy value in a bid for survival) where a pirate ever offers gold to a pirate yet to propose something?
IP Logged
James Fingas
Uberpuzzler
*****





   
Email

Gender: male
Posts: 949
Re: HARD: GREEDY PIRATES  
« Reply #53 on: May 13th, 2003, 2:08pm »
Quote Quote Modify Modify

rmsgrey,
 
Very good analysis! You noticed what I didn't in the analysis of [0,0,R,1000-R], namely that #2 can still buy off #3 even for some R>166. Excellent. I agree with you down to where you start to apply it to the 5-pirate case. I haven't checked that part yet.
 
Great work!
IP Logged

Doc, I'm addicted to advice! What should I do?
James Fingas
Uberpuzzler
*****





   
Email

Gender: male
Posts: 949
Re: HARD: GREEDY PIRATES  
« Reply #54 on: May 14th, 2003, 9:10am »
Quote Quote Modify Modify

Hmm ... your five-pirate analysis is a good start, but I think that #3 will find a way to survive. The answer I gave was based on poor assumptions (as your new analysis of the four-pirate case shows). Most likely #3 can find a way out. Furthermore, if #3 can't find a way out, then #3 will not vote for the proposal. If #4 proposes [0,0,0,182,818] with a payout of [364,269,X,183.5,183.5], then he will lose the vote in favour of [650.5,348.5,0,X,1], which is the payout supposing #4 dies.
 
Now if #3 can find a way to survive, then #4 he may be able to propose this and get away with it. Otherwise, he will be stuck proposing [0,0,0,T,1000-T] with 183 <= T <= 250, with the result [532,267,100.5,50.25,50.25], which at least #3 will ratify.
 
I think I have found the way in which #3 survives. It is not so hard: he just proposes [0,0,198,401,401] (a reverse 200/400/400 split). The expected payoff if #2 dies in this case is [399,X,199,201,201], so #2 will propose [0,266,199,267,268], thereby paying off #3. In this case, the payout is [533,267,200,0,0]. Note that #3 would always use this tactic, depriving #4 and #5 of any money, except that for 200 <= T <= 250, #1 gets too much money to be payed off like this, forcing #3 to pay off #4 and #5 instead.  
 
Now in the case where #4 proposes [0,0,0,T,1000-T] for T <= 166, then the payout if #3 dies is [332,333,X,167.5,167.5]. Since 333 is the largest amount of money that #2 can ever end up with, #3 cannot buy off #2. He can buy off #1, but he also has to buy a vote from either #4 or #5. His 400/400/200 split trick does not work, since it doesn't give enough money to #4 and #5. He cannot split the money 3 ways between himself, #4 and #5, because 1000 isn't divisible by 3. Therefore, I believe he has to sacrificially offer money to either #4 or #5. He offers a reverse 400/400/200 split, but with the winning money to either #4 or #5. His proposal is [0,0,Y,1000-2Y,Y] or [0,0,Y,Y,1000-2Y], with 401 <= Y <= 417. Anything above 417 and the payout for #4 or #5 is not large enough to win a vote. Anything less than 401 means that the payout is split between the two people assigned 'Y', and the required effect is lost. This leads to an average payout of [544,272,0,92,92]. Checking back up the decision tree, this wins for #3 against [332,333,X,167.5,167.5] (because #3 specifies which of #4 or #5 will get the payout). However, it does not win for #4 against [650.5,348.5,0,X,1], because #1, #2, and #3 will all vote against it.  
 
Since #4 must beat [650.5,348.5,0,X,1], if he tries the [0,0,0,T,1000-T] trick, he must use 200 <= T <= 250. For T <= 166, his proposal leads to [544,272,0,92,92], which is rejected. For 167 <= T <= 182, his proposal leads to [533,267,200,0,0], which is also rejected. For 183 <= T <= 199, his proposal also leads to [533,267,200,0,0].
 
As for a pirate proposing something to somebody "up the line", I examined some possibilities, and in every case I found it was worse in one way or another, so I abandoned the search. I have a theory that it is never useful to propose money for a higher-ranked pirate. It would explain why the last pirate's proposal makes no difference (because he has only one useful proposal, namely [0,0,0, ... ,1000]). The analysis of this problem, however, is always messy. I can show it clearly for pirate #2, and I think you could show it for pirate #3, but after that it just gets messy.
 
BTW, I propose we call this puzzle the "Penta-Pirate Proposal Passing Problem". What do you think?
IP Logged

Doc, I'm addicted to advice! What should I do?
rmsgrey
Uberpuzzler
*****





134688278 134688278   rmsgrey   rmsgrey


Gender: male
Posts: 2872
Re: HARD: GREEDY PIRATES  
« Reply #55 on: Jul 24th, 2003, 3:30am »
Quote Quote Modify Modify

Since Icarus has gone to the effrot of tagging this as unsolved, I thought I'd point out that the original version gets a little more interesting once you get more than five pirates since you have only probabalistic information on lower ranked pirates suggestions...
IP Logged
pedronunezmd
Junior Member
**





   


Gender: male
Posts: 115
Re: HARD: GREEDY PIRATES  
« Reply #56 on: May 23rd, 2004, 7:33pm »
Quote Quote Modify Modify

Hope some of you guys are still around. I'd love to get this one solved.
 
I agree that the answer to the 3-pirate case is [500,500,0].
 
The answer that has been brought up for the 4-pirate case appears wrong so far. Pirate #4 would offer [4,0,498,498]. This would lead to an expected payoff at the end of [502,248,125,125]. The reason for the 2 125's is that pirate #2 will ultimately choose, at random, either pirate #3 or pirate #4 for a payment of 250 coins and the other to get zero, I assume that when you calculate "expected payoff" that means that if a certain pirate is going to end up with a 50% chance of 250 coins, that would be an expected payoff of 125 coins.
 
So the logic would go as follows:
 
First of all, it is a given that #1 can never die. Second of all, it is a given that #2 can never die. I have the proofs of both statements if you need them.
 
First round. Pirate #4 proposes anything. It does not matter, because he knows it will be accepted by #3 and #1 and rejected by #2, because he knows there is only one thing #3 will propose when it is his turn. He knows that #3 will come up with the one proposal that guarantees that #1 will end up with more than 500 coins and give both #3 and #4 equal shots at getting 250 coins! Trust me that it will exist for now. If #3 tries to offer something that does not guarantee #1 more than 500 coins, #1 will reject it and #3 dies. If #3 tries to offer something that does not guarantee #4 at least a chance at some coins, #4 will reject it and #3 dies, because otherwise #4 will end up with zero coins and not getting to see anyone die. Pirate #2 will say "no" since he also knows what #3 is going to propose, and that will lead him to less than 500 coins, but if he could somehow kill #4 first, he would get exactly 500 coins. Proposal passes (3-1)
 
Next round. Pirate #3 proposes [4,0,498,498]. This option will ultimately lead #3 to a chance at getting 250 coins, which is better than getting guaranteed zero coins and watching #4 die, which is why he supported not killing #4 in the first round. Pirate #2 says "no" again, because if this goes through, he will end up with fewer than 500 coins, but if can somehow kill #3 he would end up with exactly 500 coins. Pirate #1 says "yes" since this proposal will lead to #1 getting 502 coins, and if he says "no" than #3 will die and #1 only gets 500 coins. Pirate #4 says "yes", because if he says "no" then #3 dies and #4 gets guaranteed zero gold, but if he says "yes" then #4 gets a 50% shot at 250 gold, for an expected payoff of 125 gold. Proposal passes (3-1).
 
Next round. Pirate #2 proposes [0,247,249,504]. Remember that his first priority is to get as much gold for himself as possible. Pirate #1 says "yes" because next round, he'll be able to claim 502 coins, which is higher than the expected payoff if #2 dies of only 501 coins. Pirate #3 says "yes" because he is now guaranteed 250 coins, which is higher than the expected payoff of 249.5 coins if #2 dies. Pirate #4 says "no" because pirate #2 has chosen, at random, to make #4 the pirate who ends up with nothing, but of course, now it is too late. Proposal passes (3-1). Note that pirate #2 could just have easily and randomly had proposed [0,247,504,249] which would have just reversed the positions of #3 and #4 in the final allotment.
 
Final round. Pirate #1 proposes [502,248,250,0]. Pirate #2 now says "yes" since he is getting 1 more than the alternative and previous proposal. Pirate #3 says "yes" because he is getting 1 more than the alternative as well. And poor pirate #4 is left with nothing. (Or #3 and #4 are reversed if pirate #2 had at random choosen the other equal alternative.)
 
If this is okay with everyone (anyone there?) then maybe we can get on to solving the 5-pirate case!
« Last Edit: May 23rd, 2004, 7:38pm by pedronunezmd » IP Logged
rmsgrey
Uberpuzzler
*****





134688278 134688278   rmsgrey   rmsgrey


Gender: male
Posts: 2872
Re: HARD: GREEDY PIRATES  
« Reply #57 on: May 24th, 2004, 9:00am »
Quote Quote Modify Modify

It's been a while since I last thought about this problem at all, but your solution looks good. Checking back over James' previous analysis, the problem comes with the assumption that pirates only assign money to those who have survived their own proposal. That leads directly to the conclusion that #3 can't get any money because #2 always wants #3 or #4 dead, so #4 must expect some money, meaning #3 can't except in the case where #3 and #4 are assigned the same amount - if #3 doesn't trash some by assigning it to #1 or #2, then #1 is looking at a bribe of better than 500 to make one of 3 and 4 happy, meaning he isn't happy.
IP Logged
Grimbal
wu::riddles Moderator
Uberpuzzler
*****






   


Gender: male
Posts: 7526
Re: HARD: GREEDY PIRATES  
« Reply #58 on: May 24th, 2004, 10:24am »
Quote Quote Modify Modify

I have a slightly different solution to the original problem.
 
It is not clear what happens when 2 pirates remain and 2 proposes 1000 to 1 and nothing for himself.  Would 1 refuse the proposal just for the fun of throwing someone over board?  Would 2 take the risk?  That means 2 would not necessarily accept every proposal by 3.  I assume that to win a vote, you have to offer more that what the pirate would get otherwise to be sure to get it.
 
So I propose the following:
1 pirate: 1:1000 is accepted anyway.
2 pirates: 1:1000 2:0 is the outcome whether it is accepted or not.
3 pirates: 3 cannot win 1's vote.  It needs to win 2's so he must offer 1:0 2:1 3:999.  It will be accepted.
4 pirates: 4 cannot win 3's vote, it must win 1's and 2's.  He proposes 1:1 2:2 3:0 4:997.
5 pirates: 5 needs 2 votes, the cheapest are 1's and 3's.  So he offers 1:2 2:0 3:1 4:0 5:997.  This solution is safer than offering the 2 coins to 2.
IP Logged
pedronunezmd
Junior Member
**





   


Gender: male
Posts: 115
Re: HARD: GREEDY PIRATES  
« Reply #59 on: May 24th, 2004, 2:25pm »
Quote Quote Modify Modify

Grimbal, I think your above solution is the generally accepted solution to the original problem. The new offshoot to the original problem, however, is the one proposed by Icarus on 10/25/2002, and is definitely much harder!
 
on Oct 25th, 2002, 6:27pm, Icarus wrote:
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?

By the way, if after a reasonable amount of time, nobody objects to my 4-pirate case solution, I'll post my 5-pirate case solution, since obviously it hinges on knowing what the correct 4-pirate solution is.
« Last Edit: May 24th, 2004, 2:27pm by pedronunezmd » IP Logged
Icarus
wu::riddles Moderator
Uberpuzzler
*****



Boldly going where even angels fear to tread.

   


Gender: male
Posts: 4863
Re: HARD: GREEDY PIRATES  
« Reply #60 on: May 24th, 2004, 5:43pm »
Quote Quote Modify Modify

Grimbal - the accepted interpretation of "bloodthirsty" is that each pirate would prefer to have other pirates dead than alive. The working assumptions that have arisen in the thread are:
 
First, the pirates try to stay alive themselves (money's worthless when you're too dead to spend it! Roll Eyes)
Second, among proposals that leave them alive, pirates will prefer those that give them the greatest amounts of gold.
Third, among the proposals that leave them alive with the greatest amounts of gold, pirates will prefer those that leave the largest number of other pirates dead.
 
If you want, you can add a fourth rule: pirates will prefer higher numbered pirates dead over lower numbered. But this is only a question for the variant, wherein different solutions arise when you have the rule and when you don't.
 
By the way, I still say the solution to the original problem is that Pirate 5 gets 999 coins - though I admit that I allow a looser interpretation of the problem than is used in calculating 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
rmsgrey
Uberpuzzler
*****





134688278 134688278   rmsgrey   rmsgrey


Gender: male
Posts: 2872
Re: HARD: GREEDY PIRATES  
« Reply #61 on: May 25th, 2004, 3:44am »
Quote Quote Modify Modify

Having had time to refresh my memory (dishwashing is a useful chance to think!), I've remembered why the four pirste case can't have #3 offer anything to #1 or #2. If both die, then #3's offer stands, and a second round ensues with #3 and #4 redistributing the surplus. #3 promptly throws #4 overboard, and gets the lot. Therefore, if #2 goes, #1's proposal is going to be voted through by #4 for simple survival, leading to [1000,X,0,0]. So #2 simply has to give #3 and #4 a non-zero expected return, with either  [0,332,334,334] or [1,332,333,334] giving an expected result of [332,333,167.5,167.5]. Both #1 and #2 prefer [500,500,X,0] so any proposal #3 makes assigning money to #1 or #2 will get thrown out immediately. Therefore, I think James Fingas' analysis still stands and the actual outcome for 4 pirates is [500,500,0,X]
IP Logged
Grimbal
wu::riddles Moderator
Uberpuzzler
*****






   


Gender: male
Posts: 7526
Re: HARD: GREEDY PIRATES  
« Reply #62 on: May 25th, 2004, 6:08am »
Quote Quote Modify Modify

on May 24th, 2004, 2:25pm, pedronunezmd wrote:
Grimbal, I think your above solution is the generally accepted solution to the original problem.

No. The accepted solution was to give 2 coins to 1 or 2.  It is better to give to 2.
But I agree, it assumes that "bloodthirsty" only means that they have no remorse killing.
IP Logged
pedronunezmd
Junior Member
**





   


Gender: male
Posts: 115
Re: HARD: GREEDY PIRATES  
« Reply #63 on: May 25th, 2004, 8:26am »
Quote Quote Modify Modify

Rmsgrey, it is impossible for #1 and #2 to die in the 4-pirate case, because it is impossible for #1 to die in the 4-pirate case. In fact, I can prove that in the 45-pirate case (anyone want to propose we solve that one?) that #1 cannot die. I am not sure what happens with the 46-pirate case or higher, but at least all the way up to the 45-pirate case, #1 is guaranteed to live.
 
I am at work right now, so I will be unable to provide the proof that #1 cannot die as long as there are 45 pirates to start with. But I can post it if anyone wants to see it later tonight.
IP Logged
rmsgrey
Uberpuzzler
*****





134688278 134688278   rmsgrey   rmsgrey


Gender: male
Posts: 2872
Re: HARD: GREEDY PIRATES  
« Reply #64 on: May 25th, 2004, 8:28am »
Quote Quote Modify Modify

on May 24th, 2004, 10:24am, grimbal wrote:
It is not clear what happens when 2 pirates remain and 2 proposes 1000 to 1 and nothing for himself.  Would 1 refuse the proposal just for the fun of throwing someone over board?  Would 2 take the risk?  That means 2 would not necessarily accept every proposal by 3.  I assume that to win a vote, you have to offer more that what the pirate would get otherwise to be sure to get it.

Even if #1 isn't guaranteed to throw #2 overboard when given the chance, #2 is likely to regard 0 coins, #3 and #2 survive as a better deal than 0 coins, #3 overboard and possibly #2 survives. The accepted interpretation of the puzzle's conditions is that each pirate places survival above all else, and prefers even the chance of more gold to seeing someone drown.
Quote:

So I propose the following:
1 pirate: 1:1000 is accepted anyway.
2 pirates: 1:1000 2:0 is the outcome whether it is accepted or not.

For 2 pirates, [1000,X] is the outcome: #1 would prefer to see #2 drown and take all the money to anything #2 could offer him.
Quote:

3 pirates: 3 cannot win 1's vote.  It needs to win 2's so he must offer 1:0 2:1 3:999.  It will be accepted.

As above, even if there were a chance of #2 surviving if #3 dies, #2, being more interested in survival than gold, would still support anything #3 suggests.
Quote:

4 pirates: 4 cannot win 3's vote, it must win 1's and 2's.  He proposes 1:1 2:2 3:0 4:997.
5 pirates: 5 needs 2 votes, the cheapest are 1's and 3's.  So he offers 1:2 2:0 3:1 4:0 5:997.  This solution is safer than offering the 2 coins to 2.

Follow through errors give the accepted result of [2,0,1,0,997] or [0,2,1,0,997] being equally likely as far as we can tell from the stated conditions. Depending upon how pirates divide gold among others when they've got no direct stake under the three stipulated conditions, one may take precedence over the other.
IP Logged
Three Hands
Uberpuzzler
*****





    Reucserru+Oymai


Gender: male
Posts: 715
Re: HARD: GREEDY PIRATES  
« Reply #65 on: May 25th, 2004, 8:55am »
Quote Quote Modify Modify

Just had an interesting thought with regards to the 3-pirate case. Basically, each pirate needs the pirate 1 rank above them to survive, since they would otherwise be left making the first proposal in a 2-pirate situation. So, if 1 proposes 1000,0,0, then 2 would be against this, but 3 would support it in order to stay alive (if 1 dies, then 3 makes the next proposal on how to split the cash). So surely this is what the result for the 3 pirate case would be...
IP Logged
rmsgrey
Uberpuzzler
*****





134688278 134688278   rmsgrey   rmsgrey


Gender: male
Posts: 2872
Re: HARD: GREEDY PIRATES  
« Reply #66 on: May 25th, 2004, 8:56am »
Quote Quote Modify Modify

on May 25th, 2004, 8:26am, pedronunezmd wrote:
Rmsgrey, it is impossible for #1 and #2 to die in the 4-pirate case, because it is impossible for #1 to die in the 4-pirate case. In fact, I can prove that in the 45-pirate case (anyone want to propose we solve that one?) that #1 cannot die. I am not sure what happens with the 46-pirate case or higher, but at least all the way up to the 45-pirate case, #1 is guaranteed to live.
 
I am at work right now, so I will be unable to provide the proof that #1 cannot die as long as there are 45 pirates to start with. But I can post it if anyone wants to see it later tonight.

There's a proof higher up the page that #1 doesn't die for up to 1001 pirates (including him) surviving to hear his offer - at that stage #1 is still guaranteed to be able to offer the 500 pirates worst off if he dies one gold more each than they would expect to get by rejecting him.
 
But that's not the point of my argument anyway. By considering what would happen were #1 to be rejected, you get the situation his offer has to beat in order for him to achieve his guaranteed survival. In the 3 pirate case, were #1 to make the offer of [1000,0,0] he would get thrown overboard (assuming #2 didn't assign any gold to him)  and #2's offer would stand. The fact that #1 always survives doesn't mean that he can make any offer he wants and have it pass - it means that he never makes an offer that would be rejected. In the situation where #3's proposal gives money to #1 or #2 (or both) and #2 drowns, any proposal #1 makes will be accepted, so he'll make the greediest.
 
To make sure we're looking at the same set of assumptions:
1) A pirate will follow the rules of distribution
2) A pirate will always try to survive except where this conflicts with the rules of distribution.
3) A pirate will try and secure as much gold as possible except where this conflicts with survival or the distribution rules.
4) A pirate will always try and see as many other pirates dead as possible, except where this conflicts with survival, gaining gold or the rules of distribution.
 
The rules of distribution:
A) Each pirate in turn, starting with the highest numbered (lowest ranked) will propose a distribution of gold so that each pirate is assigned a non-negative integer quantity of gold, with the sum of the assignments being the amount of gold available (1000 on the first pass).
B) Each other surviving pirate will then vote on the current proposal, with ties being broken by the proposer. If the proposal is rejected, then the porposer gets thrown overboard immediately.
C) Once all pirates have made a proposal, the most recent proposal not rejected is applied.
D) Any gold belonging to dead pirates gets pooled together and distributed by the surviving pirates acocrding to these rules.
E) No pirate will kill or steal from another except as permitted by these rules.
 
Rule A is the same as the original problem. Rule D was added to the extension problem after the situation it covers was found to require consideration. Yes, rule D will never be applied, but it controls how much #1 would need to offer in situations where it could apply.
IP Logged
rmsgrey
Uberpuzzler
*****





134688278 134688278   rmsgrey   rmsgrey


Gender: male
Posts: 2872
Re: HARD: GREEDY PIRATES  
« Reply #67 on: May 25th, 2004, 8:59am »
Quote Quote Modify Modify

on May 25th, 2004, 8:55am, Three Hands wrote:
Just had an interesting thought with regards to the 3-pirate case. Basically, each pirate needs the pirate 1 rank above them to survive, since they would otherwise be left making the first proposal in a 2-pirate situation. So, if 1 proposes 1000,0,0, then 2 would be against this, but 3 would support it in order to stay alive (if 1 dies, then 3 makes the next proposal on how to split the cash). So surely this is what the result for the 3 pirate case would be...

 
Only if #2 was silly enough to asisgn gold to #1. If #2 offers [0,R,1000-R] and #1 is rejected, then there's no need for another proposal - #2 pockets R gold, and #3 1000-R. #3 only has to make a follow up proposal if the deceased #1's gold needs to be redistributed.
IP Logged
Three Hands
Uberpuzzler
*****





    Reucserru+Oymai


Gender: male
Posts: 715
Re: HARD: GREEDY PIRATES  
« Reply #68 on: May 25th, 2004, 9:02am »
Quote Quote Modify Modify

Sorry - forgot that clause. No wonder I had a feeling something was wrong, since I've been through the puzzle before and reached the 500:500:0 conclusion before...
IP Logged
pedronunezmd
Junior Member
**





   


Gender: male
Posts: 115
Re: HARD: GREEDY PIRATES  
« Reply #69 on: May 25th, 2004, 10:41am »
Quote Quote Modify Modify

on May 25th, 2004, 3:44am, rmsgrey wrote:
Having had time to refresh my memory (dishwashing is a useful chance to think!), I've remembered why the four pirste case can't have #3 offer anything to #1 or #2. If both die, then #3's offer stands, and a second round ensues with #3 and #4 redistributing the surplus. #3 promptly throws #4 overboard, and gets the lot. Therefore, if #2 goes, #1's proposal is going to be voted through by #4 for simple survival, leading to [1000,X,0,0]. So #2 simply has to give #3 and #4 a non-zero expected return, with either  [0,332,334,334] or [1,332,333,334] giving an expected result of [332,333,167.5,167.5].

I will stop at that point in the posting, because this last statement is wrong. Assume pirate #3 offers [4,0,498,498]. Pirates #1, #3 and #4 will not be happy if #2 now offers [0,332,334,334] and will reject it, thus killing #2. Why? If #2 offers this, then under the previous (#3's) proposal, they are expecting [501,X,249.5, 249.5] if #2 dies, and this new offer only gives expected [332,333,167.5,167.5] and all of #1, #3 and #4 will vote #2 to die. Pirates #1 and #4 will not be happy if #2 instead offers [1,332,333,334] and will reject it, thus killing #2. Why? If #2 offers this, then under the previous (#3's) proposal, they are expecting [501,X,249.5, 249.5] if #2 dies, and this new offer only gives expected [333,333,334,0] and #1 and #4 will vote #2 to die.
 
So, if #3 proposes on his turn [4,0,498,498], #2 will have to figure out a way to give at least 2 people better than expected payoff if he gets killed [501,X,249.5,249.5]. What is that offer, that will maximize #2's gain? Simple, #2 will offer [0,247,249,504] which will be accepted by #1 and #3, or [0,247,504,249] which will be accepted by #1 and #4.
 
Thus I still stand by my original solution proposed on 5/23/2004 for the 4-pirate case.
« Last Edit: May 25th, 2004, 11:59am by pedronunezmd » IP Logged
Grimbal
wu::riddles Moderator
Uberpuzzler
*****






   


Gender: male
Posts: 7526
Re: HARD: GREEDY PIRATES  
« Reply #70 on: May 25th, 2004, 2:44pm »
Quote Quote Modify Modify

on May 25th, 2004, 8:28am, rmsgrey wrote:
Follow through errors give the accepted result of [2,0,1,0,997] or [0,2,1,0,997] being equally likely as far as we can tell from the stated conditions. Depending upon how pirates divide gold among others when they've got no direct stake under the three stipulated conditions, one may take precedence over the other.

No, no.  Correct analysis, but wrong problem.  The result is not the "accepted solution", but that [0,2,1,0,997] is better than [2,0,1,0,997].  So if you are not quite sure to what extent the pirates are bloodthirsty, it is safer to give the 2 coins to #2.
 
For the extended problem, the more I advance, the more it becomes messy.  I get ranges or valid proposals that supposedly I have to average out.
IP Logged
pedronunezmd
Junior Member
**





   


Gender: male
Posts: 115
Re: HARD: GREEDY PIRATES  
« Reply #71 on: May 25th, 2004, 7:01pm »
Quote Quote Modify Modify

Okay, rmsgrey, now I see the problem. As I've been working on the solution, I did not like the idea of a "second round" of proposals as a way of distributing any gold assigned to a dead pirate. I've been working under the assumption that any proposal included what would happen to any gold given to a dead pirate. The 5-pirate case proposed by Icarus did not specify for a second round of proposals.
 
Quote:
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.

I took this to mean that once all 5 pirates made their one proposal each, the gold is split up then and there. There is no mention of a second round of proposals in the rules. Therefore, it has to be known in advance what will happen with the dead pirates' gold at the end of all the proposals.
 
I would propose that the best way to fit the rules outlined by Icarus as above would be that each pirate, in making his offer, has to outline what will happen to any gold assigned by his method to a dead pirate, and that "shift" would occur as soon as that pirate died. For example, pirate #2 could say "I get 500 gold, and #1 gets 500 gold, but if #1 is killed, all this gold immediately will go to #3."
 
Alas, re-reading all of the previous posts, it looks like I might be outvoted on this issue and will have to walk the plank.
IP Logged
rmsgrey
Uberpuzzler
*****





134688278 134688278   rmsgrey   rmsgrey


Gender: male
Posts: 2872
Re: HARD: GREEDY PIRATES  
« Reply #72 on: May 26th, 2004, 3:29am »
Quote Quote Modify Modify

As I recall, at the point where the need to establish procedures for redistribution became apparent, three different suggestions came up - a second round, throw the gold overboard with the body, or have contingency clauses built into every proposal.
 
Obviously, the first of the three became the accepted version. Even with built in contingency clauses, there's a problem with pedronunezmd's proposal. If #2 dies, #1 is competing, not with #3's original proposal, but with the contingency version. The contingency has to assign all the gold to #3 and #4, and must do so equally or favour #4 (by asisgning more to #3) if #3 wants #4's support. If it splits equally, then #1 needs to assign 501 to one of them to get their support, leaving himself with less than 500. If it's unequal, then #3 gets nothing. Therefore, #2 needs to beat [499,X,250.5,250.5] for 2 of the others - either [0,500,250,250] or [0,248,250,502] (or switch #3 and #4), giving payouts of [498,0,251,251] and [500,249,251,0] respectively. Obviously, he prefers the second, but both #1 and #2 would prefer [500,500,X,0] (or [500,500,0,X]) so reject #3's proposal.
 
As an aside, including contingencies is equivalent to banning assignments of gold to pirates yet to make a proposal - the only version of their proposal that could take effect is the contingency when everyone else afterwards gets thrown overboard. Therefore, any other contingencies included in the proposal are irrelevant.
 
If you consider cases where assigned gold needs to be reassigned in subsequent rounds, then (with the exception of the first to speak whose proposal is irrelevant - either a subsequent proposal is accepted anyway, or #2's proposal gets accepted by #1 on survival grounds), any proposal that assigns gold to a pirate yet to make a proposal again needs to be evaluated in terms of the outcome if all subsequent pirates die - which is again effectively a proposal for splitting the gold amongst those who have already made their proposals (possibly with non-integer values if there is a range of possible outcomes). Again, this is generally equivalent to banning proposals where pirates yet to speak get assigned gold, except in those cases where non-integer distributions result.
 
The only one of the three which differs substantially from banning assigning gold to lower numbered pirates is ditching the orphaned gold over the side, and in most cases the only motive would be to keep others from getting it. It's possible that there are cases where ditching the odd piece of gold improves distribution.
IP Logged
Grimbal
wu::riddles Moderator
Uberpuzzler
*****






   


Gender: male
Posts: 7526
Re: HARD: GREEDY PIRATES  
« Reply #73 on: May 26th, 2004, 6:03am »
Quote Quote Modify Modify

There is another point to clarify in the case of multiple rounds:
Suppose a pirate gets some money in the first round, and there is some money to be redistributed in a second round.  If the pirate dies in the second round, what happens to the money he got in the first round?
If a pirate gets killed, the money he was to get can be reused in a subsequent proposal.  Now if the money he got from previous rounds must also be redistributed, it would make sense that all of the pirate's money is immediately available to be allocated in the next pirate's proposal.
We can also imagine that a pirate in a difficult situation wants to offer some coins he got in a previous round, just for surviving.  If we continue in that direction, we could imagine that in a new round, all of the money is in play again, regardless of who earned what in the first rounds.
 
To this extreme, it will probably make the game endless. But we still need to know what happens to a dead pirate's money.  Is it "recycled"?  if yes, when.
IP Logged
pedronunezmd
Junior Member
**





   


Gender: male
Posts: 115
Re: HARD: GREEDY PIRATES  
« Reply #74 on: May 26th, 2004, 10:24am »
Quote Quote Modify Modify

This is part of the reason I don't like the "second round" idea.  
 
In my example, where any proposal has to include contingencies, pirate #3's offer would look like this:
 
"I propose [4,0,498,498] and if pirate#1 dies, his 4 gold coins gets thrown in the ocean."
 
This would result in an expectation, if #2 gets killed and #1 gets killed of [X,X,498,498], which #1 would beat by proposing [501,X,499,0] or [501,X,0,499], therefore #1 will agree to #3's proposal. Finally #3 and #4 are being offered, by #3's proposal, a nonzero expectation of coins, and would also agree to vote yes for #3's proposal.
IP Logged
Pages: 1 2 3 4 5  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print

« Previous topic | Next topic »

Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board