Pirate game

Simple mathematical game

For other uses, see Pirate (disambiguation) § Games and toys.

This article relies largely or entirely on a single source. Relevant discussion may be found on the talk page. Please help improve this article by introducing citations to additional sources.
Find sources: "Pirate game" – news · newspapers · books · scholar · JSTOR (January 2013)

|

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

## The game

[edit]

There are five rational pirates (in strict decreasing 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:

1. Each pirate wants to survive.
2. Given survival, each pirate wants to maximize the number of gold coins he receives.
3. Each pirate would prefer to throw another overboard, if all other results would otherwise be equal.[2]
4. 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

[edit]

To increase the chance of their plan being accepted, one might expect that Pirate A will have to offer the other pirates most of the gold. However, this is far from the theoretical result. When each of the pirates votes, they will not just be thinking about the current proposal, but also other outcomes down the line. In addition, the order of seniority is known in advance so each of them can accurately predict how the others might vote in any scenario. This becomes apparent if we work backwards.

The final possible scenario would have all the pirates except D and E thrown overboard. Since D is senior to E, they have the casting vote; so, D would propose to keep 100 for themself and 0 for E.

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 one coin in this round to win E's vote. Therefore, when only three are left the allocation is C:99, D:0, E:1.

If B, C, D and E remain, B can offer 1 to D; because B has the casting vote, only D's vote is required. Thus, B proposes B:99, C:0, D:1, E:0.

(In the previous round, 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.)

With this knowledge, 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]

