The Pirate Game and Generalized Backward Induction

0. The Pirate Game: A Study in Backward Induction

The Pirate Game is a famous puzzle in game theory that perfectly illustrates the concept of backward induction—solving a problem by working backward from the end to figure out the best strategy at the beginning.

The Setup

Imagine a ship with five pirates who have just found a treasure chest containing 100 gold coins. The pirates are strictly ranked by seniority:

A (the captain, most senior)
B, C, D, E (the cabin boy, least senior)

The Rules

The Proposal: The most senior pirate alive proposes a plan to divide the 100 gold coins.
The Vote: All remaining pirates vote. A tie (50% or more) goes to the proposer.
The Outcome: If the plan fails, the proposer is thrown overboard, and the next senior pirate takes over.

The Pirates’ Motivations

Survive: Above all else.
Maximize Gold: Second priority.
Be Ruthless: If the gold is equal, they prefer to throw the proposer overboard.

1. The 5-Pirate Solution (Backward Induction)

To find what A should propose, we work backward from the smallest possible crew:

2 Pirates (D, E): D needs 50% (1 vote). D takes 100, gives E 0. Result: (100, 0).
3 Pirates (C, D, E): C needs 2 votes. C needs one more vote besides their own. E gets 0 in the 2-pirate scenario, so C gives E 1 coin to secure a “Yes.” Result: (99, 0, 1).
4 Pirates (B, C, D, E): B needs 2 votes. B needs one more. D gets 0 in the 3-pirate scenario. B gives D 1 coin. Result: (99, 0, 1, 0).
5 Pirates (A, B, C, D, E): A needs 3 votes. A needs two more. C and E both get 0 in the 4-pirate scenario. A gives them 1 coin each.
- Final Proposal: A:98, B:0, C:1, D:0, E:1

2. The Generalized Solution

If we increase the number of pirates ( $n$ ) while keeping the coins ( $G = 100$ ) constant, a clear pattern emerges. The proposer always offers 1 coin to the pirates who would receive 0 in the $n-1$ scenario.

The Pattern of Allocation

The proposer needs $\lceil n/2 \rceil$ votes.
They keep $G - (\lceil n/2 \rceil - 1)$ coins.
They distribute 1 coin to $\lceil n/2 \rceil - 1$ pirates.
Because the pirates to whom they give coins alternate every round (those who got 0 last time), the specific “cheap” pirates are always those with the same parity as $n$ .

The Limits of Wealth ( $n \le 2G$ )

As long as the number of pirates is less than or equal to twice the number of coins ( $n \le 200$ ), the captain can always survive by buying enough votes with 1 coin each. At $n = 200$ , the captain gives 1 coin to 99 pirates, keeping 1 coin for themselves. At $n = 201$ , the captain gives away all 100 coins to 100 pirates and receives 0, but still survives because they get their own vote.

3. The Chaos Threshold ( $n > 2G + 1$ )

When the number of pirates exceeds $2G + 1$ (201 in this case), the captain can no longer buy enough votes to guarantee survival using gold alone. Survival now depends on the ruthlessness priority.

The Survival Intervals

For $n > 201$ , the pirates who get 0 gold will only vote “Yes” if their alternative is certain death. This creates a pattern based on powers of 2:

Pirate 202: Needs 101 votes. Can only offer 100 coins. They get 100 votes from gold-receivers + their own vote = 101. They survive with 0 gold.
Pirate 203: Needs 102 votes. Can offer 100 coins. However, if they die, Pirate 202 survives. Pirate 202 has no incentive to save 203. Pirate 203 dies.
Pirate 204: Needs 102 votes. They can offer 100 coins to 100 pirates. These 100 will vote yes. They also know that if 204 dies, 203 will also die (because 203 can’t pass a plan). Therefore, Pirate 203 will vote “Yes” to 204’s plan just to stay alive. 100 (gold) + 1 (203) + 1 (self) = 102. Pirate 204 survives.

The Law of Survival: A pirate in a massive crew ( $n > 201$ ) can only survive if $n - (201)$ is a power of 2.

Pirates at $202, 204, 208, 216, 256...$ can survive with 0 gold.
All pirates in between these numbers are inevitably thrown overboard, as they cannot assemble a 50% coalition even with the threat of death hanging over their subordinates.