|
||||||||
|
Title: HARD: GREEDY PIRATES Post by Frank Gevaerts on Jul 25th, 2002, 8:57am Greedy Pirates (http://www.ocf.berkeley.edu/~wwu/riddles/hard.shtml#greedyPirates) I think this should be solved in reverse order : 1 : his proposal will of course be accepted 2 : Since 1 can always make a better proposal himself, he will reject this one. Therefore, 2 needs to make sure anm earlier proposal is accepted 3 : Because 2 will not survive his own proposal, he will accept any proposal that 3 makes, even if he gets nothing. 1 is irrelevant. 3 will therefore propose to keep all coins for himself 4 : Since 3 can get a everything proposal, he will reject this one. However, if this proposal is rejected, 1 and 2 will get nothing. If 4 offers 1 coin each to 1 and 2, and keeps 998 coins, they will both accept. 5 : Since 1 and 2 can hope for only 1 coin each if 5s proposal gets rejected, they will support 5 if he offers them at least 2 coins each. The optimal proposal is therefore : 2 coins for 1, 2 coins for 2, 996 coins for 5. |
||||||||
|
Title: Re: HARD: GREEDY PIRATES Post by kul on Jul 25th, 2002, 11:19pm The solution is that 5 will propose 998 for himself and 1 coin each for 3 and 4. If this proposal is rejected, 3 and 4 cannot get anything as 1 and 2 can reject all proposals and finally accept 500 coins each. Note that majority is required for accepting a proposal. |
||||||||
|
Title: Re: HARD: GREEDY PIRATES Post by Frothingslosh on Jul 26th, 2002, 12:09am kul: The solution is that 5 will propose 998 for himself and 1 coin each for 3 and 4. If this proposal is rejected, 3 and 4 cannot get anything as 1 and 2 can reject all proposals and finally accept 500 coins each. Note that majority is required for accepting a proposal. No, I think Frank is right. The 500/500 split is certainly wrong, as if 2 ever proposes it (or anything else, even giving all the coins to 1!) he will be killed by the bloodthirsty 1 and not able to get a majority - 1 gets to keep everything and kill 2 if 2 makes any proposal. While you said 3 can't get anything as 1 and 2 can reject all proposals, 2 can't reject 3's proposal and live. If 3 walks the plank, 2 does also! I wanted to find a solution where 3, 4 and 5 agree, maybe with 5 even getting everyhing and 3 and 4 agreeing to save their lives, but 3 is smart and knows that 2 is smart enough to have to agree with anything 3 proposes, so 3 will not make a deal with 5. Strangely, the pirates were not quite smart enough to know better than to set up this way of splitting the loot in the first place! |
||||||||
|
Title: Re: HARD: GREEDY PIRATES Post by kul on Jul 26th, 2002, 7:00am Frothingslosh: you are right! I was wrong about 1 and 2 sharing! Cannot think straight at 1 am. However, the solution is: 5 proposes 2 coins for either 1 or 2, 0 coin for 3 and 998 for himself. The reasoning is: Going backwards: 2 Proposes: 1 rejects; 3 Proposes: 0 for 2 and 1000 for himself; 2 keeps life 4 proposes: 1 for 1 and 2 and 998 for himself. ( 1 and 2 do better here than in 3's proposal). 5 proposes: 2 for either 1 or 2, 0 for 3, and 998 for himself. what is better for them in this than in 4's proposal: 1 or 2 gets 1 more coin. 3 gets to live. |
||||||||
|
Title: Re: HARD: GREEDY PIRATES Post by kul on Jul 26th, 2002, 7:06am Actually it is : 2 for 1 or 2 and 1 for 3, and 997 for 5. The reason is 3 lives even if 4 proposes, so he has to do better in 5's proposal. |
||||||||
|
Title: Re: HARD: GREEDY PIRATES Post by mebden on Jul 27th, 2002, 10:45am Yes I think that's it, kul. |
||||||||
|
Title: Re: HARD: GREEDY PIRATES Post by tim on Jul 27th, 2002, 6:15pm I read the problem differently, with a different idea in mind for what "proposal" meant. I read it as any procedure for dividing the treasure. For example, I thought that 5 could make a proposal including something like "1 and 2 flip a coin to determine who gets it". Then everyone votes. No wonder I couldn't find a unique solution! That aside, there is another more serious problem with the question: the pirates have two conflicting goals. They are both bloodthirsty and greedy. Are they more bloodthirsty than greedy, or the reverse? Let's look at 4's proposal, under which both 1 and 2 get a coin each. 3 will definitely reject it. If 1 and 2 accept it, they don't get to kill anyone. Is one lousy coin enough to buy off their bloodthirstiness? I wouldn't have thought so. In order for kul's solution to work, the pirates have to value a single gold coin above the pleasure of tossing someone overboard. The problem doesn't say whether that's true or not, so we can't know whether it will work. |
||||||||
|
Title: Re: HARD: GREEDY PIRATES Post by Nathan on Jul 27th, 2002, 6:38pm Tim, great post. I was laughing out loud reading it. |
||||||||
|
Title: Re: HARD: GREEDY PIRATES Post by Fluffy on Jul 27th, 2002, 8:10pm Close, everyone, but no cigar. NOTE: this solution implies that the puzzle DOES have a single solution, and that we CAN determine the answer from the information given. (I'm assuming that this is implied for ALL puzzles). First, we need to construct a behavior model for the pirates. We know exactly three facts about them; a) Infinitely intelligent b) greedy c) bloodthirsty. From a, we can imply three things; first, that any given pirate will always make the choice that will maximise his gains. Second, a pirate will never make an incorrect choice. Third, every pirate knows everything that every other pirate knows. (Corollary: every pirate knows all of the above facts). Greedy simply means that they desire gold, bloodthirsty means that they desire the death of other pirates. As a previous poster said, we do not know which is the greater desire, greed or bloodthirst. Therefore, let's assign the value B to represent the amout of pleasure a pirate gets from another pirate's death. B is measured in gold coins, since there are no other standards of measurement. We know that B is not 0, since that would mean that the pirates are _not_ bloodthirsty after all. We know that B is not greater that 1000, since that would result in every single proposal being rejected, rendering the puzzle moot. So, B is 1000 or less. Since we are assuming that the problem is solvable, we can conclude that B is so small as to be statistically insignifigant, since a signifigant number would represent a datum we do not possess, making the problem unsolvable. Yes, this assumption could be considered circular logic; let's just assume it isn't. ;D As most people have reasoned, pirate 1 will simply propose he gets all the gold, which will suceed. Thus, no matter what pirate 2 proposes, 1 will vote no and it will fail. Most people said that pirate 3 will propose 1000 gold for himself. However, if he does, 2 WILL VOTE NO! Why? Bloodthirst! If he votes yes, he gets no gold and sees two pirates die; if he votes no, he gets no gold and sees three deaths (four if you count himself!) Yes, it's odd that a pirate places no value on his own life, but if he did the rules should have said so. Therefore, 3 will propose 999 gold for himself and 1 for pirate 2. 2 will vote yes, making it pass. (remember, even one gold piece is worth more than any amount of deaths). So, 4 will propose one gold for 1, two for 2, and 997 for himself. 1 and 2 will vote yes, since both will be getting more gold than they would otherwise, making the proposal pass. Therefore, 5 should propose 2 gold for pirate 1, 3 gold for pirate 2, and 995 for himself. Again, 1 and 2 will vote yes, making it pass. |
||||||||
|
Title: Re: HARD: GREEDY PIRATES Post by Mark Ebden on Jul 28th, 2002, 6:17am Fluffy, Interesting, that's clever. But I think this part is wrong: "a pirate places no value on his own life ... if he did the rules should have said so." :o The rules DID say so, when they announced that the pirates are very intelligent. An intelligent person understands that his life has value and meaning to himself. I take that as a given, and most people would. It is common sense; I don't think the puzzle was meant to 'trick' us in such a trivial way. If you are still skeptical, consider as well that the pirates are "greedy". You cannot have greed without a sense of self worth; that's because you don't aggrandize to help someone else, you do it solely to benefit yourself. Why? Because you believe yourself to be more important than others. If the pirates were infinitely "financially-motivated", then MAYBE they would not value their own life. But because they are "intelligent", and for that matter "greedy", they do. Hence I think kul's answer earlier on is still correct. Cheers, Mark |
||||||||
|
Title: Re: HARD: GREEDY PIRATES Post by Frost on Jul 28th, 2002, 7:12am How about this one: The pirates are infinitely bloodthirsty, so no finite amount of coins can save a pirate's life. Each pirate knows they'll die if they get to propose, so they'll always agree. Pirate 5 takes all the coins. |
||||||||
|
Title: Re: HARD: GREEDY PIRATES Post by tim on Jul 28th, 2002, 3:20pm Frost: Quote:
No, pirate 3 knows that pirate 2 will accept his proposal out of self-preservation. (Or to put it another way, to avoid giving up all future killings) Pirates 4 and 5 will always be outvoted by 1 2 3, all three of whom want to see them die. If there were 7 highly bloodthirsty pirates, things would be different: 4 5 6 would know that they're doomed by 1 2 3, and so agree with 7 on anything. Another interesting problem arises where the bloodthirst is of trivial value: Given that the treasure hoard consists of 1000 coins, and that any proposal must allocate an non-negative integer number of coins to each pirate, how many pirates can there be before the lowest-ranked pirate is thrown overboard regardless of what they propose? |
||||||||
|
Title: Re: HARD: GREEDY PIRATES Post by Frost on Jul 29th, 2002, 2:11am The more I look at this riddle, the more solutions I get. I even tried to design a new "infinitely bloodthirsty vampires" riddle, with the marketprice of a bucket of blood dropping when another vampire dies (less demand, more supply). Didn't work out though. |
||||||||
|
Title: Re: HARD: GREEDY PIRATES Post by srowen on Jul 29th, 2002, 12:19pm on 07/27/02 at 20:10:49, Fluffy wrote:
I think the intended interpretation involves two assumptions: * Pirates are primarily concerned with gold, but all else being equal, would rather see somebody die. That is, B=0.5. This should be stated in the problem. * They value their lives above any amount of gold, as dead pirates sure don't keep their gold long. This is implied I think. I believe this leads to the intended answer of: 997 for pirate 5 0 for pirate 4 1 for pirate 3 2 for pirate 2 0 for pirate 1 5 needs to win the votes of 2 pirates by making their share larger than what it would be if 4 decided things. Working out the cheapest way to do that (under the assumptions above) leads to this answer. |
||||||||
|
Title: Re: HARD: GREEDY PIRATES Post by Gamer555 on Jul 29th, 2002, 7:38pm Sorry if I missed anything! I feel yall are very good at coming up with solutions... Do any of you feel we need to come up with seperate solutions (like if bloodthirstiness beats greed, and so on) because it seems like now we are solving 2a + b = 5 and we can't come up with one solution... Hmmm... ??? PS: Just say so if I am wrong (I am sure i missed something) but wouldn't 3 turn down the recent request? ("I believe this leads to the intended answer of: 997 for pirate 5 0 for pirate 4 1 for pirate 3 2 for pirate 2 0 for pirate 1") If 4's request gave anything but 0 coin for 3, he would turn it down, right? Sorry if i am not paying attention. |
||||||||
|
Title: Re: HARD: GREEDY PIRATES Post by Alex Harris on Jul 29th, 2002, 8:22pm Yes it does matter whether greed or bloodthirst are more important, and how important survival is. I think survival > bloodthirst/greed seems most logical, but as for the ratio of bloodthirst and greed you could argue lots of different things. srowen's answer is correct for his stated assumptions of survival >> greed >> bloodthirst. If 5's proposal gets voted down then 4 would propose 998, 0, 1, 1 so 3 would get nothing and he prefers the 1 gold he'd get from 5's proposal. The easiest general way to do these is just to build up from the bottom. What if there are 2 pirates, then add a third, etc. A generalization: if survival is top priority, then after that each pirate you see die is worth k gold (break ties in favor of bloodthirst). If k < 333: 5 proposes #1 gets 0, #2 gets 2k+2, 3 gets k+1, #4 gets 0, 5 gets 997-3k. (#1 and #2 are interchangable for this) If 333 <= k < 500: 5 proposes #1 and #2 get 0, #3 gets k+1, #4 gets 999-k, #5 gets 0. If 500 <= k < 1000 5 proposes #1 #2 and #4 get 0, #3 gets k+1, #5 gets 999-k If k >= 1000 5 and 4 are doomed, 3 proposes 1000 for himself and wins. Its a bit interesting the way it works out. 5 has to pay out more and more as k rises until he gets down to 0, but then at 500 he can make money again because he no longer has to pay off #4 who is doomed if it becomes his turn. |
||||||||
|
Title: Re: HARD: GREEDY PIRATES Post by tim on Jul 29th, 2002, 9:08pm For the 500 <= k < 1000 case: I presume you meant that #1 or #2 gets k+1, since 3 isn't going to be bought off. If #5 dies, so does #4 and #3 gets 1000 coins + 2 deaths. |
||||||||
|
Title: Re: HARD: GREEDY PIRATES Post by klbarrus on Jul 29th, 2002, 9:57pm I thought this puzzle sounded vaguely familiar, and did a search, finding "A Puzzle for Pirates" in the May 1999 issue of _Scientific American_. The text adds a bit more info, that pirates enjoy throwing others overboard, but prefer gold coins instead. No pirate enjoys suicide either. The explanation follows the "work backwards" reasoning that many have explored, and arrives at a slightly different answer (puzzle is slightly different, dividing 100 coins among pirates): P1 and P3 get 1 coin each P2 and P4 get no coins P5 gets the remainder Basically you get here by starting with 2 pirates: P2 says he gets all, and P1 gets none. P2's vote is good enough to carry, so the proposal is accepted. Add another pirate: P1 will support anything that results in more than nothing, what he got when P2 proposed. So P3 says 1 for P1, 0 for P2, rest for P3. With another pirate, P2 will vote for anything that gets him more than 0, so P1 and P3 get 0, P2 gets 1, P4 gets the rest. And so forth. The pattern that emerges is the last pirate has to bribe every other pirate with a gold coin to get their vote. The interesting part of the article in the magazine is what happens when there isn't enough money to bribe all the pirates - the original puzzle examined is something like divide 100 coins among 500 pirates. I won't mention anything further in case somebody wants to work on it :) 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 |
||||||||
|
Title: Re: HARD: GREEDY PIRATES Post by AlexH on Jul 29th, 2002, 10:16pm Doh. Wasn't paying enough attention when I did that. Good catch tim. I got so happy that we had the "interesting behavior" of 5 getting money again that I didn't properly check that. Sadly 5 has to pay off 2 or 1, but since they'll get to see both 4 and 5 die he won't have the cash to manage it. At k >= 500 we get the same result as k >=1000. 4 and 5 die while 3 takes all the gold. |
||||||||
|
Title: Re: HARD: GREEDY PIRATES Post by mebden on Jul 30th, 2002, 7:43am Thanks Klbarrus, that clears it up completely. The problem on William Wu's site now seems to be very likely modelled on the Scientific American puzzle - but there is of course one important difference: In Mr Wu's puzzle, "A proposal is accepted if and only if a majority of the pirates agrees on it." According to dictionary.com, a majority is "a number more than half of the total". The Oxford English Dictionary agrees, defining a majority as "a number which is more than half the whole number." So we have to make a few adjustments on Scientific American's answer, which requires merely 50.0% for acceptance, instead of a majority. We end up deriving kul's answer above (scroll way up!): 2 coins for 1 or 2, 1 for 3, 0 for 4, and 997 for 5. What a neat puzzle. Cheers, Mark ::) ::) ::) ::)[font=Verdana][/font] |
||||||||
|
Title: Re: HARD: GREEDY PIRATES Post by Erit on Jul 30th, 2002, 3:09pm if pirate 4 knows what pirate 5 WILL do and he knows he will get nothing. Why doesn't he propose 1 for himself and 499 for pirate 1 and 500 for pirate 2. That way pirate 5 would have no way of appeasing pirate 2 without making pirate 1 mad (without pirate 5 getting nothing) and vice versa, so he'll give 1 to pirate 3 (who had nothing) and 2 to pirate 4 (who now has one more) who will agree because they get more than before and pirate 1 and 2 will get nothing. If I were pirate 4 that's what I would do. (Hey it beats getting more than zero!) Am I wrong here or am I making sense? Actually, can't pirate 4 give himself even more up to a certain point? Because as long as he doesnt give himself more than what pirate 1 and 2 are getting each, pirate 5 will have to bribe pirate 3 with 1 (that's all thats needed to bribe) and bribe pirate 4 with one more than what pirate 4 proposed for himself. Because pirate 5 wouldn't bribe 1, 2 with more money since he'd lose more money himself so he'd have to settle with bribing pirate 3 and 4. So in this case: Pirate 4 proposal: 1) 334 2) 334 3) 0 4) 332 5) 0 1 and 2 will definitely accept this since its a lot more (then again if they know what then pirate 5 will do and they will get nothing then will they deny this??) so then pirate 5 would do the smart thing and bribe 3 and 4 as to give himself more money 1) 0 2) 0 3) 1 4) 333 5) 666 (its the devils question I knew it! ;) does this make any sense?? I dunno! im at work and bored to heck! ahhhhhhh hehe This whole (I know what you're gonna do so here's what I'm going to do but you knew that already so this is what im going to do but...) is really confusing me. It's like that one guy in The Princess Bride =P Because if you're dealing with this with one pirate first then two pirates then three.. up to five and if each pirate is indeed infinitely smart they will know what the next pirate(s) will do and use some sort of scheme to at least get SOMETHING. No infinitely smart pirate would allow himself to get zero without somehow giving himself one and giving the rest to others at least. Or are we just assuming here that the pirates don't know what will happen when an additional pirate is added? (but that defeats the question) Sigh.. ok my head hurts, let me know, thanks. Eric |
||||||||
|
Title: Re: HARD: GREEDY PIRATES Post by Erit on Jul 30th, 2002, 3:16pm Actually this can be applied to other pirates too to screw over other pirates from getting stuff. Im just applying it to the original situation thinking from pirate 4's position. =P Eric |
||||||||
|
Title: Re: HARD: GREEDY PIRATES Post by hot dog samurai on Jul 30th, 2002, 3:21pm personally i think the pirates will kill each other regardless of what happens because they are pirates and that's what pirates do. actually, pirates aren't exactly mathematicians, so during the 20 years it takes them to come up with a solution they will probably all die of scurvy. |
||||||||
|
Title: Re: HARD: GREEDY PIRATES Post by Mark Ebden on Jul 31st, 2002, 3:15am Hi Erit, Interesting, but a case of over-analysis. Since the puzzle says "Starting with pirate 5 they can make a proposal...", the unfortunate Pirate 4 :-X cannot propose anything until Pirate 5 does. So, your statement about Pirate 4, "Why doesn't he propose 1 for himself and 499 for pirate 1 and 500 for pirate 2", doesn't apply, since this proposal cannot possibly be announced until AFTER Pirate 5 is thrown overboard. And, here's the most important part: IF/when Pirate 5 is thrown overboard, of course all the pirates know that Pirate 4 will NOT go ahead and make the proposal above, no matter how much they thought he might previously. Instead of giving all the coins away to his cap'n and first mate, he will change his mind at the last minute and keep most of the coins for himself (as per kul's solution above) because he is greedy and he CAN. ;D So yeah, to keep this problem soluble, we have to assume the pirates make no deals or alliances with each other, no hand-shaking, nudges or winks. Otherwise, a near-infinity of solutions explodes. Cheers, Mark |
||||||||
|
Title: Re: HARD: GREEDY PIRATES Post by Eric Yeh on Aug 1st, 2002, 9:03am Re: tim's msg: First, to clarify the principles of the original problem, the priorities of the pirates are, in order: 1) Preserve your own life, 2) Maximize your number of gold pieces, and 3) Kill as many pirates as possible. Although kul's answer is the correct one for this formulation of the problem, I like your idea of generalizing to probabilities (btw, for some reason I recall the true original problem leaving out the survivorship priority, so that the answer comes out uniquely as (2/0/1/0/997) -- if anyone recalls please let me know). Unfortunately, allowing probabilities doesn't make the problem significantly harder in this case; the answer just becomes (2 delta/0/delta/0/1000-3delta), where delta is the smallest probability the pirates can simulate, and 1 and 2 are interchangeable as before. Oh well. |
||||||||
|
Title: Re: HARD: GREEDY PIRATES Post by Vincenzo on Aug 5th, 2002, 2:26pm klbarrus has the right answer! This is an old puzzle I've seen before. |
||||||||
|
Title: Re: HARD: GREEDY PIRATES Post by Chronos on Aug 6th, 2002, 12:11pm 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. |
||||||||
|
Title: Re: HARD: GREEDY PIRATES Post by kul on Aug 9th, 2002, 8:33am 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. |
||||||||
|
Title: Re: HARD: GREEDY PIRATES Post by AlexH on Aug 10th, 2002, 7:29pm 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. |
||||||||
|
Title: Re: HARD: GREEDY PIRATES Post by Seb on Aug 13th, 2002, 7:43am 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 |
||||||||
|
Title: Re: HARD: GREEDY PIRATES Post by Icarus on Oct 25th, 2002, 6:27pm 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! |
||||||||
|
Title: Re: HARD: GREEDY PIRATES Post by James Fingas on Oct 28th, 2002, 12:37pm 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! |
||||||||
|
Title: Re: HARD: GREEDY PIRATES Post by Icarus on Oct 28th, 2002, 3:43pm 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. |
||||||||
|
Title: Re: HARD: GREEDY PIRATES Post by James Fingas on Oct 29th, 2002, 7:59am 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. |
||||||||
|
Title: Re: HARD: GREEDY PIRATES Post by Icarus on Oct 29th, 2002, 4:23pm 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:
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. |
||||||||
|
Title: Re: HARD: GREEDY PIRATES Post by James Fingas on Oct 31st, 2002, 9:00am 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! |
||||||||
|
Title: Re: HARD: GREEDY PIRATES Post by Icarus on Oct 31st, 2002, 9:54pm 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. |
||||||||
|
Title: Re: HARD: GREEDY PIRATES Post by James Fingas on Nov 1st, 2002, 8:10am 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. |
||||||||
|
Title: Re: HARD: GREEDY PIRATES Post by Icarus on Nov 1st, 2002, 3:53pm 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! |
||||||||
|
Title: Re: HARD: GREEDY PIRATES Post by James Fingas on Nov 4th, 2002, 1:50pm 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! |
||||||||
|
Title: Re: HARD: GREEDY PIRATES Post by Icarus on Nov 4th, 2002, 5:45pm Sorry, but I didn't read all your post. After I read rule 1, I had to stop! 8) |
||||||||
|
Title: Re: HARD: GREEDY PIRATES Post by UofLis#1 on Mar 10th, 2003, 3:11pm 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 :D -Ford |
||||||||
|
Title: Re: HARD: GREEDY PIRATES Post by Icarus on Mar 10th, 2003, 6:48pm 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 [hide]999 gold pieces[/hide]. |
||||||||
|
Title: Re: HARD: GREEDY PIRATES Post by Oleander Malcontent on Mar 24th, 2003, 3:05pm 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) |
||||||||
|
Title: Re: HARD: GREEDY PIRATES Post by rmsgrey on Apr 12th, 2003, 11:36am on 10/31/02 at 09:00:32, James Fingas 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? |
||||||||
|
Title: Re: HARD: GREEDY PIRATES Post by James Fingas on Apr 17th, 2003, 1:42pm on 04/12/03 at 11:36:33, rmsgrey wrote:
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]. |
||||||||
|
Title: Re: HARD: GREEDY PIRATES Post by rmsgrey on Apr 22nd, 2003, 10:43am 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... |
||||||||
|
Title: Re: HARD: GREEDY PIRATES Post by James Fingas on Apr 22nd, 2003, 1:45pm 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]. |
||||||||
|
Title: Re: HARD: GREEDY PIRATES Post by rmsgrey on Apr 23rd, 2003, 12:08pm 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. |
||||||||
|
Title: Re: HARD: GREEDY PIRATES Post by James Fingas on Apr 25th, 2003, 12:53pm on 04/23/03 at 12:08:17, rmsgrey wrote:
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]. |
||||||||
|
Title: Re: HARD: GREEDY PIRATES Post by rmsgrey on May 8th, 2003, 6:34pm 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. |
||||||||
|
Title: Re: HARD: GREEDY PIRATES Post by James Fingas on May 9th, 2003, 1:30pm 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... |
||||||||
|
Title: Re: HARD: GREEDY PIRATES Post by rmsgrey on May 13th, 2003, 12:43pm 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? |
||||||||
|
Title: Re: HARD: GREEDY PIRATES Post by James Fingas on May 13th, 2003, 2:08pm 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! |
||||||||
|
Title: Re: HARD: GREEDY PIRATES Post by James Fingas on May 14th, 2003, 9:10am 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? |
||||||||
|
Title: Re: HARD: GREEDY PIRATES Post by rmsgrey on Jul 24th, 2003, 3:30am 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... |
||||||||
|
Title: Re: HARD: GREEDY PIRATES Post by pedronunezmd on May 23rd, 2004, 7:33pm 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! |
||||||||
|
Title: Re: HARD: GREEDY PIRATES Post by rmsgrey on May 24th, 2004, 9:00am 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. |
||||||||
|
Title: Re: HARD: GREEDY PIRATES Post by grimbal on May 24th, 2004, 10:24am 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. |
||||||||
|
Title: Re: HARD: GREEDY PIRATES Post by pedronunezmd on May 24th, 2004, 2:25pm 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 10/25/02 at 18:27:10, Icarus wrote:
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. |
||||||||
|
Title: Re: HARD: GREEDY PIRATES Post by Icarus on May 24th, 2004, 5:43pm 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. |
||||||||
|
Title: Re: HARD: GREEDY PIRATES Post by rmsgrey on May 25th, 2004, 3:44am 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] |
||||||||
|
Title: Re: HARD: GREEDY PIRATES Post by grimbal on May 25th, 2004, 6:08am on 05/24/04 at 14:25:58, pedronunezmd wrote:
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. |
||||||||
|
Title: Re: HARD: GREEDY PIRATES Post by pedronunezmd on May 25th, 2004, 8:26am 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. |
||||||||
|
Title: Re: HARD: GREEDY PIRATES Post by rmsgrey on May 25th, 2004, 8:28am on 05/24/04 at 10:24:25, grimbal wrote:
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:
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:
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:
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. |
||||||||
|
Title: Re: HARD: GREEDY PIRATES Post by Three Hands on May 25th, 2004, 8:55am 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... |
||||||||
|
Title: Re: HARD: GREEDY PIRATES Post by rmsgrey on May 25th, 2004, 8:56am on 05/25/04 at 08:26:38, pedronunezmd wrote:
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. |
||||||||
|
Title: Re: HARD: GREEDY PIRATES Post by rmsgrey on May 25th, 2004, 8:59am on 05/25/04 at 08:55:12, Three Hands wrote:
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. |
||||||||
|
Title: Re: HARD: GREEDY PIRATES Post by Three Hands on May 25th, 2004, 9:02am 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... |
||||||||
|
Title: Re: HARD: GREEDY PIRATES Post by pedronunezmd on May 25th, 2004, 10:41am on 05/25/04 at 03:44:49, rmsgrey wrote:
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. |
||||||||
|
Title: Re: HARD: GREEDY PIRATES Post by grimbal on May 25th, 2004, 2:44pm on 05/25/04 at 08:28:34, rmsgrey wrote:
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. |
||||||||
|
Title: Re: HARD: GREEDY PIRATES Post by pedronunezmd on May 25th, 2004, 7:01pm 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:
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. |
||||||||
|
Title: Re: HARD: GREEDY PIRATES Post by rmsgrey on May 26th, 2004, 3:29am 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. |
||||||||
|
Title: Re: HARD: GREEDY PIRATES Post by grimbal on May 26th, 2004, 6:03am 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. |
||||||||
|
Title: Re: HARD: GREEDY PIRATES Post by pedronunezmd on May 26th, 2004, 10:24am 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. |
||||||||
|
Title: Re: HARD: GREEDY PIRATES Post by pedronunezmd on May 26th, 2004, 2:47pm Lightning flashed overhead, illuminating the sweat that was now beading on Malo's forehead. Why is Greybeard hesitating?, thought Malo to himself. As the #3 pirate in the group, he had seen many pirates die in this ritual, making proposals to divide the gold in such a way that would ensure they lived, but failing miserably. On this 4-pirate ship, Malo had always voted the #4 pirate to die. Sure he never got any gold, but he always got to live. And of course, they always had to head to the nearest port to get a new #4 pirate to join them. But he had drawn the wrath of the the captain, Greybeard, and his first mate, just the day before. Those two always got 500 gold if someone died. And since those blood-thirsty bastards didn't really care who died, tonight they had chosen Malo as the one to walk the plank. So Malo trusted the new pirate#4 and his crazy idea for a proposal. As expected, #2 rejected the offer, and #4 had supported the offer. But he needed one more vote to live. He told me it would work, that damn new pirate! Why is Greybeard still thinking? Had he stated the offer right? "I propose #4 and #3 each get 498 gold, #2 gets none, and #1 gets 4 gold, but if #1 dies, we will toss his 4 gold coins into the ocean along with him." Yes, I did get it right. So why is #1 hesitating? It was then that Greybeard began to speak. "If I get thrown overboard, then what guarantee would I have that my 4 coins would get thrown overboard with me? Obviously none, since you all are infinitely greedy. You will probably just keep the 4 coins and divide them amongst yourselves equally! Therefore I would have to offer someone more than 500 coins for me to live... This offer is worthless to me!" Damn that fourth pirate! I'll slit his throat now! Malo began to slowly unsheath his dagger... "Hold on, my captain Greybeard," said the new pirate. "The four coins will indeed go with you into the ocean if you die." Malo stopped moving, his hand held steady on the hilt of the now half-unsheathed blade. He could feel his pulse in his throat. Greybeard eyed the young new pirate cautiously. "Here, Greybeard, hold these 4 coins now in your pocket. If we reject your offer, you can throw yourself into the icey waters with the coins on you. Maybe then you would be able to buy a nice drink of ale once you are in Davey Jones' Locker." Malo could see the blood-thirst drain from Greybeard's eyes, and he quietly slid the dagger away and smiled. |
||||||||
|
Title: Re: HARD: GREEDY PIRATES Post by Icarus on May 26th, 2004, 7:14pm Concerning the "additional rounds" variation: It was always my idea (and I believe the idea of James, who proposed it) that all coins were on the table. No distribution would take place until a round ended with a valid proposal. Grimbal is wrong about this ever resulting in an infinite reccursion. A pirate must die in every invalid round (otherwise all pirates would be able to take their share). Since there are only a finite number of pirates... In fact, it is extremely doubtful that a 2nd round would ever occur. The possibility of future rounds is only needed for their effect on decisions in the first and only actual round. pedronunezmd's concept of requiring proposals to cover all eventualities is also interesting, and can even influence the multiple rounds scenario. There is no restriction in that scenario on what sort of proposal is made, so it may be that a proposal outlining multiple cases would produce a better result for higher-numbered pirates than the simple "you get this; you get that" proposals considered so far. A third possibility - far-fetched, but so is the whole puzzle: The pirates agree that if final proposal is invalid, they will all die (by means of some contrivance, to prevent cheating). This makes it in everyone's favor to ensure a valid outcome. Without giving it a full analysis to be sure, it seems likely to me that this would result in no one other than #1 ever proposing any money for him (certainly #2 wouldn't dare). For if the current proposal at the start of #1's turn assigns any money to him, he can propose whatever he chooses and everyone else must vote for it to assure their own survival. (And if he were feeling suicidal, he could propose giving money to some already dead pirate, thereby taking everyone else out with him!) |
||||||||
|
Title: Re: HARD: GREEDY PIRATES Post by pedronunezmd on May 26th, 2004, 8:06pm Quote:
I believe it is impossible for an actual second round to ever occur, as long as there are no more than 45 pirates to begin with. (Someone said up to 1000 pirates even.) I therefore agree that the possibility of future rounds is only needed for their effect on decisions in the first and only actual round. However, the second round is only a more complex way of saying that, if #1 dies (which he won't), then the money will be distributed in a certain fashion, which for any given number of leftover pirates, will always be the same. For example, in the 4-pirate case, the theoretical second round is basically saying "split the leftover money equally amongst the 2 lowest numbered pirates". In the 3-pirate case, the theoretical second round is basically saying "kill the highest numbered pirate." Since the original statement of the expanded 5-pirate case puzzle does not specify how "leftover" money is split, but only that the pirates themselves are making the proposals, it stands to reason that any proposal should also include, as part of the proposal, what happens should a pirate who is assigned money is killed, if that proposal were to be the final accepted proposal. Any pirate could have that method be any way he deems most likely to prove favorable for himself when making his proposal. He might say that the leftover coins are thrown into the ocean, or split evenly amongst all surviving pirates, or split in a second round following the same rules, or all go to a certain pirate, or randomly be given to either one pirate or another, etc. The key is that whatever is proposed, the expectations for each of the pirates can always be calculated, as the pirates are infinitely smart and can do all the calculations. And therefore pirate #1 will always be able to propose something to ensure his survival, and therefore no need for the actual contingency to ever take place. |
||||||||
|
Title: Re: HARD: GREEDY PIRATES Post by rmsgrey on May 27th, 2004, 4:11am For any contingent proposal, there are only two possibilities: some later proposal gets accepted (overriding it), or all subsequent proposals are rejected, in which case only the contingency in which all subsequent pirates die needs to be considered. Therefore any contingent proposal is entirely equivalent to a non-contingent proposal which assigns nothing to any lower-numbered pirate. The only question becomes one of whether you are allowed to assign gold to be thrown overboard (ruled out by my rule A). If yes, then a new class of solutions becomes available. If no, then previous analysis stands. Re-reading the thread, while disposing of gold has been mentioned as a possibility, no-one has previously suggested it as a serious option. Since James Fingas put most work into the existing solutions, I feel his formulation deserves some respect, but if alternative versions lead to more interesting results, then I agree they should be explored. |
||||||||
|
Title: Re: HARD: GREEDY PIRATES Post by pedronunezmd on Jun 2nd, 2004, 4:45pm Well, since everyone seems to think that the only way to deal with coins assigned to dead pirates have to be reassigned using a second round, then I'll agree that the 4-pirate case must end with [500,500,0,X]. |
||||||||
|
Title: Re: HARD: GREEDY PIRATES Post by pedronunezmd on Jun 21st, 2004, 5:09pm Quote:
Actually, I revoke my last statement. I no longer feel the statement is valid that "whoever did the most work first is right". ;) The riddle does not state how money assigned to dead pirates gets distributed, therefore it is more reasonable (to me) that the pirates themselves would make this determination as part of each pirate's plan for how to distribute the money. |
||||||||
|
Title: Re: HARD: GREEDY PIRATES Post by mattian on Jul 7th, 2004, 6:56am Given pirates (P1, P2, P3, P4, P5, ..., Pn): Let n be the number of pirates (in this case n=5) where P1 makes the first proposal P1 would propose the following distribution: P1: 997 P2: 0 P3: 1 P4: 2 P5: 0 OR P1: 997 P2: 0 P3: 1 P4: 0 P5: 2 Proof: Let A = P5, B = P4, C = P3, D = P2, E = P1, F = P0, G = etc. where n = 1: A proposes: A: 1000 - accepted: no contest where n = 2: B proposes: A: 1000 - rejected: blood B: 0 - accepted: survival (in vane) where n = 3: C proposes: A: 0 - rejected: greed B: 0 - accepted: survival C: 1000 - accepted: greed where n = 4: D proposes: A: 1 - accepted: greed (would reject 0 in favour blood) B: 1 - accepted: greed (would reject 0 in favour blood) C: 0 - rejected: greed/blood D: 998 - accepted: greed where n = 5: E proposes: A: 2 (or 0) - accepted: greed (or rejected: greed/blood) B: 0 (or 2) - rejected: greed/blood (or accepted: greed) C: 1 - accepted: greed D: 0 - rejected: greed/blood E: 997 - accepted: greed where n = 6: F proposes: A: 2 (or 0) - accepted: greed (rejected: greed/blood) B: 0 (or 2) - rejected: greed/blood (accepted: greed) C: 2 - accepted: greed D: 1 - accepted: greed E: 0 - rejected: greed F: 995 - accepted: greed Note in the case of n = 6, F does not need to offer any more than 2 to A or B because they would have to accept it in fear that E switches the offering around. |
||||||||
|
Title: Re: HARD: GREEDY PIRATES Post by Grimbal on Jul 7th, 2004, 7:59am The reason this thread gets so long is that we are now looking for a modified problem where even after a proposal was accepted, the next pirates still can make their proposals. In the original problem, where the first accepted proposal settles the matter, you are right. |
||||||||
|
Title: Re: HARD: GREEDY PIRATES Post by mattian on Jul 8th, 2004, 6:24am Noted. Apologies. |
||||||||
|
Title: Re: HARD: GREEDY PIRATES Post by rmsgrey on Jul 8th, 2004, 12:36pm For the original problem, once the number of pirates passes 5, you need to consider what's known about the means by which pirate 5 (using the numbering convention used through most of the thread whereby the first pirate to speak has the highest number - avoiding renumbering when translating conditional cases) assigns gold - if pirate 5 has an equal chance of assigning the 2 gold to either pirate 1 or 2, then they both expect to get 1, and need 2 to buy off. If pirate 5 is known to favour one or the other, then the one least likely to get assigned gold by pirate 5 can be bought off more cheaply by being assigned 1... A complete answer to the n pirate case of the original problem would then require consideration of the various possible distributions the pirates could use in their assignments. |
||||||||
|
Title: Re: HARD: GREEDY PIRATES Post by mattian on Jul 9th, 2004, 10:11am I think it is safest to make no assumption about which of pirates 1 and 2 pirate 5 favours. Thus his assignment of 2 gold coins to one rather than to the other becomes arbitrary. This was the bases for my explanation at the bottom of n = 6 (where n is the number of pirates) - simply that given the choice between 2 gold coins and the potential for 2 or 0, any greedy person will take the sure thing and go for the definite 2 offered by pirate 6. Where it becomes hairy is if P6 (pirate 6) offers 1 gold coin each to P1 and P2. This is difficult because it is difficult to assess whether P1 and P2 would accept the safe offer of one over the risky potential for 2 to be offered by P5. Assuming we knew they would accept the safe 1 gold coin, P6 could then decide to offer only 1 gold coin to only one of them and keep the other one for himself pushing his total up from 995 to 996. If we knew that they would take the risk for the potentially higher booty (2 gold coins) - which seems likely of greedy folk - my original solution for P6 stands - 995 gold coins kept and 2 to P1 or P2. P7 is where things get really furry, because those same questions remain about how the pirates will make their decisions. This is my theory for n = 7. P7 proposes: P1: 2 (or 0) - accepted: greed (rejected: greed/blood) P2: 0 (or 2) - rejected: greed/blood (accepted: greed) P3: 0 - rejected: greed P4: 2 - accepted: greed P5: 1 - accepted: greed P6: 0 - rejected: greed P7: 995 - accepted: greed Although I've identified certain patterns in the way these solutions have panned out, I can't say that I have a generic solution for Pn. |
||||||||
|
Title: Re: HARD: GREEDY PIRATES Post by mattian on Jul 9th, 2004, 11:01am I suppose we could start off by identifying the patterns we do know. In general for Pn (where n > 2) P(n-1) will always reject. Until of course, the gold is so dispersed among the pirates as bribes that the bribes begin to outweigh the Pn's earnings. It would be interesting to see what happens as the bribes get higher and higher. I'm sure there are key thresholds beyond which any patterns identified in n=7 will break down - as a particular pirate Pi's bribes P(i-1) with more money than P(i-1) could make by making a proposal of his own. This of course would all vary if we varied the total number of coins too. Now that I think of it, the generic function describing Pn's proposal surrounding x gold coins, has to be fairly complex. Perhaps by examining a smaller x, and a larger n, we might begin to see the behavioural pattern that would ensue. For example: let n = 8 and x = 5. for n = 2, P2 proposes: P1 : 5 rejects - bloodthirsty P2 : 0 accepts - self for n = 3, P3 proposes: P1 : 0 rejects - greedy P2 : 0 accepts - survival P3 : 5 accepts - self for n = 4, P4 proposes: P1 : 1 accepts - greedy P2 : 1 accepts - greedy P3 : 0 rejects - greedy P4 : 3 accepts - self for n = 5, P5 proposes: P1 : 0(2) rejects - greedy P2 : 2(0) accepts - greedy P3 : 1 accepts - greedy P4 : 0 rejects - greedy P5 : 2 accepts - self for n = 6, P6 proposes: P1 : 0(2) rejects - greedy P2 : 2(0) accepts - greedy P3 : 2 accepts - greedy P4 : 1 accepts - greedy P5 : 0 rejects - greedy P6 : 0 accepts - self for n = 7, P7 proposes: P1 : 0 rejects - greedy P2 : 0 rejects - greedy P3 : 0 rejects - greedy P4 : 2 accepts - greedy P5 : 1 accepts - greedy P6 : 1 accepts - greedy - here P6's bribe is better than his own proposal P7 : 1 accepts - self for n = 8, P8 proposes P1 : 0 rejects P2 : 0 rejects - greedy P3 : 1 accepts - greedy P4 : 0 rejects - greedy P5 : 2 accepts - greedy P6 : 2 accepts - greedy P7 : 2 accepts - self P8 : 0 accepts - self P8 doesn't have enough gold to survive, but again that will play an interesting role in P9's proposal, with P9 knowing (as P3 knew of P2) that he will have P8's vote regardless of his offer. This does give some indication as to the generic formula for Pn. The number of votes (V) that Pn requires to survive is V = [floor(n/2)+1]. And Pi's vote can be bought for a price (G) of G = [(P(n-1)'s offer to Pi)+1]. Thus the V lowest values for G are the offers made by Pn. By assigning a value of -1 to pirates who are doomed to die (such as P2 and P8 in this example), the formula for G still holds. Finally, the logical description of the case which exists between P1 and P2 for n = 5 and n = 6, can be explained as follows. Where only one vote is needed from one of many pirates with the same bribe requirements, the bribe for that one pirate will be (G - 1). That pirate pays 1 gold coin for security. Thoughts? |
||||||||
|
Title: Re: HARD: GREEDY PIRATES Post by rmsgrey on Jul 12th, 2004, 8:38am on 07/09/04 at 11:01:01, mattian wrote:
I get P6's proposal as: P1: 0/2/2 (loses to expected 1 from P5) P2: 2/2/0 (beats expected 1 from P5) P3: 2/0/2 (beats certain 1 from P5) P4: 1 (beats 0 from P5) P5: 0 (loses to 2 from P5) P6: 0 (self) P7 then needs to bribe three of the others - P5, P6 at 1 each and one of the other 4 at 2 (beating an expected 4/3 for P1, P2, P3 or certain 1 for P4) giving: P1: 2/0/0/0 P2: 0/2/0/0 P3: 0/0/2/0 P4: 0/0/0/2 P5: 1 P6: 1 P7: 1 meaning P8, needing 4 votes can beat an expected 1/2 each for P1-4 easily: P1: 1 P2: 1 P3: 1 P4: 1 P5: 0 P6: 0 P7: 0 P8: 1 So P9 (needing 4 votes) gives: P1: 2/0/0/0/0 P2: 0/2/0/0/0 P3: 0/0/2/0/0 P4: 0/0/0/2/0 P5: 1 P6: 1 P7: 1 P8: 0/0/0/0/2 P9: 0 PA (using letters for numbers higher than 9 to keep things as a single digit), chasing 5 beats 2/5 or 0 for 5 of 6: P1: 1/1/1/1/1/0 P2: 1/1/1/1/0/1 P3: 1/1/1/0/1/1 P4: 1/1/0/1/1/1 P5: 0 P6: 0 P7: 0 P8: 1/0/1/1/1/1 P9: 0/1/1/1/1/1 PA: 0 PB (11) is then also looking for 5 votes, and has to beat 0 or 5/6 in each case so gives one each to any 5 (no I'm not going to list the 252 possible ways fo choosing 5 of 10) of the others, giving the other 10 an expected value of 1/2 each. PC (12) needs to bribe 6 people with 5 coins, so is doomed. PD (13) also needs to bribe 6, but has 5 coins and survival as bribes. P14 is doomed, and P15 needs to find 7 bribes with 5 coins and 1 survival. P16 similarly faces needing 8 with 5 coins and 2 survivals. P17 can scrape the required 8 together with 5 coins and P14, P15 and P16's survival votes. P18 is hopelessly short of the target 9 votes, and it's not until P25 scrapes together 7 survival votes that the next person survives. The pattern should be obvious from there... |
||||||||
|
Title: Re: HARD: GREEDY PIRATES Post by mattian on Jul 12th, 2004, 9:02am RMS: My perspective on P8's proposal is based on the assumption that the greedy pirate will take his chances and forfeit 1 gold coin for a shot at 2 gold coins, even if he risks getting none. If the alternative assumption is made, then your solution is accurate and interesting. Perhaps my choice of 5 coins in the hypothesis was a bad choice because the pirates ran out of gold before the point I was trying to make could be sufficiently demonstrated - ie. that rewards from bribes would at some point begin to outweigh the benefits of making a proposal. Your projection however, does illustrate this principle with the survival concept rather than the bribes, so I suppose it's done. :-) Matt. |
||||||||
|
Title: Re: HARD: GREEDY PIRATES Post by rmsgrey on Jul 12th, 2004, 3:07pm I hadn't actually considered variant utility functions (the amount of value a pirate puts on a given amount of gold) - I was implicitly assuming a linear utility function (2 pieces of gold is worth twice as much as 1 piece) with no risk bias (a chance of getting gold which averages to an expected 1 piece is the same as a guaranteed single piece). If the pirates each assume that their preferred outcome will occur (given that they know what ends the others pursue, so P2 doesn't expect to survive if he has to make a proposal) then bribes start going up rather faster (if a chance of getting a corpse and 2 coins outweighs the certainty of 2 coins and no more corpses, then 3 coins are needed for a successful bribe). In fact, P6 (in the 5 coin case) has to offer: P1: 3/0/0 P2: 0/3/0 P3: 2 P4: 1 P5: 0/0/3 P6: -1 P7 then faces (competing against the same P5 offer): P1: 0 P2: 0 P3: 2 P4: 1 P5: 0 P6: 0 P7: 2 P8 has it easy: P1: 1 P2: 1 P3: 0 P4: 0 P5: 1 P6: 1 P7: 0 P8: 1 P9 barely survives: P1: 2/0/0/0/0 P2: 0/2/0/0/0 P3: 1 P4: 1 P5: 0/0/2/0/0 P6: 0/0/0/2/0 P7: 1 P8: 0/0/0/0/2 P9: 0 P10 can't make it, nor can P11 or P12, but P13 (luckily!) can give 2 gold each to two of P3, P4 and P7, and the remaining 1 to P9. For higher numbers, any successful offer will always have at least 5 pirates with no chance of gold - those with a chance of gold at the next lower successful offer and those making survival votes At the other extreme, if pirates prefer birds in hand to those in metaphorical bushes, bribes are much cheaper - for instance, P6 offers 1 each to P1, P2 and P4... As yet another possibility, you could have 2 certain coins outweighing 2 possible coins and any number of corpses, but two possible coins outweighing any lesser number of certain coins, in which case P6 still can give 2 coins to any 2 of P1, P2 and P3 - rather than automatically giving 2 to P3. P7 still survives, but has a free choice among P1, P2, P3 and P4 for the 2 coin bribe. P8 is then facing a price of 2 coins per bribe, which also sinks P9 and P10 - P11 survives, as does P15 (1 coin each to P8, P9, P10, 2 to one of P1-7 or P11and 3 survival votes). The interesting features of this solution are that there is a constantly growing list of pirates requiring 2 coins to bribe (until someone gets at least 5 survival votes - at which point the 2's get nothing from the next survivor, meaning a list of 1s develops instead), and that P13 dies for once... |
||||||||
|
Title: Re: HARD: GREEDY PIRATES Post by mattian on Jul 13th, 2004, 5:38am RMS: I don't understand your P7 - everything else makes sense and I agree with your reasoning. I wasn't consistent in my assumptions - because I assumed that pirates would risk loss in the face of potential gain and did not take into consideration the prospect of blood as a reason for such a risk. Thus, I agree with your offer of 3 to P1 or P2 to prevent any interest in blood over certain gold. But P7 confuses me in your result. Is he doomed or do you claim that he will survive with his proposal? |
||||||||
|
Title: Re: HARD: GREEDY PIRATES Post by Three Hands on Jul 13th, 2004, 7:43am I believe that it is to do with the number of votes that P6 and P7 need to secure is, in fact, the same, but P7 gets a bonus in that P6 will vote for P7 regardless of what the offer is. So, while P6 does not have enough treasure to bribe 3 pirates with, P7, facing the same competition from P5's expected offer (as P6 will not survive), only needs to bribe 2 pirates, as he has the third required vote secured from P6. Hence, P7 bribes the two pirates who are cheapest to bribe (P3 and P4), and takes the remaining gold for himself. So yes, P7 does survive. |
||||||||
|
Title: Re: HARD: GREEDY PIRATES Post by mattian on Jul 13th, 2004, 7:49am Right. Got it, I was looking at P7 as though P6 would survive for n=6. P3 and P4 won't need a better offer from P7 because they won't win the vote on P6's proposal. Quite right. |
||||||||
|
Title: Re: HARD: GREEDY PIRATES Post by daniducci on Aug 16th, 2004, 2:42pm I agree with Icarus that Pirate 5 can get away with 999 coins. I think the proposals would break down as follows: If it makes it to Pirate 1, Pirate 1 takes 1000 and accepts the proposal. If it makes it to Pirate 2, even if he proposes that Pirate 1 gets all 1000 and Pirate 2 gets nothing, Pirate 1 will reject the proposal because he is bloodthirsty and would rather take the money and see Pirate 2 die. Pirate 2 alone is not a majority, so Pirate 2 dies if it gets to him. So Pirate 2 has incentive to make sure it doesn't make it to his turn. If it makes it to Pirate 3, 2 is going to approve the proposal regardless just to stay alive. So Pirate 3 proposes 1000 for himself, 0 for 2, and a fun killing of Pirate 1. So Pirate 1 doesn't want Pirate 3 to make a proposal. If it makes it to Pirate 4, 3 has no reason to ever agree, since he gets all the coinage if the proposal is rejected. So 4 needs to convince both 1 and 2. Pirate 1 doesn't want Pirate 3 to make a proposal, since it results in Pirate 1's death, so he will agree with Pirate 4 regardless. Pirate 2 lives in Pirate 3's proposal, so Pirate 4 needs to offer Pirate 2 a gold coin to buy his vote. So, Pirate 4 proposes 999 for himself, 1 for 2, 0 for 1, and let's kill 3. So Pirate 3 doesn't want Pirate 4 to make a proposal. Therefore he will agree with 5 irregardless. So Pirate 5 only needs to convince one other pirate. Pirate 4 has no incentive to agree, since he will make 999 in his own proposal. Pirate 2 will only agree if offered 2 gold. Pirate 1 will get 0 in Pirate 4's proposal, so his vote only costs a single coin (or a pack of cigarettes, if a Detroit Democrat ;) ). So Pirate 5 proposes 999 for himself, 1 for Pirate 1, 0 for Pirate 3, and a dual killing of both pirates 2 and 4. |
||||||||
|
Title: Re: HARD: GREEDY PIRATES Post by rmsgrey on Aug 17th, 2004, 6:14am If you're allowed to propose killing other pirates, then, yes, pirate 5 can get away with 999 gold, as can pirates 6 and 7. Pirate 8 starts facing ambiguities though as 7 could offer his extra 1 gold to pirate 2 and kill 4, or offer it to 4 and kill 2. Pirate 8's offer will depend on what's known about how 2 and 4 weigh the chance of 1 gold against the chance of death. If guaranteeing survival outweighs all other considerations, then pirate 8 can get all the gold, killing 1,5 and 7. Pirate 9 then gets 999, giving the extra to any of 2,3,4,6 and killing 8 and the other three, in turn giving 10 the lot, 11 999, 12 1000, etc. * !! x0* 01x* 1x0x* x010x* 0?x?0x* x000x0x* 0???0?0x* x000x0x0x* |
||||||||
|
Title: Re: HARD: GREEDY PIRATES Post by daniducci on Aug 17th, 2004, 1:00pm Frankly, if I'm an infinitely intelligent pirate, then I would definitely stop inviting all of these additional pirates over to join the game. Especially when they didn't bring any new gold to the table. Stupid cheap pirates. ;D |
||||||||
|
Title: Re: HARD: GREEDY PIRATES Post by rmsgrey on Aug 18th, 2004, 5:00am It depends on precisely which system you're running - if you set it up right, then you get the same amount of gold, but a lot more corpses by inviting extra pirates - provided you get to pick your position in the order... |
||||||||
|
Title: Re: HARD: GREEDY PIRATES Post by ThyGod on Oct 13th, 2004, 9:34am #5 should propose, assuming that the pirates survival>greed>bloodtirst, that he gets 998 gold, number 2 gets 2. #4 will agree, b/c otherwise, next round, on his turn, #3 will disagree, b/c then, on #3s turn, he will propose 999 to himself and 1 to number 2, and number 1 will will always disagree, since he gets the money eventually and number 4 will die. #3 will not agree, for the reason listed above. #2 will agree b/c this way, he gets more gold than if #3 gave his proposal. #1 will not agree. #5 will obviously agree with himself. I think this is the optimal solution. :D |
||||||||
|
Title: Re: HARD: GREEDY PIRATES Post by rmsgrey on Oct 13th, 2004, 12:23pm Were I pirate #4, I would vote against ThyGod's proposal - I plan on offering pirates #1 and #2 1 gold each and taking 998 for myself - I expect them to prefer that offer to #3's expected offer of 1000 for himself and nothing for anyone else - which he expects #2 to prefer to letting #1 kill him and take all the gold anyway. This has been covered on the first page of this thread. Since then, some of us have been discussing an extended version where proposals are only accepted provisionally, until the surviving pirate of lowest number has had his proposal accepted. |
||||||||
|
Title: Re: HARD: GREEDY PIRATES Post by vicki on Nov 29th, 2004, 10:39pm Hey I thought of something similar ... an optimized solution is: 5 proposes 332 coins for himself 334 each of any two of the rest four Such that he along with two others would vote for it (If he is not allowed to vote then he would propose a division of 250 among each and zero for any one pirate and that would be the best possible division which will get 3 votes out of four.) |
||||||||
|
Title: Re: HARD: GREEDY PIRATES Post by rmsgrey on Nov 30th, 2004, 9:20am To which problem do you claim this to be an optimised solution? If the original, then pirate 5 can get more than 332. If the revised version, where proposals are only accepted provisionally until pirate 1 has had his say (with subsequent rounds of proposals if there's any gold left over), then I doubt your solution is correct because pirates 1 and 2 each stand to gain 500 gold if 5 dies, so 5's proposal must give pirate 3 a chance of ending up with some money (and pirate 4 a chance of survival) |
||||||||
|
Title: Re: HARD: GREEDY PIRATES Post by vicky on Dec 1st, 2004, 12:55am clarify some points: 1. Whats majority? 3 out of 5 or 2 out of reaming 4 (one excluded is the one who proposes) or 3 out of remaining four? 2. The above solution for original problem not the provisional one. |
||||||||
|
Title: Re: HARD: GREEDY PIRATES Post by rmsgrey on Dec 1st, 2004, 10:05am The "majority" most people seem to accept is: 1 pirate has to vote for his own proposal in order for it to pass. With 2 pirates, both have to vote for the proposal in order for it to pass. With 3 pirates, 2 have to vote for the proposal in order for it to pass. With 4 pirates, 3 have to vote for the proposal in order for it to pass. With 5 pirates, 3 have to vote for the proposal in order for it to pass. In the original problem, if pirate 5 were to propose 334 each to pirates 3 and 4, and the remaining 332 for himself, pirates 1, 2 and 4 would all vote him down because pirate 4 could then propose to give 1 each to pirates 1 and 2, nothing to pirate 3, and take the remaining 998 himself, leaving all 3 of them better off than if they'd accepted pirate 5's proposal. Even if pirate 4 proposed to take all the gold himself (and got accepted), pirates 1 and 2 would still be better off than under 5's proposal because, while they'd still not have any gold, they would have got to watch pirate 5 drown. To work out what the actual solution is, it may help to look at what happens with fewer pirates to start with - 2 pirates is easy, 3 may take a little thought, and if you can get 4, 5 should follow easily. |
||||||||
|
Title: Re: HARD: GREEDY PIRATES Post by vicki on Dec 2nd, 2004, 12:19am Ok ... Lets move forward then ... what if it is a deadlock and each one gives a proposal that majority accepts?? |
||||||||
|
Title: Re: HARD: GREEDY PIRATES Post by rmsgrey on Dec 2nd, 2004, 8:06am The conditions for the original version are: 1) Each pirate values survival over any amount of gold, gold over any number of corpses, and seeing other pirates die above any unlisted considerations. 2) There are 1000 standardised gold pieces to be divided among 5 pirates. 3) Pirate 5 makes the first proposal. If he is rejeted, pirate 4 has a turn, then pirate 3, pirate 2 and finally pirate 1 who only gets to make a proposal if everyone else is executed. 4) A proposal consists of an ordered list of non-negative integers, one for each surviving pirate, summing to 1000. 5) A proposal is accepted if a strict majority of the surviving pirates vote for it, and rejected otherwise. 6) If a proposal is rejected, the proposing pirate is executed. 7) If a proposal is accepted, it is enacted immediately, each pirate recieving the appropriate quantity of gold (this condition is changed for the harder version) 8) All pirates know all these conditions, and are perfect reasoners, who do whatever gives them the highest expected value. For the extension, 7) becomes: 7) If a proposal is accepted, it becomes the "current proposal" and the nesxt pirate takes their turn. Once all pirates have taken their turn, the current proposal is enacted. Any ownerless gold must then be shared out by this same process. In neither situation does a deadlock arise (except in the impossible situation where the last surviving pirate votes against his own proposal, throws himself overboard and the 1000 gold is left ownerless) |
||||||||
|
Title: Re: HARD: GREEDY PIRATES Post by Icarus on Dec 2nd, 2004, 3:30pm on 12/02/04 at 08:06:46, rmsgrey wrote:
I didn't realize that it had been established that the 2nd round was only for leftover gold. There are other possibilities as well. There is also a question of what to do when two possible proposals are equally favorable under the conditions described. I believe this is being analyzed under the idea that the Pirates pick one at random. I have decided (seeing as I came up with the variation in the first place) that I will offer other versions as separate puzzles in another thread (something I wish now I had done for the variation in first place), and leave this thread for the "leftover gold is distributed/random picks between equal positions" version. |
||||||||
|
Title: Re: HARD: GREEDY PIRATES Post by dragomanjk on Mar 17th, 2006, 2:41am The only way I can think of 5 getting 999 gold is for an infinitely smart pirate to not know everything that will happen. P1 will kill P2 for lack of 'majority'. He then thinks he can say no to everyone and get all the money, greed clouds the mind. P2 knows that if it gets down to it he will die so he will vote for 3 no matter what. P3 gets P2's vote b/c he wants to live and so P3 gets all 1,000 gold. P4 gives P2 one piece, but it doesn't make a difference, he can't get P1's or P3's vote b/c they believe they will get 1,000. P5 gets P4's vote b/c P4 is going to die. P2 gets one piece of gold. P5 gets the 999. Lets say P1 and P2 split if it gets down to it, 500 each. P3 has to offer one of them more than 500 to get their vote. Giving only 500 will get him killed as the killing is seen as more money. P1=501/P3=499 P4 really has no option. he would have to offer each one more money and that's impossible. P4's only option is to try to convice P2 he's not getting anything if he passes this offer up and then give him a piece, and give P3 500 as well. P2=1/P3=500/P4=499 P5 must now convince P1 that he will be getting nothing if passes this offer and that P2 will only be getting 1. So he gives P1=1/P2=2/P5=997. |
||||||||
|
Title: Re: HARD: GREEDY PIRATES Post by rmsgrey on Mar 17th, 2006, 7:34am on 03/17/06 at 02:41:26, dragomanjk wrote:
I'm not sure where your analysis is coming from, but it doesn't seem to work under the standard assumptions. If there are three pirates, P2 will vote for P3 through survival, so P3 gets everything. This means that P1 will get nothing if he lets it get down to 3 pirates, and should know that (if we can figure it out, so can he) so he'd vote for anything P4 offers that gives him any gold. So would P2 for the same reason, so P4 would offer 1,1,0,998... I'll let you figure out what P5 would offer for yourself. |
||||||||
|
Title: Re: HARD: GREEDY PIRATES Post by dragomanjk on Mar 17th, 2006, 10:35am on 03/17/06 at 07:34:56, rmsgrey wrote:
I realize that, but unless it happens that way, there is no other way to get 999 then like Icarus says should be possible and the riddle is solved at 997 for P5. |
||||||||
|
Title: Re: HARD: GREEDY PIRATES Post by rmsgrey on Mar 17th, 2006, 11:12am on 03/17/06 at 10:35:51, dragomanjk wrote:
There is no way to give P5 999 if proposals solely consist of division of money in 1 gold increments. What Icarus had in mind was to allow proposals to include throwing people overboard as well - so, for instance, in the three pirate case, P3 suggests throwing P1 overboard and keeping all the gold for himself, and P2 will agree to avoid getting killed by P1. This solution avoids the situation with very large numbers of pirates where some pirates just can't buy enough votes (though survivial votes will build up until you have enough at a higher number of pirates to make up the shortfall) but it does roughly halve the size of the crew each time (each proposal either buys a given pirate's vote, or throws that pirate overboard) |
||||||||
|
Title: Re: HARD: GREEDY PIRATES Post by Icarus on Mar 17th, 2006, 3:06pm Yes. If pirates are allowed to make any proposal which will be acted upon if agreed to, then pirates can buy votes with the life of the voter, not just with money. |
||||||||
|
Title: Re: HARD: GREEDY PIRATES Post by LaCiTy on Sep 21st, 2006, 8:53am Solution I didn't read all of your considerations, but it looks like the goal to reach is 999 for #5 (which is easily shown maximal as 1000 doesn't fit). Nervetheless, with rather sensible backward induction, one come only to 997. This is because one can not, (a priori) share a coin between 2 pirates or more. Or else, the solution will obviously be 1000 minus 3*epsilon, with epsilon fixed to be the minimal size for which a part of a coin is still valuable. In fact, the correct answer lies between 1000 and 999, being very close to 1000. As soon as i'll reveal my point, you'll immediately see a solution, so stop reading here if you want to figure out by yourself. Knowing the answer which is 999+ is actually quite good a hint. Or maybe you can keep on reading, i'll try to act like socrates and make the reader discover by himself. There are coins right ? Many of them ! What do you do with coins ? You toss them ! That is you can introduce randomness. Still don't get it ? You can, as an illustration, suggest to give P1 1 coin with probability 1/2, which is tantamount to give him 0.5 coin ! (if he is risk neutral, or a little less if not, but still positive). To finish the problem properly, on has to be sure that a lower bound exists for the minimum non zero value one can pledge. If it is arbirarily small, things get confused and one can not apply what has been used so far without randomness in a straightaway manner. A pirate can not toss infinitely many coins which is clear given his life expectancy is finite and the speed of his moves is bounded by, say the speed of light ;D. Thus, the minimal probability he can obtain is 1/2^N, where N is the maximal number of coins he can toss. Let not assume all pirate are the same for the sake of useless complexity. We denote by epsilon1, epsilon2, epsilon3, epsilon4, epsilon5 the minimum probability they can draw. Things work the same by backward induction, it's has been shown that in the situation there are 3 pirates left, 3 can grab all the money, yielding : (0,0,1000) Knowing that, 4 needing 2 favorable votes will give strictly more to 1 and 2 : (epsilon4, epsilon4, 0, 1000 - 2*epsilon4) [He does only 1 tossing for 1 and 2, so as to respect his drawing possibilities] Now, #5 has to get 2 favorable votes. He chooses to give more (strictly) to those who would be dispriviledged by #4's proposal, that is 1 and 2. One solution is : (epsilon5, epsilon5, 0, 0, 1000-2*epsilon5) if epsilon5 > epsilon4 and (n*epsilon5, 0, epsilon5, 1000-(n+1)*epsilon5) if epsilon4 > epsilon5 and n := inf { t : t*epsilon5 > epsilon4 } Note that if epsilon5 = epsilon4, a solution is provided by (0, 2*eps, eps, 0, 1000 - 3*eps). In anycase, only epsilon4 and epsilon5 are relevant and well, if epsilon is very small, I virtually reach 1000 ! Can anyone be of better advice to #5 ? Thank you for your reading. P.S.: I am sorry if this solution was found before. But i feel quite proud of it and in need to communicate it ! |
||||||||
|
Title: Re: HARD: GREEDY PIRATES Post by Icarus on Sep 21st, 2006, 3:37pm Good idea! I believe you are the first to suggest probabilistic bribing. But I suggest you skim through the thread anyway. There is an alternative interpretation of the problem which led to some interesting discussions. |
||||||||
|
Title: Re: HARD: GREEDY PIRATES Post by rmsgrey on Sep 22nd, 2006, 11:20am I agree that it's a new and worthwhile solution. One minor quibble: I'm confident that, if the pirates are willing to trust each other to toss coins fairly, Pirate 4 would nominate the fastest surviving tosser (if the number of coin tosses is limited by life span then you can't toss for longer than the minumum of your and the potential recipient's life-spans - no self-respecting logical pirate is going to accept a proposal that will only pay him after he's dead! - therefore the difference in [epsilon]s had better arise from tossing speeds rather than life-spans) - so Pirate 5 will only have a smaller effective [epsilon] value if he's the fastest tosser - if not then he loses 3*(mini=1 to 4{[epsilon]i}; if he is, then he loses (t+1)*[epsilon]5 where t is the minimum integer for which t*[epsilon]5>mini=1 to 4{[epsilon]i} |
||||||||
|
Title: Re: HARD: GREEDY PIRATES Post by LaCiTy on Sep 23rd, 2006, 4:13pm Indeed. |
||||||||
|
Title: Re: HARD: GREEDY PIRATES Post by ThudanBlunder on Jan 8th, 2010, 10:19am What if there are a lot more pirates (say 2300) so that the bribe money runs out? |
||||||||
|
Title: Re: HARD: GREEDY PIRATES Post by SMQ on Jan 8th, 2010, 1:05pm on 01/08/10 at 10:19:15, ThudanBlunder wrote:
Using the following extension of rmsgrey's formalism to N pirates: 1) Each pirate values survival over any amount of gold, gold over any number of corpses, and seeing other pirates die above any unlisted considerations. 2) There are 1000 standardised gold pieces to be divided among N pirates. 3) Pirate N makes the first proposal. If he is rejeted, pirate N-1 has a turn, then pirate N-2, ..., and finally pirate 1 who only gets to make a proposal if everyone else is executed. 4) A proposal consists of an ordered list of non-negative integers, one for each surviving pirate, summing to 1000. 5) A proposal is accepted if a strict majority of the surviving pirates vote for it, and rejected otherwise. 6) If a proposal is rejected, the proposing pirate is executed. 7) If a proposal is accepted, it is enacted immediately, each pirate recieving the appropriate quantity of gold 8) All pirates know all these conditions, are perfect reasoners, and are risk-neutral, who do whatever gives them the highest expected value. If I've managed the induction properly, - [hide]for 5 <= N <= 1000, pirate N can make a proposal in which he receives 999 - 2 floor((N-2)/2) coins by offering 2 coins to any floor((N-2)/2) of the first N-3 pirates, 1 coin to pirate N-2, and keeping the rest. This given an expected value to each of the first N-3 pirates of (2 floor((N-2)/2)/(N-3) coins which is >= 1. [/hide] - [hide]for N = 1001, pirate 1001 can offer 2 coins to any 499 of (the first 998 pirates OR pirate 1000 (who only receives 1 coin by his best proposal)), 1 coin to pirate 999, and keep one coin himself. This gives an expected value to pirates 1-998,1000 of 998/999 coins which is < 1. [/hide] - [hide]for N = 1002, pirate 1002 can offer 1 coin to any 501 of pirates 1-998,1000 and keeping the other 499 coins for himself. [/hide] - [hide]for 1003 <= N <= 2000, pirate N can make a proposal in which he receives 1000 - floor(N/2) coins by offering 1 coin to any floor(N/2) of the first N-2 pirates and keeping the rest. [/hide] - [hide]for N = 2001, pirate 2001, can offer 1 coin to any 1000 of the first 2000 pirates, keeping none for himself. [/hide] - [hide]for N = 2002, there is no proposal pirate 2002 can make which will be accepted by 1001 pirates other than himself. [/hide] - [hide]for N = 2003, pirate 2003 can offer 1 coin to any 1000 of the first 2001 pirates, leaving nothing for pirate 2002 or himself but still receiving the needed 1002 votes. [/hide] In general: - [hide]for N > 2000, n != 1999 + 2k, there is no proposal pirate N can make which will be accepted. [/hide] - [hide]for N = 1999 + 2k, k > 0, pirate N can offer 1 coin to any 1000 of the first 1999 + 2k-1 pirates and receive the needed 1000 + 2k-1 votes. [/hide] So for 2300 pirates, [hide]pirates 2300 down through 2256 are executed. Pirate 2255 offers one coin to any 1000 of the first 2127 pirates and nothing to pirates 2128 through 2255 and his proposal is accepted. [/hide] --SMQ |
||||||||
|
Title: Re: HARD: GREEDY PIRATES Post by ThudanBlunder on Jan 9th, 2010, 10:00am SMQ, why can't 2002 rely on 2001's vote? 2001 knows he will get nothing or be executed if 2002 is executed. |
||||||||
|
Title: Re: HARD: GREEDY PIRATES Post by SMQ on Jan 9th, 2010, 10:54am If 2002 makes a proposal in which 2001 receives no gold, 2001 will prefer his own proposal (in which he still receives no gold, but gets to see 2002 executed), and so will vote against. --SMQ |
||||||||
|
Title: Re: HARD: GREEDY PIRATES Post by Bumble_Bee_Tuna on Aug 9th, 2010, 7:21am I believe that I have a better solution for the problem as originally stated. I agree with the solutions already posted if proposals are restricted only to how to distribute the treasure. However, if they're allowed to make ANY proposal, even Icarus's solution of 999 gold isn't good enough! Pirate 5 can in fact get away with taking ALL the gold, and killing ALL the other pirates. (or 3 out of 4, if ties don't pass) EDIT: I goofed, I guess #5 can't kill them all in the ties pass scenario :( I prefer using the assumption that ties pass, as it results in the most fun solution. I'll list what each pirate gets like this: aye [257, 2] where aye is what they vote, 257 is how much gold they get from the proposal (or "dead" if they're killed) and 2 is just a listing of how many pirates besides themselves they get the satisfaction of knowing die. [hide] 2 pirates: any proposal will pass. 1: nay [dead, 3] 2: aye [1000, 4] 3 pirates: pirate #1 will accept anything where he lives. Propose to kill #2 and take it all. 1: aye [0, 3] 2: nay [dead, 2] 3: aye [1000, 3] 4 pirates: pirate #2 will accept anything where he lives, but he'll also accept death if 3 other pirates die with him instead of the two he'd see in the 3 pirate scenario. Propose to kill #1, #2, and #3 and take it all. 1: nay [dead, 3] 2: aye [dead, 3] 3: nay [dead, 3] 4: aye [1000, 4] 5 pirates: Propose to kill #4 and 1 other pirate (doesn't matter which one). Assuming 1 and 3 are chosen to be spared: 1: aye [0, 3] 2: nay [dead, 3] 3: aye [0, 3] 4: nay [dead, 3] 5: aye [1000, 4] It's almost the same if a true majority is needed to pass instead of a tie: 2 pirates: Anything proposed fails. 1: nay [1000, 4] 2: aye [dead, 3] 3 pirates: #3 needs to win #2's vote by letting him live. Kill #1, take 1000. 1: nay [dead, 2] 2: aye [0, 3] 3: aye [1000, 3] 4 pirates: #4 needs to win both #1 and #2 over. He can let #1 live, but he'll have to give #2 1 gold. 3 gets killed. 1: aye [0, 2] 2: aye [1, 2] 3: nay [dead, 1] 4: aye [1000, 2] 5 pirates: Killing #4 and #2 is enough to satisfy #3, who would otherwise only die alongside 1 pirate instead of 2. And killing 2, 3, and 4 is enough to satisfy #1, who would otherwise only get to see 2 pirates die instead of 3. Propose to kill 2, 3, and 4 and take all 1000. 1: aye [0, 3] 2: nay [dead, 2] 3: aye [dead, 2] 4: nay [dead, 2] 5: aye [1000, 3][/hide] Of course, other assumptions could be thrown into the mix (if probabilistic stuff is allowed, now just a miniscule chance of survival is enough to convince a fellow voter instead of a 100% chance of survival. Or what if you could propose "I'll kill pirate #2...in 10 minutes". Would pirate #2 value that over being killed immediately? Then you have another silly avenue for making proposals. But those kinds of assumptions sort of kill the riddle. |
||||||||
|
Title: Re: HARD: GREEDY PIRATES Post by rmsgrey on Aug 9th, 2010, 8:38am In your first scenario, I think you got #4's proposal wrong: 4 pirates: pirate #2 will accept anything where he lives, or where there's only one survivor. Propose to kill #1, #2 and #3 and take it all. 1: nay [dead, 3] 2: aye [dead, 3] 3: nay [dead, 3] 4: aye [1000, 4] making #5's proposal need the support of two other survivors. #6 then also needs to let someone live since only #4 is guaranteed death if #5 gets to bid. Your analysis of the second variant seems to hold. |
||||||||
|
Title: Re: HARD: GREEDY PIRATES Post by Bumble_Bee_Tuna on Aug 9th, 2010, 1:42pm on 08/09/10 at 08:38:01, rmsgrey wrote:
Noted, I have edited to make your correction. That's a shame, I really liked having the answer involve killing everyone :( I think if I ever tell this riddle it will be 4 pirates instead of 5. |
||||||||
|
Title: Re: HARD: GREEDY PIRATES Post by Hippo on Aug 9th, 2010, 4:13pm Just one thing ... I would rather use notation where last coordinate is minus the number of alive (other) pirates. Advantage of this notation is that it is independent on the original number of pirates. |
||||||||
|
Powered by YaBB 1 Gold - SP 1.4! Forum software copyright © 2000-2004 Yet another Bulletin Board |