(Note: 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

[edit]

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 they will choose, any choice is equally good and they 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 pirate M will have the vote of all the pirates from M/2 + 1 to M out of self preservation since their survival is secured only with the survival of the pirate M. 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. For instance, with 100 gold pieces and 500 pirates, pirates #500 through #457 die, and then #456 survives (as 456 = 200 + 28) as they have the 128 guaranteed self-preservation votes of pirates #329 through #456, plus 100 votes from the pirates they bribe, making up the 228 votes that they need. The numbers of pirates past #200 who can guarantee their survival as captain with 100 gold pieces are #201, #202, #204, #208, #216, #232, #264, #328, #456, #712, etc.: they are separated by longer and longer strings of pirates who are doomed no matter what division they propose.

## See also

[edit]

* Creative problem solving
* Lateral thinking

## Notes

[edit]

1. ^ 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.
2. ^ a b c Stewart, Ian (May 1999), "A Puzzle for Pirates" (PDF), Scientific American, vol. 280, no. 5, pp. 98–99, Bibcode:1999SciAm.280e..98S, doi:10.1038/scientificamerican0599-98

## References

[edit]

* 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.

* v
* t
* e

Game theory

* Glossary
* Game theorists
* Games

Traditional Game Theory

| Definitions|

* Asynchrony
* Bayesian regret
* Best response
* Bounded rationality
* Cheap talk
* Coalition
* Complete contract
* Complete information
* Complete mixing
* Confrontation analysis
* Conjectural variation
* Contingent cooperator
* Coopetition
* Cooperative game theory
* Dynamic inconsistency
* Escalation of commitment
* Farsightedness
* Game semantics
* Hierarchy of beliefs
* Imperfect information
* Incomplete information
* Information set
* Move by nature
* Mutual knowledge
* Non-cooperative game theory
* Non-credible threat
* Outcome
* Perfect information
* Perfect recall
* Ply
* Preference
* Rationality
* Sequential game
* Simultaneous action selection
* Spite
* Strategic complements
* Strategic dominance
* Strategic form
* Strategic interaction
* Strategic move
* Strategy
* Subgame
* Succinct game
* Topological game
* Tragedy of the commons
* Uncorrelated asymmetry

|

Equilibrium Concepts|

* Backward induction
* Bayes correlated equilibrium
* Bayesian efficiency
* Bayesian game
* Bayesian Nash equilibrium
* Berge equilibrium
* Bertrand–Edgeworth model
* Coalition-proof Nash equilibrium
* Core
* Correlated equilibrium
* Edgeworth price cycle
* Epsilon-equilibrium
* Gibbs equilibrium
* Incomplete contracts
* Inequity aversion
* Individual rationality
* Iterated elimination of dominated strategies
* Markov perfect equilibrium
* Mertens-stable equilibrium
* Nash equilibrium
* Open-loop model
* Pareto efficiency
* Payoff dominance
* Perfect Bayesian equilibrium
* Price of anarchy
* Program equilibrium
* Proper equilibrium
* Quantal response equilibrium
* Quasi-perfect equilibrium
* Rational agent
* Rationalizability
* Rationalizable strategy
* Satisfaction equilibrium
* Self-confirming equilibrium
* Sequential equilibrium
* Shapley value
* Strong Nash equilibrium
* Subgame perfect equilibrium
* Trembling hand equilibrium

Strategies|

* Appeasement
* Bid shading
* Cheap talk
* Collusion
* Commitment device
* De-escalation
* Deterrence
* Escalation
* Fictitious play
* Focal point
* Grim trigger
* Hobbesian trap
* Markov strategy
* Max-dominated strategy
* Mixed strategy
* Pure strategy
* Tit for tat
* Win–stay, lose–switch

Games|

* All-pay auction
* Battle of the sexes
* Nash bargaining game
* Bertrand competition
* Blotto game
* Centipede game
* Coordination game
* Cournot competition
* Deadlock
* Dictator game
* Trust game
* Diner's dilemma
* Dollar auction
* El Farol Bar problem
* Electronic mail game
* Gift-exchange game
* Guess 2/3 of the average
* Keynesian beauty contest
* Kuhn poker
* Lewis signaling game
* Matching pennies
* Obligationes
* Optional prisoner's dilemma
* Pirate game
* Prisoner's dilemma
* Public goods game
* Rendezvous problem
* Rock paper scissors
* Stackelberg competition
* Stag hunt
* Traveler's dilemma
* Ultimatum game
* Volunteer's dilemma
* War of attrition

Theorems|

* Arrow's impossibility theorem
* Aumann's agreement theorem
* Brouwer fixed-point theorem
* Competitive altruism
* Folk theorem
* Gibbard–Satterthwaite theorem
* Gibbs lemma
* Glicksberg's theorem
* Kakutani fixed-point theorem
* Kuhn's theorem
* One-shot deviation principle
* Prim–Read theory
* Rational ignorance
* Rational irrationality
* Sperner's lemma
* Zermelo's theorem

Subfields|

* Algorithmic game theory
* Behavioral game theory
* Behavioral strategy
* Compositional game theory
* Contract theory
* Drama theory
* Graphical game theory
* Heresthetic
* Mean-field game theory
* Negotiation theory
* Quantum game theory
* Social software

Key Figures|

* Albert W. Tucker
* Alvin E. Roth
* Amos Tversky
* Antoine Augustin Cournot
* Ariel Rubinstein
* David Gale
* David K. Levine
* David M. Kreps
* Donald B. Gillies
* Drew Fudenberg
* Eric Maskin
* Harold W. Kuhn
* Herbert Simon
* Herbert Scarf
* Hervé Moulin
* Jean Tirole
* Jean-François Mertens
* Jennifer Tour Chayes
* Ken Binmore
* Kenneth Arrow
* Leonid Hurwicz
* Lloyd Shapley
* Martin Shubik
* Melvin Dresher
* Merrill M. Flood
* Olga Bondareva
* Oskar Morgenstern
* Paul Milgrom
* Peyton Young
* Reinhard Selten
* Robert Aumann
* Robert Axelrod
* Robert B. Wilson
* Roger Myerson
* Samuel Bowles
* Suzanne Scotchmer
* Thomas Schelling
* William Vickrey

Combinatorial Game Theory

| Core Concepts|

* Combinatorial explosion
* Determinacy
* Disjunctive sum
* First-player and second-player win
* Game complexity
* Game tree
* Impartial game
* Misère
* Partisan game
* Solved game
* Sprague–Grundy theorem
* Strategy-stealing argument
* Zugzwang

|

Games|

* Chess
* Chomp
* Clobber
* Cram
* Domineering
* Hackenbush
* Nim
* Notakto
* Subtract a square
* Sylver coinage
* Toads and Frogs

Mathematical Tools|

* Mex
* Nimber
* On Numbers and Games
* Star
* Surreal number
* Winning Ways for Your Mathematical Plays

Search Algorithms|

* Alpha–beta pruning
* Expectiminimax
* Minimax
* Monte Carlo tree search
* Negamax
* Paranoid algorithm
* Principal variation search

Key Figures|

* Claude Shannon
* John Conway
* John von Neumann

Evolutionary Game Theory

| Core Concepts|

* Bishop–Cannings theorem
* Evolution and the Theory of Games
* Evolutionarily stable set
* Evolutionarily stable state
* Evolutionarily stable strategy
* Replicator equation
* Risk dominance
* Stochastically stable equilibrium
* Weak evolutionarily stable strategy

|

Games|

* Chicken
* Stag hunt

Applications|

* Cultural group selection
* Fisher's principle
* Mobbing
* Terminal investment hypothesis

Key Figures|

* John Maynard Smith
* Robert Axelrod

Mechanism design

| Core Concepts|

* Algorithmic mechanism design
* Bayesian-optimal mechanism
* Incentive compatibility
* Market design
* Monotonicity
* Participation constraint
* Revelation principle
* Strategyproofness
* Vickrey–Clarke–Groves mechanism

|

Theorems|

* Myerson–Satterthwaite theorem
* Revenue equivalence

Applications|

* Digital goods auction
* Knapsack auction
* Truthful cake-cutting

Other Topics

* Bertrand paradox
* Chainstore paradox
* Computational complexity of games
* Helly metric
* Multi-agent system
* PPAD-complete

* Category
* Mathematics portal
* Commons
* WikiProject

*[v]: View this template
*[t]: Discuss this template
*[e]: Edit this template