This week’s FiveThirtyEight Riddler is a logic puzzle. Assume 10 “Perfectly Rational Pirate Logicians”. The pirates have found 10 gold pieces, and the puzzle is to figure out how they will allocate the loot among themselves. There are several constraints.
First, the pirates themselves are ranked in a strict hierarchy, with the Captain at the top, and then the others ordered beneath them, so if for any reason the Captain is no longer able to fulfill his duties, the second in command becomes new Captain, and everyone else moves up one step on the hierarchy.
Second, the Pirates practice a form of democracy. While the Captain, due to rank, gets to propose an allocation, the whole crew, with one vote per pirate, votes on the proposal. If that proposal gets half or more of the vote, it carries, but if more than half of the pirates vote against it, they will mutiny, killing the old Captain, and leaving it to the new captain to propose an allocation.
So our perfectly rational pirate logicians have three constraints in determining how they will vote on a proposed allocation:
- They value life above all, so they will not vote in a way to put their own lives at risk of mutiny if they can at all avoid doing so.
- They are greedy, so as long as their life is not at stake, they will vote for something which maximizes their own personal share of the loot.
- They are bloodthirsty, so if they have two choices in which they’d remain alive but get the same booty, they will prefer to mutiny and kill the captain.
Given the above constraints, how will the 10 pirates allocate their 10 newly found gold pieces?
It’s easier to analyze things with fewer pirates, so I’ll start there and look for some patterns. Trivially one pirate simply keeps all the wealth for himself. Two is almost as simple: even if the second ranked pirate votes against, the Captain’s vote for the proposal will guarantee passage, and thus with two pirates, the Captain again keeps all the treasure.
At three there’s a new wrinkle: now the Captain can’t keep it all himself, or else he’ll be killed. So he must buy at least one vote. He could do this by offering 1 gold piece to another pirate (who otherwise might face the prospect of getting nothing). He must offer 1 gold to the 3rd ranked pirate, who would then accept the proposal because if he votes to mutiny, the 2nd ranked pirate would simply then keep all the gold, and the 3rd ranked one would get nothing. Note that the Captain can’t offer the 1 gold to the 2nd ranked pirate instead: while that would get him 1, if #2 knows #3 will get nothing, he knows he will vote to mutiny (since, all other things being equal, a bloodthirsty pirate prefers mutiny); thus #2 will vote to mutiny even if he’s offered 1 gold. And the captain, being greedy, won’t offer gold to #2 if he’s already offering it to #3.
Four pirates is effectively the same situation as three: the Captain will offer 1 gold to #3, and keep the rest himself. Now there are two votes to mutiny, but a tie goes to the Captain’s proposal.
At 5, however, the Captain must buy a 3rd vote. We know he can’t offer 1 gold to #2 (who gets to be captain after a mutiny), so he must offer gold to two of #3, #4, and #5. But remember that if there’s a successful mutiny, we revert to the 4 pirate case, with the surviving pirates each moving up a rank. Thus the Captain must offer only to #3 and #5. If he offers 1 gold to #4, #4 will still reject it, because he can still get 1 gold from the allocation after a mutiny reduces them to 4 pirates. Giving 1 gold to #3 and #5 works when you have 5 or 6 pirates.
And we’re seeing a pattern emerging. Add a seventh pirate, and now the Captain needs to buy a 4th vote. A mutiny would leave us in the 6 pirate case, in which pirates #3 and #5 would then get 1 gold. Before a mutiny, those are the ones ranked #4 and #6, so we see that the Captain must offer 1 gold each to #3, #5, and #7 to ensure the 4 votes needed to win. This allocation also works in the 8 pirate case.
So to solve the main riddle as posed, we get to the 10 pirate case, and the Captain will offer 1 gold each to pirates #3, #5, #7, and #9, which gives him their four votes, plus his own, to avert a mutiny. Since he gave 4 gold to other pirates, he’s kept 6 gold for himself. So that’s the answer to the riddle.
As extra credit, the problem asks how to generalize to P pirates sharing G gold pieces. The generalization is (mostly) trivial from here: so long as there’s enough gold, the captain offers 1 gold to each of the odd number ranked pirates, and he keeps the rest for himself. But this model only works so long as G >= P/2 – 1. In other words, there must be enough gold for the Captain to buy off each of the odd-number ranked pirates below him. When G = P/2 – 1, then the Captain gets no gold at all, but at least he lives!
If there’s not enough gold to buy off all the lower-ranked odd numbered pirates, then things get quirky and depend on whether the number of pirates is even or odd. If he’s 1 gold short, the Captain of an odd numbered crew is doomed. The crew will vote to mutiny (because they’re bloodthirsty), which reduces the crew by 1 member, and now the new Captain can save his own skin by keeping nothing and buying off the lower-ranked odd numbered pirates. But if he’s 1 gold short and the crew is an even number, then the Captain lives: he takes nothing, and offers nothing to one odd numbered pirate also, but he will get the vote of pirate #2 in this case, because #2 realizes that unless they agree to a distribution, he will become the new Captain in a hopeless situation and will also be killed. So in this case the original Captain can afford to stiff #3 because he’s assured of #2’s vote. In this case the Captain must stiff the lowest ranking odd numbered pirate: even if that pirate gets a gold, because he’s bloodthirsty, he’d still vote to mutiny because he knows there will be another mutiny of the odd numbered crew before the new Captain now has enough gold to buy off all the other odd numbered pirates.
If the shortfall is 2 gold, and there is an odd number of pirates, the Captain is again doomed: the second in command can vote to mutiny, knowing that he can save himself as captain described above in the situation of being short 1 gold with an even number of pirates. For a shortage of 2 gold and an even number of pirates, the Captain could now count on the vote of the #2 pirate, but that doesn’t seem to be enough to help. #3 would become Captain after 2 mutinies and could then save himself, and the lower-ranked odd numbered pirates (except the last) would each get 1 gold in that case. So the pattern here seems to be bad news for the Captain when there is a larger shortfall of gold. With larger gold deficits I think matters just become worse. The number of pirates who would vote to receive nothing in hope of preventing themselves from becoming Captain and facing mutiny does not appear to grow faster than the increasing shortfall in gold to buy off lower ranked pirates. So I think at larger deficits the highest ranking pirates will face mutinies until you get down to an even number of pirates with a G = P/2 – 2, at which point the Captain can save himself by taking no gold and giving 1 to each of the odd numbered pirates except the lowest ranked odd pirate.