Greedy pirates
Categories: Challenges
A pirate ship captures a treasure of 1000 golden coins. The treasure has to be split among the 5 pirates: 1, 2, 3, 4, and 5 in order of rank. Assume the pirates are all perfect logicians, and they aim to maximise their own profit at any cost. They, being pirates, are also bloodthirsty -- so if they can get the same profit and MORE deaths, they prefer to also maximise casualties. Starting with pirate 5 they can make a proposal to split the treasure. This proposal can either be accepted or the pirate is forced to walk the plank. A proposal is accepted if and only if a majority of the pirates agree on it -- if there is a tie, the proposal fails. What proposal should pirate 5 make?
Let n be the number of pirates. The nth pirate needs to offer a majority of pirates a strictly superior deal to the (n-1)st optimal strategy in order to succeed. The strictness is enforced by the bloodthirst assumption. (Note that I also assume each pirate's bloodthirst is tempered by a desire to avoid his own death if possible.)
If n=1, clearly the best strategy is to give pirate #1 all the money.
If n=2, then pirate #2 can't claim even one coin without offering pirate #1 an inferior deal to the n=1 case. Since #1 gets all the money anyway, he votes to reject any offer since he's bloodthirsty.
if n=3, assuming that #2 has a preference to not die, the ideal strategy is to offer the following: #1:0, #2:0, #3:1000. #2 will vote in favor since he doesn't want to die, which is a 2:1 majority to accept.
If n=4, Then no offer to #3 will be superior to the n=3 case, so offer him nothing. But you need both of the votes from 1 and 2 to get a majority, and they can both be bought for no less than a coin. Thus the optimal strategy is #1:1, #2:1, #3:0, #4:998
If n=5, a similar logic applies. #4 is a lost cause, #3 can be bought for 1 coin, and either #2 or #1 can be bought for two coins. Thus there are two optimal strategies: #1:2, #2:0, #3:1, #4:0, #5:997 and #1:0, #2:2, #3:1, #4:0, #5:997.
We'll assume from the beginning that all pirates want to live, first and foremost. Priorities go like this:
1) survive
2) maximize wealth
3) maximize deaths
Also worth noting is that pirates walk the plank on tie votes.
Let's look at this in reverse order, as Lucas did above.
1 pirate: If pirates 2-5 have all walked the plank, pirate 1 walks away with all the gold. So he proposes 1000 to himself and approves it. Pirate 1 will also vote to reject every single deal.
2 pirates (1 and 2): Pirate 2 will accept any offer made by pirate 3, as 3 will vote in favor and 1 will vote against whatever 3 proposes. Since 2 and 3 both want to live, and 2 dies if 3 dies, he must. However, if it gets down to pirate 3, pirate 2 gets no money (see below); thus, pirate 2 has incentive to accept the porposals of 4 or 5 that give him something, since he prioritizes gold over casualties.
3 pirates (1-3): Pirate 1 will reject all proposals and pirate 2 must accept them all. Thus, pirate 3 will allocate 1000 gold coins to himself.
4 pirates (1-4): Pirate 4 can count on rejection from 1 and 3 no matter what he does, thus walking the plank. Since 3 will get all the money if it gets to him, he'll reject any proposal. Thus, 4 will accept anything 5 proposes.
5 pirates (1-5): The original problem. From the above, we see that 1 rejects all offers, 2 accepts any offer that gives him even a single coin, 3 rejects any offer as he gets all the money, 4 accepts anything. Thus, the offer should be 999 to pirate 5, 1 coin to pirate 2, and nothing for pirates 1,3, and 4.
The answer is that Pirate 5 should propose 1 coin be given to Pirates 1 and 4 while he/she receive the rest (998 coins).
(I recently applied for an internship with LiveRamp)
Pirate 2 knows Pirate 1 would disagree with his proposal leaving him to either walk the plank or receive nothing. Therefore, Pirate 2 knows he needs Pirate 3 in order to come to an agreement and at least receive some of the money (Pirate 3 would most likely propose Pirate 2 receive 1 coin and he/she receive the rest).
Since they are perfect logicians, Pirate 1 and 4 know what Pirate 2 and 3 have in mind, they also know that if they vote against Pirate 5's proposal and he/she walks the plank that Pirate 2 and 3 will vote against Pirate 4's proposal, which would result in tie and the demise of Pirate 4 (then they can hatch their evil plan).
Therefore, because Pirates 1 and 4 know they need Pirate 5 in order to secure any money while also staying alive, they are willing to accept 1 coin each while Pirate 5 receives the rest.
The answer is actually that Pirate 5 propose Pirate 1 receive 1 coin, Pirate 4 receives nothing, and he/she receive the rest (999 coins).
Same decision making logic applies except that because Pirate 1 knows he will stay alive he needs some compensation to be convinced, but Pirate 4 just wants to stay alive and so it therefore willing to accept nothing. Got to maximize profit right?!!
Sorry, my proposals were both incorrect my last reply I promise. Lucas is correct in his first proposal, but not the second. My reasoning is similar, but with a few corrections.
Pirate 5 should offer 2 coins to Pirate 1 and 1 coin to Pirate 3 while he/she receives the rest (997 coins).
Yes with just Pirates 1 and 2, Pirate 2 would have to offer all coins to Pirate 1 to stay alive.
With Pirates 1, 2, and 3, Pirate 3 would offer 1 coin to Pirate 2 while he/she received the rest (999 coins). Pirate 2 would agree because other option is no coins OR death (the first difference from Lucas).
With Pirates 1, 2, 3, and 4, Pirate 4 would offer 1 coin to Pirate 1 and 2 coins to Pirate 2; they would accept this superior deal knowing what Pirate 3 would offer (2nd difference: if Pirate 2 were offered 1 coin he/she would decline knowing he would be offered 1 coin by Pirate 3 while also enjoying the demise of Pirate 4).
Therefore, to maximize profit and survive Pirate 5 should offer 2 coins to Pirate 1 and 1 coin to Pirate 3 while receiving the rest (997 coins). Pirate 3 would agree because otherwise he/she will receive nothing from Pirate 4's deal and of course Pirate 1 would agree knowing that otherwise he/she would receive only 1 coin.
I have to amend my previous post for pirates 4 and 5. The logic is correct for 1-3.
4 pirates (1-4): Since pirate 1 will definitely get no money if it gets down to 3, he'll approve any offer from 4 that gives him even a single coin. 4 will propose 1 coin to pirate 1. Pirate 2 still has to be similarly placated. Thus, 4 gives a coin to 1 and 2 and 998 to himself. This gets him yes votes from 1, 2 and 4.
This also changes his vote for pirate 5. He'll reject any offer 5 proposes.
----
5 pirates (1-5): Pirate 5 now has to placate 2 of the first 3 pirates. P1 knows he'll get 1 coin from P4, so P5 has to offer him 2 coins for his vote. The same goes for P2; he needs an offer of 2 to give a yes vote. 3 get nothing from 4, thus he'll take a single coin from 5. Thus, five will do the following: P3: 1 coin, P1 OR P2 (but not both): 2 coins, P4: 0 coins, P5: 997 coins.
Looking back, I see that Lucas got it correct with his first reply. Well done!
Working backwards:
If it's #2 and #1, then #1 will decline any proposal made by #2 to get 1,000 coins and maximize deaths.
If it's #3, #2, and #1, then #3 knows #2 will accept anything or else he will die if left alone with #1, so #3 will make the proposal #3 - 999, #2 - 1, #1 - 0.
If it's #4, #3, #2, and #1, then #4 knows if he dies, #1 will be left with nothing, so he gives him a coin to gain his vote. He also gives #2 an extra coin, increasing his gain to 2 coins because if #4 dies, #2 will only get 1 coin. He will maximize his profit by only giving out 3 coins to #1 and #2 because if he dies, #3 will get 999 coins, so there is nothing to gain by giving anything to #3.
If all pirates are alive, #5 just needs to other votes to secure his proposal. If he dies, #4 will get 997 coins, so he'd have to offer him 998 coins to secure a vote, meaning this is probably a bad choice; however if he dies, #3 will receive nothing, so he should give 1 coin to #3 to secure his vote. If #5 dies, #2 and #1 receive 2 and 1 coin/s respectively. So to secure the last vote he needs to increase one of their profits by 1. To maximize his own profit, he should give #1 an extra coin.
So the proposal by 5 should be as follows:
#5 - 997
#4 - 0
#3 - 1
#2 - 0
#1 - 2
Alex said "Yes with just Pirates 1 and 2, Pirate 2 would have to offer all coins to Pirate 1 to stay alive."
This is incorrect. If there is just pirate 1, he gives all the coins to himself. Since he is bloodthirsty, (pirate 2 dying + 1000 coins) is strictly better than (pirate 2 living + 1000 coins). Thus pirate 1 would vote to reject *any* offer from pirate 2.