GAME THEORY

backwards induction

think ahead and reason backwards

A group of 5 pirates is dividing up 100 gold coins. How will they split the treasure?

The pirates are a disciplined and logical group, and they have a custom of how to split up treasure.

The 5 pirates (A, B, C, D, and E) have a strict organization by strength: pirate A is the strongest, followed by B, then C, then D, and then E. The voting process is a series of proposals with a lethal twist. Here are the rules:

1. The strongest pirate (A) offers a split of the gold. An example split is: “50 to A (me), 10 to B, 20 to C, 10 to D, and 10 to E.”

2. All of the pirates, including the proposer, vote on whether to accept the split. In the case of a tie, the proposer holds the casting vote to break the tie.

3. If the pirates agree to the split, it happens.

4. Otherwise, the pirate who proposed the plan gets thrown overboard from the ship and perishes.

5. The next strongest pirate takes over and then offers a split of the money. The process is repeated until a proposal is accepted.

Pirates care first and foremost about living, then about getting gold.

If a pirate is indifferent between saying “Yes” and “No” to a split in terms of money, then the pirate votes “No” because the pirate prefers to eliminate stronger pirates.

How does the game play out?Solution to game

The game can be solved by backwards induction. You want to think ahead and reason backwards.

Start at the end of the game. What would happen if the game continued so only pirate E remained? This is a trivial case as pirate E would take all 100 coins for himself.

Now reason backwards one step. What would happen if the game got to pirate D proposing a split? Similarly, pirate D would take all 100 coins for himself. While pirate E would oppose the split, pirate D is in favor, so the vote would be tied at 1-1. Pirate D could then cast the tie-breaking vote and make the proposal go through.

Now comes the interesting part when we reason one more step backwards. What would happen if pirate C is offering the split? Pirate C needs to buy 1 vote to make the plan go through. If pirate C dies, then pirate D would take all 100 coins and pirate E ends up with nothing. All the pirates know this. This presents an opportunity to buy the vote of pirate E.

Pirate C does not take all 100 coins for himself. Instead pirate C offers 1 coin to pirate E. Now pirate E can either vote for this split and get 1 coin, or pirate E can vote against it which leads to getting nothing when pirate D is in charge. So pirate E prefers this plan and would vote for it.

Therefore, pirate C would offer, “99 to C, 0 to D, and 1 to E.” Pirates C and E would vote for this plan and it would go through.

Now let’s reason one more step. What would happen if pirate B was in charge? Pirate B similarly needs to buy 1 vote. The easiest vote to buy is pirate D, who ends up with nothing if the split fails and pirate C ends up in charge.

Accordingly, pirate B would offer, “99 to B, 0 to C, 1 to D, and 0 to E.” Pirates B and D vote affirmatively against C and E, and pirate B holds the tie-breaking vote so the plan goes through.

Now we return to the original situation. What does pirate A do? Pirate A needs to buy two votes in order to make a proposal pass. If pirate A dies, then pirate B ends up in charge and that would leave pirates C and E with nothing. Pirate A can therefore buy the votes of pirates C and E by offering each 1 coin.

Pirate A offers, “98 to A, 0 to B, 1 to C, 0 to D, and 1 to E.” Pirates A, C, and E vote for the plan and it passes.

The surprising part of the problem is the strongest pirate can end up with most of the money, even though the other pirates hold the power to toss him overboard. The reason is some of the weaker pirates can be bought off for very little, knowing they would end up with nothing if the original split failed.