Author |
Topic: Greedy Pirates Variations (Read 1367 times) |
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender: 
Posts: 4863
|
 |
Greedy Pirates Variations
« on: Dec 2nd, 2004, 6:06pm » |
 Quote  Modify
|
These are versions of the Greedy Pirates problem that have been discussed to some extent in that thread. But the main work on this variation has centered around a probabilistic version different from those below. I have decided to list these versions so that they might receive some attention as well. They all start with the same basic premises:
A group of N (nominally 5) pirates is dividing 1000 gold pieces between them. They split the gold according to the following rules.
Each pirate is assigned a number from 1 to N. Starting with #N and going down to #1, each pirate makes a proposal of how the gold should be divided. Then all surviving pirates (including the proposer) vote whether or not to accept the proposal. The proposal must have a true majority (no ties) to be accepted. If the proposal is rejected, the proposer is immediately killed. If the proposal is accepted, it becomes the "current" proposal (any previous proposal is scrapped), and the next pirate takes his turn.
When all pirates have had their turn, the money is distributed according to the "current" proposal, assuming it doesn't assign any gold to a dead pirate (one whose proposal failed).
When the current proposal does assign gold to a dead pirate, there are 4 variations as to what happens:
(1) The gold is thrown overboard with the pirate to whom it was assigned.
(2) All pirates are killed for their poor planning.
(3) The surviving pirates proceed to spit the excess gold following the same procedure (taking turns in the same order).
(4) The current proposal is scrapped, and the process starts over again to split all the gold (with turns in the same order).
When making decisions, the pirates all follow these guidelines:
i) The first priority of each pirate is to survive.
ii) The second priority is to come out with as much gold for themselves as they can.
iii) Third, the pirates are ruthless, and would prefer to see as many of their colleagues dead as possible.
This does not completely specify the pirates' actions in all situations. To address this, I have two more variations:
(A) Everyone prefers the lower numbered pirates to the higher numbered ones, so if given a choice between, for example #2 or #4 getting gold while the other doesn't, all pirates other than #4 would prefer that #2 get the gold (conversely, they would rather #4 die instead of #2).
(B) is just the opposite. Higher numbered pirates are prefered.
So I am proposing 8 variations: 1A, 1B, 2A, 2B, 3A, 3B, 4A, 4B.
--------------------------------------------------
The discussion in the other thread mostly centers around variant 3"C", wherein the pirates decide randomly between two otherwise equal choices.
It has been argued in that thread that the situation of having money assigned to a dead pirate at the end will never actually arise. Despite this, the rules for such an event do affect the outcome. For example, by variation (2), if any money at all is assigned to #1 at the start of his turn, he can get away with proposing that he get all the gold. Everyone else will agree, because if his proposal fails, everyone dies. But this is not true for any of the other 3 variations. In them, it is likely that at least one pirate would be better off if #1 failed in his proposal.
|
|
 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
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Greedy Pirates Variations
« Reply #1 on: Dec 3rd, 2004, 4:48am » |
Quote Modify
|
For (3) there is the question of what happens to the money a pirate got from a first round if he gets killed in the second.
And for the preferences, it is still not 100% unambiguous. Does #5 prefer 2 coins to be split between #1 and #4 or between #2 and #3?
I would propose to use a lexical-like rule for the remaining pirates, i.e. start by pirate 1, prefer him to survive, then to maximize his money, then prefer #2 to survive, then for him to have the most money, etc. All this after you have maximized your own survival, then your profit (if you survive) and then the number of deaths (whether you survive or not).
|
|
IP Logged |
|
|
|
Three Hands
Uberpuzzler
Gender:
Posts: 715
|
|
Re: Greedy Pirates Variations
« Reply #2 on: Dec 3rd, 2004, 8:40am » |
Quote Modify
|
I would imagine that, with (3), if a pirate that had been assigned gold from round 1 died during round 2, a third round would then occur to redistribute this newly "freed up" wealth, rather than letting it go to waste
|
|
IP Logged |
|
|
|
rmsgrey
Uberpuzzler
   
Gender:
Posts: 2873
|
|
Re: Greedy Pirates Variations
« Reply #3 on: Dec 3rd, 2004, 10:07am » |
Quote Modify
|
on Dec 2nd, 2004, 6:06pm, Icarus wrote:(3) The surviving pirates proceed to spit the excess gold following the same procedure (taking turns in the same order).
|
|
*spit* the excess gold?? ?? ?? ??
There's also the undefined issue of what happens to the non-excess gold in this case...
*******************************************
It was hypothesised, but never proven, in the other thread that no pirate could ever sensibly assign gold to a lower-numbered pirate (except the first to speak, who is usually irrelevant).
Under variant 2, this is no longer true. For n=3, pirate 3 proposes anything other than [0,0,1000], getting pirate 2's vote automatically. Pirate 2 then proposes [0,1000,0] under 2A, or [0,500,500] under 2B, getting pirate 3's vote. Then pirate 1 proposes [999,0,1] or [499,0,501] respectively, getting pirate 3's vote. Had pirate 3 proposed [0,0,1000], the outcome would be [499,501,0] or [500,500,0] respectively since pirate 2 is guaranteed pirate 1's support.
It is, however, always true that the precise distribution of gold among lower numbered pirates is irrelevant - the only way a given pirate's proposal will ever be enacted is if all lower numbered pirates die, in which case it doesn't matter which corpse would have got which gold, meaning that the gold assigned to lower numbered pirates can, WLOG, be regarded as all being assigned to pirate 1.
***************************************************
Some more work:
In all variants, the 1and 2 pirate cases are the same - pirate 1 gets 1000 gold, and pirate 2 (if there is one) gets thrown overboard because he has nothing with which to bribe pirate 1. Therefore, whatever pirate 3 proposes in the 3 pirate variants will be accepted by pirate 2 so long as it offers pirate 2 a chance to survive.
For variants 3 and 4, in the 3 pirate case, if pirate 3 survives pirate 1 is guaranteed to vote for pirate 2's proposal since if pirates 1 and 2 both die, pirate 3 will get all the gold and 2 corpses, which pirate 1 can't beat.
For 3 pirates:
1A) Pirate 3 proposes [1000,0,0], which pirate 2 can survive under, so reluctantly supports. If pirate 2 dies, pirate1 will then be able tosurvive by proposing [999,X,1], so pirate 2 has to bribe pirate 3 (he can't bribe pirate 1), meaning he gets nothing, so offers [x,y,1] where y is at least 2. Pirate 1 then proposes [998,0,2], winning pirate 3's vote.
1B) As 1A, except pirate 2 proposes [0,500,500] and 1 proposes [499,0,501].
2A) As above, ends up with [999,0,1]
2B) As above, ends up with [499,0,501]
From here on, pirate 3's proposal is irrelevant - pirate 1 will always support pirate 2. Also, pirate 2 cannot afford to assign any gold to pirate 1 - doing sowould force pirate 3 to support pirate 1 to stay alive letting pirate 1 get all the gold.
3A) Pirate 2 proposes [0,500,500] and pirate 1 [499,501,0].
3B) Pirate 2 proposes [0,499,501] and pirate 1 [500,500,0].
4A) As 3A ([499,501,0])
4B) As 3B ([500,500,0])
So of the three pirate cases, pirate 1 prefers 2A, pirate 2 either 3A or 4A,and pirate 3 either 1B or 2B. Interestingly, for cases 3 and 4, pirate 1 actually prefers the situation where the others prefer to give money to each other rather than to him...
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print