Sequential Take-Away Game

• Content map: SMU H3 Game Theory Map

Setup

Definition:

Sequential Take-Away Game

• Players: Player 1 and Player 2.
• Strategies: On each turn, remove 1, 2, or 3 objects.
• Rules: Start with $21$ objects; players alternate moves and the player who removes the last object wins.

Decision Table

\setlength{\tabcolsep}{18pt} \renewcommand{\arraystretch}{1.5} No. of Objects Left & Optimal Choice \

$1,2,3$ & Win: take all \ $4$ & Lose: any choice \ $5$ & take $1$ \ $6$ & take $2$ \ $7$ & take $3$ \ … & … \ $17$ & take $1$ \ $18$ & take $2$ \ $19$ & take $3$ \ $20$ & Lose: any choice \ $21$ & take $1$

Derivation (Backward Induction)

• Starting from the end state of $1,2,3$, the player is winning for the player.
• The positions $0,4,8,12,16,20$ are losing for the player.
• From any non-multiple of $4$, a player can move to the nearest lower multiple of $4$.

Winning Strategy

• First move: remove $1$ to leave $20$.
• Thereafter: if the opponent removes $x\in\{1,2,3\}$, remove $4-x$ to restore a multiple of $4$.

Nash Equilibrium

Result:

The first player has a winning strategy: always leave a multiple of $4$ to the opponent.

Insights

Insight:

The game is solved by identifying a winning invariant (here: leaving multiples of $4$). This is a standard backward-induction pattern in take-away games.