You have 1000 pirates, who are all extremely greedy, heartless, and perfectly rational. They're also aware that all the other pirates share these characteristics. They're all ranked by the order in which they joined the group, from pirate one down to a thousand.

They've stumbled across a huge horde of treasure, and they have to decide how to split it up. Every day they will vote to either kill the lowest ranking pirate, or split the treasure up among the surviving pirates. If 50% or more of them vote to split it, the treasure gets split. Otherwise, they kill the lowest ranking pirate and repeat the process until half or more of the pirates decide to split the treasure.

The question, of course, is at what point will the treasure be split, and what will the precise vote be?

After that, consider solving the problem when a two-thirds or three-fourths majority is required. Try to generalize the result.

(In reply to Power of the supermajority (spoiler) by Steve Herman)

 (As a practical matter, it is hard to believe that the first 744 pirates will not figure this out and stage a mutiny on day 1, instead of letting themselves get killed off one day at a time.  The out-of-luck 744 outnumber the top 256 by almost 3 to 1.)

Exactly. I think this undermines the difficulty with this whole approach, given that the pirates are supposedly 'rational', and the outcome 'receive no treasure and die' is demonstrably worse than 'receive less than x treasure'. The true rule is masked by the first example (50-50 split, where the analysis is correct, as far as it goes) and is not a 'power of 2 rule' but an 'is the number of pirates who are otherwise guaranteed death equal to the number of those who take' rule. In this alternative, each pirate plays out the initial scenario mentally and then adjusts his behaviour accordingly. I don't think there's any alternative but to reiterate the mental process repeatedly until a stable result is obtained; something that may require repeated iterations in some circumstances.

Incidentally, for a yet further variant on the same theme, see http://omohundro.files.wordpress.com/2009/03/stewart99_a_puzzle_for_pirates.pdf

Edited on April 21, 2013, 2:11 am

Posted by broll on 2013-04-21 01:59:55