538 had a fun riddler this past week:
Ten Perfectly Rational Pirate Logicians (PRPLs) find 10 (indivisible) gold pieces and wish to distribute the booty among themselves.
The pirates each have a unique rank, from the captain on down. The captain puts forth the first plan to divide up the gold, whereupon the pirates (including the captain) vote. If at least half the pirates vote for the plan, it is enacted, and the gold is distributed accordingly. If the plan gets fewer than half the votes, however, the captain is killed, the second-in-command is promoted, and the process starts over. (They’re mutinous, these PRPLs.)
Pirates always vote by the following rules, with the earliest rule taking precedence in a conflict:
- Self-preservation: A pirate values his life above all else.
- Greed: A pirate seeks as much gold as possible.
- Bloodthirst: Failing a threat to his life or bounty, a pirate always votes to kill.
Under this system, how do the PRPLs divide up their gold?
Extra credit: Solve the generalized problem where there are P pirates and G gold pieces.
Here is my answer:
The Captain will propose the following distribution, which will be accepted by all pirates who are offered a coin: 6 gp for himself, and 1 gp each for pirates 2, 4, 6, and 8 (where lower numbers indicate lower ranks).
To see why, we can work backwards from the end game. If it comes down to just P2 and P1, P2 will propose taking all the gold for himself; since 50% is sufficient to ratify a plan, it will be go into effect even though P1 will vote against it. So what does P3 have to offer to do to get a proposal approved? He clearly can’t get the support of P2. (Even if he offered P2 all the gold, P2 would still vote against the plan on account of bloodthirst!) But 1 gp is sufficient to get a vote from P1. P3 doesn’t need to offer P2 anything, so he can take the balance (9 gp) for himself. Continuing this backwards reasoning, P4 also needs 1 vote other than his own . It is most easily acquired from P2, who will end up with nothing if things proceed to the next stage. So P4 can offer P2 1 gp, keep 9 gp for himself, and offer nothing to P1 or P3. The ideal solution for each pirate is thus as follows:
s(P2) = {0, 10} (meaning 0 gp for P1 and 10 gp for P2)
s(P3) = {1, 0, 9}
s(P4) = {0, 1, 0, 9}
s(P5) = {1, 0, 1, 0, 8}
s(P6) = {0, 1, 0, 1, 0, 8}
s(P7) = {1, 0, 1, 0, 1, 0, 7}
s(P8) = {0, 1, 0, 1, 0, 1, 0, 7}
s(P9) = {1, 0, 1, 0, 1, 0, 1, 0, 6}
s(P10)={0, 1, 0, 1, 0, 1, 0, 1, 0, 6}
In each case, every pirate who is offered a gold piece will vote for the proposal, since the alternative is to end up with nothing. Every pirate who is offered nothing will, of course, vote against the proposal.
What about the extra credit problem, with g gold pieces and P pirates. The same basic reasoning applies:
S(P2) = {0, g}
S(P3) = {1, 0, g-1}
S(P4) = {0, 1, 0, g-1}
S(P5) = {1, 0, 1, 0, g-2}
S(P6) = {0, 1, 0, 1, 0, g-2}
For any even P, the captain will award 1 gp to each even-numbered pirate other than himself, and take all the remaining gold pieces for himself.
For any odd P, the captain will award 1 gp to each odd-numbered pirate other than himself, and take all the remaining gold pieces for himself.
But what if there are not enough gold pieces? E.g. consider 2 gp for 5 or 6 pirates? In this case, the captain will be forced to distribute all of the gold to others just to save his own hide: the rule above still holds but leaves the captain with nothing. 2 gp for 7 pirates is even worse: there is no proposal the captain can make that will get 3 (or more) votes other than his own. There are just too many bloodthirsty pirates with nothing to lose. Whatever P7 proposes, it will be rejected and he will be killed. What about 2 gp for 8 pirates? Now, a new wrinkle is introduced: P7 will vote for P8’s proposal to save his own life, even if P8 offers him no gold. Furthermore, pirates will decide whether to vote for P8’s proposal not by comparing their outcome to P7’s doomed hypothetical proposal, but rather to P6’s proposal. Therefore, P8 needs to offer gold pieces to 2 of P1, P3, and P5. Those 2 votes, plus the votes of P8 and P8, will be enough to ratify.
What about P9? P9 can count on P7’s vote and his own vote. He needs 3 more votes, but with only 2 gps to spread around, he isn’t going to get them.
And P10? He can count on P7 and P9’s vote (even if he offers them nothing), and his own. So he only needs 2 more votes. Pirates will decide by comparing his proposal to P8’s hypothetical proposal. But P8 could propose any of three possible distribution schemes, which complicates the votes of P1, P3, and P5. Each has only a 2/3 probability of getting any gold if P10’s proposal fails (or an expected value of 2/3 of a gp), so if they are offered a gp by P10, they will support the proposal. So P10’s proposal will pass.
11 pirates and 2 gp? P11 can count on the votes of himself, P7, and P9. He needs 3 more votes, and has no way to secure them with only 2 gp. Any proposal he makes will fail.
12 pirates and 2 gp? P12 can count on the votes of himself, P7, P9, and P11. He needs 2 more votes. By offering 1 gp each to 2 of P2, P4, P5, and P6 (each of whom otherwise has only a 50% chance of receiving a gp), he can secure them.
With 2 gp, this odd-even pattern will repeat indefinitely. I’m not sure of the general rule, but things get tricky when there are a lot more pirates than gold pieces.