The Pirate Puzzle
There are five pirates on a ship, A, B, C, D and E. A is the captain, with B second in command and so on. They have just completed a raid and so they have 100 gold coins to split between them.
It is up to the captain to offer a distribution of coins which the crew (including the captain) will then vote on. If there is a tie then the proposer of the deal gets a deciding vote. If the deal is accepted then anyone who has been given coins will keep them. However if the deal is voted against then the proposer is thrown overboard and it is up to the next in command to propose a new distribution of coins. This pattern continues until a deal is accepted. The pirates priorities are in the following order:
1. Pirates are savvy. Each pirate wants to survive. (Pirates have their rules in the opposite order to robots it would seem.)
2. Pirates are greedy. Each pirate wants as many coins as they can, unless it would result in the first rule being broken.
3. Pirates are bloodthirsty. Each pirate would prefer to throw other pirates overboard unless it would result in breaking the first or second rule.
What distribution of the 100 gold coins is optimal for the captain to propose?
Hints and answer below...
Hint 1/3: If it got down to only pirates D and E, what should pirate D offer?
Hint 2/3: Answering the first hint, pirate D would offer 100 coins to xemself* since in a tie D would be able to get the deciding vote. Therefore E doesn't want to get into this situation.
Hint 3/3: Working backwards, what should C offer to D and E?
Answer: Ok, so hopefully you've had a think about the hints. When it gets down to only D and E, E will end up with nothing. So for the three pirate version, C could offer [99,0,1] to [C,D,E]. D wouldn't vote for it, but E would get a 1 more coin than they would if they voted to throw C overboard. Therefore E will vote for it, which means it goes through.
The situation for B, C, D and E gets a bit more complicated. D knows that they won't get anything if they vote to throw B overboard, so they can be bought with a coin. Therefore [99,0,1,0] will work because the proposer wins in the case of a tie. However we should just check that no other distribution works. Offering C anything won't be able to compete with the 99 that C gave themselves in the 3 person game, so that line isn't worth pursuing.
What about [99,0,0,1]? This looks tempting for pirate E because they would receive 1 gold coin whichever way they vote. Either immediately or when C proposes their offer. However if you check back to rule 3: pirates are bloodthirsty: E would prefer to see someone thrown overboard when all else is equal. Therefore E won't go for this deal.
Ok, now for the full thing. A should offer the deal [98,0,1,0,1]. Notice that in B's best proposal neither C nor E received anything and so both stand to gain 1 gold coin by accepting the captain's proposal. Thus A has bought enough votes while keeping the majority of coins for xemself. Savvy?
*Why are there so many conflicting gender neutral pronouns? Here's a list of English language ones on wikipedia. I suspect the answer is the same reasoning highlighted in this XKCD comic.