Five pirates, P1 the most senior down to P5, divide 100 gold coins. P1 proposes a split and all living pirates vote. If at least half approve, counting the proposer, it passes. Otherwise P1 is thrown overboard and P2 proposes. Each pirate wants to survive first, take the most coins second, and throw a rival overboard when otherwise indifferent. What does P1 propose?

Five pirates, P1 the most senior down to P5, divide 100 gold coins. P1 proposes a split and all living pirates vote. If at least half approve, counting the proposer, it passes. Otherwise P1 is thrown overboard and P2 proposes. Each pirate wants to survive first, take the most coins second, and throw a rival overboard when otherwise indifferent. What does P1 propose?

Approach: Solve the two pirate case first and work upward. Each proposer only has to buy the cheapest votes, and a pirate accepts one coin whenever the next round would pay him nothing.

98, 0, 1, 0, 1. Work backward by induction. With P4 and P5 alone, P4 keeps 100 because his own vote is half of two, so P5 gets nothing there. P3 then needs one extra vote for a majority and bribes P5 with 1 coin, proposing 99, 0, 1. P2 needs one extra vote and bribes P4, who gets nothing under P3, proposing 99, 0, 1, 0. P1 needs two extra votes, and the pivotal pirates are P3 and P5, who each get nothing under P2, so 1 coin each buys them and P1 keeps 98. An equal split is wrong because every pirate compares the offer with what the next proposal gives him, never with an even share.

Follow-up: How does the split change if a pirate strictly prefers throwing the proposer overboard whenever his coin payoff would be equal either way?

Key concepts: backward induction, majority vote, pivotal pirate, bribe.