Five pirates of different rank share a chest of 100 gold coins. The most senior proposes a split, and everyone votes, including him. If at least half vote yes, that is the split. If not, the proposer goes overboard and the next in rank proposes. The pirates are perfectly logical: first they want to survive, then to get as much gold as possible, and all else being equal they are happy to see someone thrown overboard. What does the captain propose?
It looks as if the captain must split evenly, or even give away nearly everything to survive. In fact he keeps 98 coins and gives one each to pirates 3 and 5. They agree, because without the captain they would get nothing. The whole trick is to reason backwards: from two pirates up to five.
This puzzle is a staple of quant-interview prep: Xinfeng Zhou's 2008 guide opens its brain-teaser chapter with it as "Screwy pirates". It tests one skill: reasoning from the end. Mathematicians call it backward induction, and a good part of game theory rests on it.
Five pirates have different ranks: from 1 (the captain) to 5 (the most junior). No two pirates share a rank.
The most senior pirate still alive proposes how many coins each one gets. Coins cannot be cut, and every one of the 100 goes to someone.
Everyone votes, the proposer included. If at least half vote yes, the split is accepted. Otherwise the proposer goes overboard, and it all starts again with the next in rank.
Each pirate first wants to survive. Then he wants as much gold as possible. And if he does not care how he votes, he votes no: watching someone go overboard is a pleasure too.
What split does the captain propose to survive and keep as much as possible?
"An equal split, 20 each, or the crew will mutiny"
Others think the captain will be lucky to survive at all. In fact he keeps 98 coins: the votes of pirates 3 and 5 cost just one coin each, because without the captain those two get nothing.
Five pirates, 100 coins, the rules above. Lock in how many coins you think the captain can keep without going overboard.
A breakdown of your answer will appear here.
Hard to decide? Open the hints one at a time: the easy one first, then stronger ones.
A pirate doesn't vote for fairness. He compares two futures: with this captain and without him. So first you need to know what happens if the captain goes overboard.
Reason from the end: solve the game for two pirates, then three, then four, and only then five. A pirate's vote costs one coin more than he would get without the captain.
With only pirates 4 and 5 left, pirate 4 is half the vote by himself and takes all 100. So pirate 3 buys pirate 5's vote for one coin: 99, 0, 1. Now do the same for four pirates, then for five.
Choose how many pirates are on board and hand out the coins. The rest is yours. Each pirate votes by the rules of the puzzle: he compares your split with what he would get if you went overboard, and says yes only if you offer more. Each vote comes with a one-line reason.
Backward reasoning can be checked by brute force: go through every possible split, hold a vote on each, and see where the captain gets the most. Then throw hundreds of thousands of random splits at the crew and compare with the exact count.
A row is a game with n pirates, a column is a rank. Each row is computed from the one above: the captain buys the cheapest votes.
Five pirates, 100 coins. The captain takes c coins and scatters the rest among the other four at random (all splits equally likely). What share of such splits passes the vote? The line shows the exact share from the full count, the dots show the simulation.
A pirate does not vote for fairness: he compares two futures, with this captain and without him. To know the second one you have to solve the game with a smaller crew. So we start from the end.
A pirate left alone keeps all the gold. With two, the captain's own vote is already half, so he takes everything. Each step rests on the one before: a pirate knows what he will get if the captain goes overboard.
A pirate votes yes only if he gets more than without the captain, since when it is equal he happily votes no. So a pirate's vote costs one coin more than he would get in the four-pirate game. Pirates 3 and 5 get 0 there, so their votes cost one coin each. The captain needs three votes out of five: his own and two more.
The split 20, 20, 20, 20, 20 does not fail: pirates 3, 4 and 5 get more than without the captain and vote yes. Only pirate 2 votes no, because without the captain he becomes captain himself and takes 99. But the captain pays 60 coins for three votes when two at one coin each are enough. Fairness costs him 78 coins here.
The second in rank is waiting for the captain to go overboard: then he splits the chest himself and takes nearly all of it. To buy his vote you would have to give him at least 100, which is the whole chest. So nobody ever buys him: in the round 3 table the rank 2 column holds only zeros.
Hence the alternation. Whoever gets a coin in the game with n pirates gets nothing in the game with n + 1, and the other way round (except the captain himself). So the coins always go to ranks 3, 5, 7 and on, every other pirate.
The pirate game has perfect information: everyone knows everything that has happened and every possible continuation. Such a game is solved from the end. First find the best move in the last situation, then in the one before it, knowing what comes next, and so on back to the start.
Vn = G − (sum of ⌈n/2⌉ − 1 smallest of xi(n−1) + 1)
Here Vn is the captain's share in the game with n pirates, and xi(n−1) is what pirate i gets in the game without the captain. In 1965 Reinhard Selten proposed the requirement now called subgame perfect equilibrium: strategies must be best not only in the actual game but in every part of it, even parts that are never reached. A threat like "I will vote no even if it hurts me" carries no weight here, because at the moment of the vote nobody would carry it out.
At least half of the votes are needed. The captain always has one, the rest must be bought.
Each bought vote costs 1 coin: it is sold by a pirate who would get 0 without the captain. There are always enough of them.
Five pirates and 100 coins: two votes must be bought.
The limit: with 2G + 1 and 2G + 2 pirates the captain hands out every coin and keeps nothing, but lives. Beyond that there are not enough coins for the votes.
You can check the formula against the round 3 table: every two pirates cost the captain one more coin. Notice that an odd n and the even n after it cost the captain the same, because half of an even n equals a majority of n − 1.
The pirate puzzle opens the door to three worlds. In mathematics it shows what happens when there is not enough gold to go round. In logic it runs into its own weak spot: what if the other side is not so logical? In practice the same vote counting helps make sense of bargaining and parliamentary coalitions.
Mathematics
Captains who survive beyond 2G pirates:
While there are at most 2G + 2 pirates, the captain buys votes at a coin each. Beyond that the coins run out, and a new currency appears: fear. A pirate who would be thrown overboard right after the captain votes yes for free, just to survive.
The captain of 2G + 3 pirates has G coins and his own vote, but needs G + 2: overboard he goes. Then the captain of 2G + 4 gets the next pirate's vote for free, and that is just enough. From 2G + 5 to 2G + 7 the captains die, and each death adds one more frightened voter, so the captain of 2G + 8 has G bought votes, 3 free ones and his own: exactly half. The next survivors come at 2G + 16, 2G + 32 and so on. For 100 coins and 500 pirates these are the captains of 201, 202, 204, 208, 216, 232, 264, 328 and 456 pirates. Steve Omohundro posed the 500-pirate version, Ian Stewart worked it out in his Scientific American column in May 1999, and we checked it with our own count.
An honest caveat: from 2G + 2 pirates on there are more cheap votes than coins, so exactly who gets a coin is not pinned down. There are many equilibria. But who survives does not depend on it: every vote except the frightened ones costs at least a coin, and there are only G coins.
Logic
You are player A and move first. On each move you can take 4/5 of the pile (the other player gets 1/5) or pass, and then the pile doubles. If nobody has taken anything after move six, A gets 256 and B gets 64.
Reason from the end. On move six, B takes 128 rather than pass for 64. Knowing that, A takes 64 on move five. Knowing that, B takes 32 on move four. And so on back to move one: A takes 4 straight away. Both get a pittance, though they could have had dozens of times more.
Robert Rosenthal described this game in 1981. In 1992 McKelvey and Palfrey ran exactly this six-move game in the lab, only in dollars: from $0.40/$0.10 up to $25.60/$6.40. Fewer than 1% of players took on the first move: people trust each other, and trust pays. The backward-induction chain is fragile: a single doubt that some player further down will act flawlessly is enough to bring the whole thing down. The pirates' chain is four steps long, and each step needs everyone to know that everyone knows that everyone is logical.
Practice
An imaginary parliament of 100 seats; a majority needs 51. Click parties to add them to the coalition.
The captain buys no surplus votes, because each extra partner takes a share of the spoils. In 1962 the political scientist William Riker stated the same "size principle" in his book The Theory of Political Coalitions: rational players form coalitions only slightly larger than the majority they need. In this parliament the largest party, with 38 seats, is not part of the smallest winning coalition: B, C and E together have exactly 51.
Real people, though, do not behave like these pirates. In 1982 Werner Güth, Rolf Schmittberger and Bernd Schwarze ran the ultimatum game: one person proposes how to split a sum, the other accepts or refuses, and then neither gets anything. Pirate logic says offer the minimum, and the responder should accept it. According to the summary of experiments in Colin Camerer's book Behavioral Game Theory (2003), proposers offer 40–50% on average, and offers of 20% or less are rejected about half the time. People will pay to punish greed, and a captain who offers a real crew 98 out of 100 is taking a risk.
Ernst Zermelo wrote one of the first papers of game theory, about chess. The theorem now named after him says that White can force a win, or Black can, or each side can secure a draw. Zermelo never stated it quite like that and did not reason backwards (Schwalbe and Walker, 2001). Today it is proved by backward induction.
In The Theory of Political Coalitions, William Riker argued that participants form coalitions just as large as they believe will ensure winning, and no larger. The pirate captain buys exactly as many votes as he needs.
Robert Rosenthal described a game in which backward induction says take at once, although patient players would get far more. The name is usually explained by its long tree of moves: early versions had up to 100 "legs".
Güth, Schmittberger and Schwarze published the first ultimatum game experiment in the Journal of Economic Behavior and Organization. It has since been repeated in many countries, and in most places people turn down offers that are too unfair, even though it costs them money. One exception: the Machiguenga of the Peruvian Amazon accepted almost any offer (Henrich, 2000).
Reinhard Selten introduced subgame perfect equilibrium in 1965 in a paper on oligopoly. In 1994 he shared the Nobel memorial prize in economics with John Nash and John Harsanyi.
In May 1999 Ian Stewart devoted his Scientific American column, "A Puzzle for Pirates", to the pirates and worked out what happens when there are more pirates than coins. With 500 pirates and 100 coins, the 44 most senior go overboard, and only the captain of the remaining 456 survives. Steve Omohundro sent him the puzzle; Stewart's own version had 10 pirates.
Share your own explanation, an objection or a variant of the puzzle. You need a GitHub account to comment.
I keep adding new puzzles, new ways to explain them and write-ups of the discussions they start. Leave your email and I'll write when something new is out. No spam, one-click unsubscribe.
The sign-up form will appear here soon.