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

Welcome, Guest. Please Login or Register.
Mar 29th, 2024, 7:10am

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





   


Gender: male
Posts: 115
Re: HARD: GREEDY PIRATES  
« Reply #75 on: May 26th, 2004, 2:47pm »
Quote Quote Modify Modify

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.
« Last Edit: May 26th, 2004, 6:04pm by pedronunezmd » IP Logged
Icarus
wu::riddles Moderator
Uberpuzzler
*****



Boldly going where even angels fear to tread.

   


Gender: male
Posts: 4863
Re: HARD: GREEDY PIRATES  
« Reply #76 on: May 26th, 2004, 7:14pm »
Quote Quote Modify Modify

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!)
IP Logged

"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
pedronunezmd
Junior Member
**





   


Gender: male
Posts: 115
Re: HARD: GREEDY PIRATES  
« Reply #77 on: May 26th, 2004, 8:06pm »
Quote Quote Modify Modify

Quote:
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.

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.
IP Logged
rmsgrey
Uberpuzzler
*****





134688278 134688278   rmsgrey   rmsgrey


Gender: male
Posts: 2872
Re: HARD: GREEDY PIRATES  
« Reply #78 on: May 27th, 2004, 4:11am »
Quote Quote Modify Modify

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.
IP Logged
pedronunezmd
Junior Member
**





   


Gender: male
Posts: 115
Re: HARD: GREEDY PIRATES  
« Reply #79 on: Jun 2nd, 2004, 4:45pm »
Quote Quote Modify Modify

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].
IP Logged
pedronunezmd
Junior Member
**





   


Gender: male
Posts: 115
Re: HARD: GREEDY PIRATES  
« Reply #80 on: Jun 21st, 2004, 5:09pm »
Quote Quote Modify Modify

Quote:
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].

Actually, I revoke my last statement. I no longer feel the statement is valid that "whoever did the most work first is right".
 
 Wink
 
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.
IP Logged
mattian
Senior Riddler
****






   
WWW Email

Gender: male
Posts: 404
Re: HARD: GREEDY PIRATES  
« Reply #81 on: Jul 7th, 2004, 6:56am »
Quote Quote Modify Modify

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.
IP Logged
Grimbal
wu::riddles Moderator
Uberpuzzler
*****






   


Gender: male
Posts: 7526
Re: HARD: GREEDY PIRATES  
« Reply #82 on: Jul 7th, 2004, 7:59am »
Quote Quote Modify Modify

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.
IP Logged
mattian
Senior Riddler
****






   
WWW Email

Gender: male
Posts: 404
Re: HARD: GREEDY PIRATES  
« Reply #83 on: Jul 8th, 2004, 6:24am »
Quote Quote Modify Modify

Noted. Apologies.
IP Logged
rmsgrey
Uberpuzzler
*****





134688278 134688278   rmsgrey   rmsgrey


Gender: male
Posts: 2872
Re: HARD: GREEDY PIRATES  
« Reply #84 on: Jul 8th, 2004, 12:36pm »
Quote Quote Modify Modify

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.
IP Logged
mattian
Senior Riddler
****






   
WWW Email

Gender: male
Posts: 404
Re: HARD: GREEDY PIRATES  
« Reply #85 on: Jul 9th, 2004, 10:11am »
Quote Quote Modify Modify

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.
IP Logged
mattian
Senior Riddler
****






   
WWW Email

Gender: male
Posts: 404
Re: HARD: GREEDY PIRATES  
« Reply #86 on: Jul 9th, 2004, 11:01am »
Quote Quote Modify Modify

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?
IP Logged
rmsgrey
Uberpuzzler
*****





134688278 134688278   rmsgrey   rmsgrey


Gender: male
Posts: 2872
Re: HARD: GREEDY PIRATES  
« Reply #87 on: Jul 12th, 2004, 8:38am »
Quote Quote Modify Modify

on Jul 9th, 2004, 11:01am, mattian wrote:
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

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...
IP Logged
mattian
Senior Riddler
****






   
WWW Email

Gender: male
Posts: 404
Re: HARD: GREEDY PIRATES  
« Reply #88 on: Jul 12th, 2004, 9:02am »
Quote Quote Modify Modify

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.  Smiley
 
Matt.
IP Logged
rmsgrey
Uberpuzzler
*****





134688278 134688278   rmsgrey   rmsgrey


Gender: male
Posts: 2872
Re: HARD: GREEDY PIRATES  
« Reply #89 on: Jul 12th, 2004, 3:07pm »
Quote Quote Modify Modify

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...
IP Logged
mattian
Senior Riddler
****






   
WWW Email

Gender: male
Posts: 404
Re: HARD: GREEDY PIRATES  
« Reply #90 on: Jul 13th, 2004, 5:38am »
Quote Quote Modify Modify

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?
IP Logged
Three Hands
Uberpuzzler
*****





    Reucserru+Oymai


Gender: male
Posts: 715
Re: HARD: GREEDY PIRATES  
« Reply #91 on: Jul 13th, 2004, 7:43am »
Quote Quote Modify Modify

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.
IP Logged
mattian
Senior Riddler
****






   
WWW Email

Gender: male
Posts: 404
Re: HARD: GREEDY PIRATES  
« Reply #92 on: Jul 13th, 2004, 7:49am »
Quote Quote Modify Modify

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.
IP Logged
daniducci
Guest

Email

Re: HARD: GREEDY PIRATES  
« Reply #93 on: Aug 16th, 2004, 2:42pm »
Quote Quote Modify Modify Remove Remove

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 Wink ). 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.
IP Logged
rmsgrey
Uberpuzzler
*****





134688278 134688278   rmsgrey   rmsgrey


Gender: male
Posts: 2872
Re: HARD: GREEDY PIRATES  
« Reply #94 on: Aug 17th, 2004, 6:14am »
Quote Quote Modify Modify

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*
0Huh0?0x*
x000x0x0x*
IP Logged
daniducci
Guest

Email

Re: HARD: GREEDY PIRATES  
« Reply #95 on: Aug 17th, 2004, 1:00pm »
Quote Quote Modify Modify Remove Remove

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.  Grin
IP Logged
rmsgrey
Uberpuzzler
*****





134688278 134688278   rmsgrey   rmsgrey


Gender: male
Posts: 2872
Re: HARD: GREEDY PIRATES  
« Reply #96 on: Aug 18th, 2004, 5:00am »
Quote Quote Modify Modify

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...
IP Logged
ThyGod
Newbie
*



:)

   
Email

Gender: male
Posts: 4
Re: HARD: GREEDY PIRATES  
« Reply #97 on: Oct 13th, 2004, 9:34am »
Quote Quote Modify Modify

#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. Cheesy
IP Logged
rmsgrey
Uberpuzzler
*****





134688278 134688278   rmsgrey   rmsgrey


Gender: male
Posts: 2872
Re: HARD: GREEDY PIRATES  
« Reply #98 on: Oct 13th, 2004, 12:23pm »
Quote Quote Modify Modify

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.
IP Logged
vicki
Guest

Email

Re: HARD: GREEDY PIRATES  
« Reply #99 on: Nov 29th, 2004, 10:39pm »
Quote Quote Modify Modify Remove Remove

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.)
IP Logged
Pages: 1 2 3 4 5  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print

« Previous topic | Next topic »

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