AHOY! The Pirate Story Solution

So I posted up a question titled “AHOY! The Pirate Story Problem” which can be found here.

Here is the solution!

We begin with a more intuitive idea.
Consider only 2 pirates. Pirate 2 can easily propose that he gets all the 100 gold coins. Since he constitutes 50% of the pirates (his vote will be the decisive vote), the proposal has to be accepted leaving Pirate 1 with nothing.

Now, we increase it by 1 more pirate by considering 3 pirate. Since Pirate 3 knows that if his proposal does not get accepted, then pirate 2 will get all the gold and pirate 1 will get nothing. So he decides to bribe pirate 1 with one gold coin. Well, you may argue that Pirate 1 can demand more. However, Pirate 1 knows that one gold coin is better than nothing so he has to back pirate 3. Pirate 3 proposes {pirate 1, pirate 2, pirate 3} {1, 0, 99}. Since pirate 1 and 3 will vote for it, it will be accepted.

Next what if there are 4 pirates, pirate 4 needs to get one more pirate to vote for his proposal. Pirate 4 realizes that if he dies, pirate 2 will get nothing (according to the proposal with 3 pirates) so he can easily bribe pirate 2 with one gold coin to get his vote. So the coin distribution will be {0, 1, 0, 99}. Getting the hang out it?

Now 5 pirates! Pirate 5 needs 2 votes to get his proposal accepted and he knows that if he dies, pirate 1 and 3 will get nothing. He can easily bribe pirates 1 and 3 with one gold coin each to get their vote. In the end, he proposes {1, 0, 1, 0, 98}. This proposal will get accepted and provide the maximum amount of gold to pirate 5.

Here our approach uses backward induction, a very useful tool in Game Theory. 🙂