Author |
Topic: HARD: GREEDY PIRATES (Read 41147 times) |
|
rmsgrey
Uberpuzzler
Gender:
Posts: 2873
|
|
Re: HARD: GREEDY PIRATES
« Reply #50 on: May 8th, 2003, 6:34pm » |
Quote 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
Gender:
Posts: 949
|
|
Re: HARD: GREEDY PIRATES
« Reply #51 on: May 9th, 2003, 1:30pm » |
Quote 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
Gender:
Posts: 2873
|
|
Re: HARD: GREEDY PIRATES
« Reply #52 on: May 13th, 2003, 12:43pm » |
Quote 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
Gender:
Posts: 949
|
|
Re: HARD: GREEDY PIRATES
« Reply #53 on: May 13th, 2003, 2:08pm » |
Quote 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
Gender:
Posts: 949
|
|
Re: HARD: GREEDY PIRATES
« Reply #54 on: May 14th, 2003, 9:10am » |
Quote 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
Gender:
Posts: 2873
|
|
Re: HARD: GREEDY PIRATES
« Reply #55 on: Jul 24th, 2003, 3:30am » |
Quote 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:
Posts: 115
|
|
Re: HARD: GREEDY PIRATES
« Reply #56 on: May 23rd, 2004, 7:33pm » |
Quote 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
Gender:
Posts: 2873
|
|
Re: HARD: GREEDY PIRATES
« Reply #57 on: May 24th, 2004, 9:00am » |
Quote 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:
Posts: 7527
|
|
Re: HARD: GREEDY PIRATES
« Reply #58 on: May 24th, 2004, 10:24am » |
Quote 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:
Posts: 115
|
|
Re: HARD: GREEDY PIRATES
« Reply #59 on: May 24th, 2004, 2:25pm » |
Quote 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:
Posts: 4863
|
|
Re: HARD: GREEDY PIRATES
« Reply #60 on: May 24th, 2004, 5:43pm » |
Quote 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! ) 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
Gender:
Posts: 2873
|
|
Re: HARD: GREEDY PIRATES
« Reply #61 on: May 25th, 2004, 3:44am » |
Quote 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:
Posts: 7527
|
|
Re: HARD: GREEDY PIRATES
« Reply #62 on: May 25th, 2004, 6:08am » |
Quote 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:
Posts: 115
|
|
Re: HARD: GREEDY PIRATES
« Reply #63 on: May 25th, 2004, 8:26am » |
Quote 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
Gender:
Posts: 2873
|
|
Re: HARD: GREEDY PIRATES
« Reply #64 on: May 25th, 2004, 8:28am » |
Quote 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
Gender:
Posts: 715
|
|
Re: HARD: GREEDY PIRATES
« Reply #65 on: May 25th, 2004, 8:55am » |
Quote 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
Gender:
Posts: 2873
|
|
Re: HARD: GREEDY PIRATES
« Reply #66 on: May 25th, 2004, 8:56am » |
Quote 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
Gender:
Posts: 2873
|
|
Re: HARD: GREEDY PIRATES
« Reply #67 on: May 25th, 2004, 8:59am » |
Quote 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
Gender:
Posts: 715
|
|
Re: HARD: GREEDY PIRATES
« Reply #68 on: May 25th, 2004, 9:02am » |
Quote 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:
Posts: 115
|
|
Re: HARD: GREEDY PIRATES
« Reply #69 on: May 25th, 2004, 10:41am » |
Quote 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:
Posts: 7527
|
|
Re: HARD: GREEDY PIRATES
« Reply #70 on: May 25th, 2004, 2:44pm » |
Quote 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:
Posts: 115
|
|
Re: HARD: GREEDY PIRATES
« Reply #71 on: May 25th, 2004, 7:01pm » |
Quote 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
Gender:
Posts: 2873
|
|
Re: HARD: GREEDY PIRATES
« Reply #72 on: May 26th, 2004, 3:29am » |
Quote 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:
Posts: 7527
|
|
Re: HARD: GREEDY PIRATES
« Reply #73 on: May 26th, 2004, 6:03am » |
Quote 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:
Posts: 115
|
|
Re: HARD: GREEDY PIRATES
« Reply #74 on: May 26th, 2004, 10:24am » |
Quote 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 |
|
|
|
|