Greed, and love of dear life: The Pirate Problem
February 5, 2011 1 Comment
There are pirates discussing on how to divide their booty of 100 gold coins. The pirates have a strictly defined seniority order among themselves. Let’s say that, for all i, Pirate i is more senior than Pirate j, for all j < i.The method that they agree upon to divide their loot is the following:-
Initially there are n pirates.
i = n;
While (there is a pirate alive)
Pirate i proposes a division.
If (at least 50% of the pirates alive approve of his division plan)
Division takes place, and things end here.
Pirate is killed (and of course, the division proposed by him is not carried out).
i – -;
End of While loop.
End of algorithm.
We also have a few other observations to make:
- The pirates value their own individual lives most of all.
- Next to protecting their lives, the thing uppermost on their minds is to maximize their own share of the loot.
- The 3rd most important consideration for the pirates is to reduce the number of pirates on board.
- All pirates are extremely intelligent (and thus, each certainly knows that, each of the others is extremely intelligent).
- Whenever pirates have to make a decision (whether to approve/ disapprove of, or to propose a division plan), they keep in their minds the 4 points mentioned above.
Question: Say, n = 5, what division should the senior-most pirate propose (he is the one who gets the first chance to propose a division plan) so as to ensure that he doesn’t get killed, and given that he doesn’t get killed, to maximize his share of the loot?
Consider what would happen with just one pirate. Obviously, he would get all the 100 coins.
With 2 pirates, Pirate 2 gets to propose a division. He knows that he will always get 50% of the vote (by approving of his own plan), and hence can propose freely any division that he likes. Hence, he will propose a division with 100 coins for himself, and none for Pirate 1, and get away with it.
With 3 pirates, Pirate 3 has to decide on how to divide the loot. He knows that if he dies, only 2 pirates would be left. In such a scenario, we all know that Pirate 1 will not get any coin. Hence, Pirate 1, being greedy, has an incentive to accept any plan that Pirate 3 proposes giving him > 0 gold coins so as to ensure that Pirate 3’s division plan is carried out. Hence, Pirate 3 can win 2 votes (out of 3) by proposing a division giving 1 coin to Pirate 1 and keeping 99 for himself.
With 4 pirates, Pirate 4 gets to decide the division scheme. Again, we know that, if Pirate 4 dies, Pirate 2 wouldn’t get even one gold coin, in the subsequent division which would be proposed by Pirate 3. Hence, Pirate 4 can win 2 votes (out of 4) by proposing a division giving 1 coin to Pirate 2, and keeping 99 for himself.
With 5 pirates, it is Pirate 5 who gets to propose. Again, his death would result in Pirate 1 and Pirate 3 not getting anything in the subsequent division which would be proposed by Pirate 4. Hence, to win their votes, and get 3 votes (out of 5), Pirate 5 can give 1 coin each to Pirates 1 and 3, and keep 98 for himself.
Generalizing for n (n < 100):-
Pirate n can propose a division giving 1 coin each to Pirates n-1, n-3, … (up to either 1 or 2), and keep the rest for himself.