Pirate game

The pirate game is a simple mathematical game. It is a multi-player version of the ultimatum game.

The game

There are 5 rational pirates (in strict order of seniority A, B, C, D and E) who found 100 gold coins. They must decide how to distribute them.

The pirate world's rules of distribution say that the most senior pirate first proposes a plan of distribution. The pirates, including the proposer, then vote on whether to accept this distribution. If the majority accepts the plan, the coins are disbursed and the game ends. In case of a tie vote, the proposer has the casting vote. If the majority rejects the plan, 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. The process repeats until a plan is accepted or if there is one pirate left.^[1]

Pirates base their decisions on four 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.^[2] And finally, 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.

The result

It might be expected intuitively that Pirate A will have to offer the other pirates with most of the gold to increase the chances of his plan being accepted. However, this is quite far from the theoretical result. When each of the pirates votes they won't just be thinking about the current proposal, but all other outcomes down the line. Also because the order of seniority is known in advance, each of them can accurately predict how the others might vote in any scenario.

This is apparent if we work backwards. The last possible scenario would have all the pirates except D and E thrown overboard. Since D is senior to E, he has the casting vote. So D would obviously propose to keep 100 for himself and 0 for E, 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 the others 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^[2]

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.

Extension

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.^[2]

Supposing there are just 100 gold pieces, then:

Pirate #201 as captain can stay alive only by offering all the gold one each to the lowest odd-numbered pirates, keeping none.
Pirate #202 as captain can stay alive only by taking no gold and offering one gold each to 100 pirates who would not receive a gold coin from #201. Therefore, there are 101 possible recipients of these one gold coin bribes being the 100 even-numbered pirates up to 200 and number #201. Since there are no constraints as to which 100 of these 101 he will choose, any choice is equally good and he can be thought of as choosing at random. This is how chance begins to enter the considerations for higher-numbered pirates.
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 can remain safe by reaching 102 votes by bribing 100 pirates with one gold coin each. This seems most likely to work by bribing odd-numbered pirates optionally including #202, who will get nothing from #203. However, it may also be possible to bribe others instead as they only have a 100/101 chance of being offered a gold coin by pirate #202.
With 205 pirates, all pirates bar #205 prefer to kill #205 unless given gold, so #205 is doomed as captain.
Similarly with 206 or 207 pirates, only votes of #205 to #206/7 are secured without gold which is insufficient votes, so #206 and #207 are also doomed.
For 208 pirates, the votes of self-preservation from #205, #206, and #207 without any gold are enough to allow #208 to reach 104 votes and survive.

In general, if G is the number of gold pieces and N (> 2G) is the number of pirates, then

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.
Any pirate whose number is greater than 2G + M/2 will receive no gold.
There is no unique solution as to who gets one gold coin and who does not if the number of pirates is 2G+2 or greater. A simple solution dishes out one gold to the odd or even pirates up to 2G depending whether M is an even or odd power of 2.

Another way to see this is to realize that every M^th pirate will have the vote of all the pirates from M/2 to M out of self preservation since their survival is secured only with the survival of the Mth pirate. Because the highest ranking pirate can break the tie, the captain only needs the votes of half of the pirates over 2G, which only happens each time (2G + a Power of 2) is reached.

Notes

↑ 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.
1 2 3 Stewart, Ian (May 1999), "A Puzzle for Pirates" (PDF), Scientific American, pp. 98–99

References

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.

Topics in game theory
Definitions	Normal-form game Extensive-form game Escalation of commitment Graphical game Cooperative game Succinct game Information set Hierarchy of beliefs Preference
Equilibrium concepts	Nash equilibrium Subgame perfection Mertens-stable equilibrium Bayesian Nash equilibrium Perfect Bayesian equilibrium Trembling hand Proper equilibrium Epsilon-equilibrium Correlated equilibrium Sequential equilibrium Quasi-perfect equilibrium Evolutionarily stable strategy Risk dominance Core Shapley value Pareto efficiency Gibbs equilibrium Quantal response equilibrium Self-confirming equilibrium Strong Nash equilibrium Markov perfect equilibrium
Strategies	Dominant strategies Pure strategy Mixed strategy Tit for tat Grim trigger Collusion Backward induction Forward induction Markov strategy
Classes of games	Symmetric game Perfect information Simultaneous game Sequential game Repeated game Signaling game Screening game Cheap talk Zero-sum game Mechanism design Bargaining problem Stochastic game n-player game Large Poisson game Nontransitive game Global game Strictly determined game Potential game
Games	Prisoner's dilemma Optional prisoner's dilemma Traveler's dilemma Coordination game Chicken Centipede game Volunteer's dilemma Dollar auction Battle of the sexes Stag hunt Matching pennies Ultimatum game Rock–paper–scissors Pirate game Dictator game Public goods game Blotto game War of attrition El Farol Bar problem Fair division Fair cake-cutting Cournot game Deadlock Diner's dilemma Guess 2/3 of the average Kuhn poker Nash bargaining game Prisoners and hats puzzle Trust game Princess and Monster game Rendezvous problem
Theorems	Minimax theorem Nash's theorem Purification theorem Folk theorem Revelation principle Arrow's impossibility theorem
Key figures	Albert W. Tucker Amos Tversky Ariel Rubinstein Daniel Kahneman David K. Levine David M. Kreps Donald B. Gillies Drew Fudenberg Eric Maskin Harold W. Kuhn Herbert Simon Hervé Moulin Jean Tirole Jean-François Mertens John Harsanyi John Maynard Smith Antoine Augustin Cournot John Nash John von Neumann Kenneth Arrow Kenneth Binmore Leonid Hurwicz Lloyd Shapley Melvin Dresher Merrill M. Flood Oskar Morgenstern Paul Milgrom Peyton Young Reinhard Selten Robert Axelrod Robert Aumann Robert B. Wilson Roger Myerson Samuel Bowles Thomas Schelling William Vickrey
See also	All-pay auction Alpha–beta pruning Bertrand paradox Bounded rationality Combinatorial game theory Confrontation analysis Coopetition List of game theorists List of games in game theory No-win situation Topological game Tragedy of the commons Tyranny of small decisions

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.