# 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?

Did you love challenges? Then you will love LiveRamp. Apply now to join our team.

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.

I'd take this a step further than the solution that Lucas, Brian, and Evan proposed. Pirate 4 knows that P5 can buy P3's vote with 1 coin, and P1 or P2's vote for 2 coins -- so he knows he's getting no coins, and no dead pirates, regardless if he accepts the proposal from P5 or not. Therefore, P5 can buy P4's vote with just one coin, and can buy P3's with just one coin. Those are the two votes P5 needs to have a majority, so he can give P1 and P2 nothing at all -- and thereby keep 998 coins for himself, instead of 997. The optimal solution is therefore:

P5: 998

P4: 1

P3: 1

P2: 0

P1: 0