|This article relies largely or entirely upon a single source. (January 2013)|
The pirate game is a simple mathematical game. It illustrates how, if assumptions conforming to a homo economicus model of human behaviour hold, outcomes may be surprising. It is a multi-player version of the ultimatum game.
There are 5 rational pirates, A, B, C, D and E. They find 100 gold coins. They must decide how to distribute them.
The pirates have a strict order of seniority: A is superior to B, who is superior to C, who is superior to D, who is superior to E.
The pirate world's rules of distribution are thus: that the most senior pirate should propose a distribution of coins. The pirates, including the proposer, then vote on whether to accept this distribution. In case of a tie vote the proposer has the casting vote. If the distribution is accepted, the coins are disbursed and the game ends. If not, the proposer is thrown overboard from the pirate ship and dies, and the next most senior pirate makes a new proposal to begin the system again.
Pirates base their decisions on three factors. First of all, each pirate wants to survive. Second, given survival, each pirate wants to maximize the number of gold coins each receives. Third, each pirate would prefer to throw another overboard, if all other results would otherwise be equal. The pirates do not trust each other, and will neither make nor honor any promises between pirates apart from a proposed distribution plan that gives a whole number of gold coins to each pirate.
It might be expected intuitively that Pirate A will have to allocate little if any to A for fear of being voted off so that there are fewer pirates to share between. However, this is quite far from the theoretical result.
This is apparent if we work backwards: if all except D and E have been thrown overboard, D proposes 100 for D and 0 for E. D has the casting vote, and so this is the allocation.
If there are three left (C, D and E) C knows that D will offer E 0 in the next round; therefore, C has to offer E 1 coin in this round to win E's vote, and get C's allocation through. Therefore, when only three are left the allocation is C:99, D:0, E:1.
If B, C, D and E remain, B considers being thrown overboard when deciding. To avoid being thrown overboard, B can simply offer 1 to D. Because B has the casting vote, the support only by D is sufficient. Thus B proposes B:99, C:0, D:1, E:0. One might consider proposing B:99, C:0, D:0, E:1, as E knows it won't be possible to get more coins, if any, if E throws B overboard. But, as each pirate is eager to throw each other overboard, E would prefer to kill B, to get the same amount of gold from C.
Assuming A knows all these things, A can count on C and E's support for the following allocation, which is the final solution:
- A: 98 coins
- B: 0 coins
- C: 1 coin
- D: 0 coins
- E: 1 coin
Also, A:98, B:0, C:0, D:1, E:1 or other variants are not good enough, as D would rather throw A overboard to get the same amount of gold from B.
The solution follows the same general pattern for other numbers of pirates and/or coins, however the game changes in character when it is extended beyond there being twice as many pirates as there are coins. Ian Stewart wrote about Steve Omohundro's extension to an arbitrary number of pirates in the May 1999 edition of Scientific American and described the rather intricate pattern that emerges in the solution.
Supposing there are just 100 gold pieces, then:
- Pirate #201 as captain can stay alive only by offering all the gold to odd-numbered pirates, keeping none.
- Pirate #202 as captain can stay alive only by offering all the gold to even-numbered pirates, keeping none.
- Pirate #203 as captain will not have enough gold available to bribe a majority, and so will die.
- Pirate #204 as captain has #203's vote secured without bribes: #203 will only survive if #204 also survives. So #204 is safe by making the same offer as #201 would make, bribing the first 100 odd-numbered pirates, who will get nothing from #202 if #204 and #203 both die.
- Because #204 is safe, #203 doesn't care if #205 dies, so #205 is doomed as captain, and likewise #206 and #207.
- The votes of self-preservation from #205, #206, and #207 are enough to ensure the safety of #208, #208 makes the same offer as #202 would make, bribing the first 100 even-numbered pirates, who will get nothing from #204 if #208 to #205 all die.
In general, if G is the number of gold pieces and N (> 2G) is the number of pirates, then no pirate whose number exceeds 2G can expect any gold. Further:
- All pirates whose number is less than or equal to 2G + M will survive, where M is the highest power of 2 that does not exceed N – 2G.
- Any pirates whose number exceeds 2G + M will die.
- The gold will go to those of the first 2G pirates whose numbers have the opposite parity to log2 M (that is, the odd numbers if M is an even power of 2; the even numbers if M is an odd power of 2).
Another way to see this is to realize that every Mth pirate will have the vote of all the pirates from M/2 to M out of self preservation, and will lose the vote of every pirate from 2G to M/2, since their survival is secured with the survival of the M/2th pirate. Because the highest ranking pirate can break the tie, the captain only needs the votes of half of the pirates over 2G, which happens at every power of 2 from 2G onwards.
The pattern starts to break down at 2G+1, which is the first time the lead pirate does not award himself gold. At 2G+2 it can no longer be determined which pirates get gold (although the first G odd-numbered will not get any). At 2G+3, the lead pirate is the first to expire. After that, for those pirates which survive, the leading pirates get nothing, and the gold is randomly distributed amongst the rest in ones.
This can be seen by analysing some sequences. In the following diagrams
- Rounds are analysed backward. Pirate 6 in round 6 needs to know what will happen in round 5 if he dies, so he can tailor the proposal accordingly. Thus we need to start at round 1 with just pirate 1, and progress from there. In each round the lead pirate looks at what will happen in the 'next' round - ie the round where he is dead.
- If the new lead pirate cannot survive this 'next' round, the process continues until a round where the lead pirate survives and gold is allocated exists.
- A round where gold is allocated is a 'survival round'
- The 'next' survival round is the closest survival round with fewer pirates than the current round
- Each line is a new round, with one more pirate than the 'previous' round (although in 'real life' the rounds would play in the opposite direction).
- Round Z is the round with Z pirates and is denoted as RZ:
- The lead pirate is to the right, and is the pirate with the highest number
- A number underneath the pirate's column means a pirate gets exactly that amount of gold - eg, 0, 1, 2, etc
- A dot means the gold is allocated randomly 1G at a time to the dotted pirates. Each pirate gets at most 1G.
- An X means the lead pirate cannot secure enough votes and dies
- A pirates vote will be secured if he gets more gold in this round than the next survival round
- A pirates vote will also be secured if he would otherwise die before the next survival round
G=1 1 2 3 4 5 6 7 8 9 10 <- Pirates R1: 1 R2: 0 1 R3: 1 0 0 2G+1 R4: 0 . . 0 2G+2 R5: X X X X X X 2G+3 R6: . . . . 0 0 R7: X X X X X X X R8: X X X X X X X X R9: X X X X X X X X X R10: . . . . . . 0 0 0 0
In the third round the lead pirate needs two votes. He has his own vote. He cannot give the gold to pirate 2, because that pirate will also get 1G in the next survival round (by allocating it to himself). He can give the gold to pirate 1, because that pirate gets 0G in the next survival round.
In the fourth round the lead pirate needs two votes. He has his own vote, and must survive by getting the vote of any other pirate. There were two pirates who got 0 gold the previous round, pirates 2 and 3, so he can give the gold to either one of those to secure their vote (illustrated by a dot). They have a 50% chance of getting 1G.
In the fifth round the lead pirate dies.
In the sixth round the lead pirate has his own vote and the vote of the fifth pirate who would otherwise die. He needs one more vote, but can get this by giving the gold to any pirate who did not have gold the previous survival round (round 4). This will be pirates 1 and 4, who got 0 gold previously, but will also be pirates 2 and 3, who each only had a 50% chance of gold. The certainty of getting 1G is better than a 50% chance of getting 1G, so whoever the lead pirate gives the gold to, this will secure their vote - "1G in the hand is worth 50% chance of 1G in the bush". Thus the lead pirate can give the gold to any of pirates 1-4, who will each have 25% chance of being assigned the gold.
Here are the sequences for G=2 and G=3
G=2 2 0 2 1 0 1 0 1 0 1 1 0 1 0 0 2G+1 0 . 0 . . 0 2G+2 X X X X X X X . . . . . . 0 0
G=3 3 0 3 1 0 2 0 1 0 2 1 0 1 0 1 0 1 0 1 0 1 1 0 1 0 1 0 0 0 . 0 . 0 . . 0 X X X X X X X X X . . . . . . . . 0 0
- Bruce Talbot Coram (1998). Robert E. Goodin, ed. The Theory of Institutional Design (Paperback ed.). Cambridge University Press. pp. 99–100. ISBN 978-0-521-63643-8.
- Stewart, Ian (May 1999), "A Puzzle for Pirates" (PDF), Scientific American: 98–99
- Robert E. Goodin, ed. (1998). "Chapter 3: Second best theories". The Theory of Institutional Design. Cambridge University Press. pp. 90–102. ISBN 978-0-521-63643-8.