Introduction

Game theory is a branch of mathematics concerned with the analysis of strategies for dealing with competitive situations. Game theory is typically concerned with the process of modeling the strategic interaction between two or more players in a situation containing a set of rules and outcomes, such as a board game. It is used in a number of disciplines, most notably in economics, where game theory can be used as a tool for financial analysis.

There are many different types of games that can be analyzed mathematically using game theory. In this lesson, we will talk about a specific thinking tool used commonly in game theory to derive the most optimal strategy called backwards induction.

Here is some general terminology commonly used in game theory.

Game: Any set of circumstances that has a result dependent on the actions of two or more decision makers (players).

Players: A strategic decision-maker within the context of the game.

Strategy: A complete plan of action a player will take given the set of circumstances that might arise within the game.

Win Condition: The state of the game that directly leads to a player winning the game (such as a checkmate in chess).

Loss Condition: The state of the game that directly leads to a player losing the game.

Winning Strategy: The strategy a player can follow to guarantee winning the game.

Payoff: The resources gained by a player when the game (or one round of the game) ends.

Game of Rooks

This $2$-player turn-based game is played on an $8\times 8$ board. The game starts off with a rook on the bottom-right corner of the board. A rook piece can move in a single, non-diagonal direction toward the top-left corner (up or to the left, but not right nor down) for any number of squares in one turn. The objective is to move the rook to the opposite corner of the board from where it started. Player $1$ moves the rook first, then player $2$ moves the rook, and the turns alternate between the two players. The player that successfully moves the rook to the opposite corner (the green square below) is the winner.

Let us illustrate a potential first two moves of a game. In this example, player $1$ might make the following move.

From this state of the game, the potential squares that player $2$ can move the rook to are highlighted in blue. Notice that the rook cannot move diagonally, to the right, nor down.

Suppose player $2$ makes the following move.

After this, it is once again player $1$’s turn to move the rook from its current position. The game continues until the rook is moved onto the green square.

Before reading further, try playing this game with an opponent, and alternate between being player $1$ and player $2$. Is there a winning strategy? Is it better to be player $1$ or player $2$?

Let us take a look at the win condition for this game. (The squares are labeled so we can clearly refer to each square.) Suppose the current game state is as follows (with the rook on the square b$7$), and it was your turn to play next. Can you win this game?

The answer is no. No matter if you move up or to the left for one square, your opponent will be able to move the rook onto the winning square. Hence, the square b$7$ is a win condition if you are able to move the rook there and force your opponent to make a move from this game state. Thus, b$7$ becomes a winning square just like the square a$8$.

Continuing this pattern, if you are able to move the rook onto c$6$, you will also secure the win condition.

This thought process can be traced back all the way to the beginning of the game. We can see that every diagonal square is a win condition if you are able to move the rook there.

If we assume both players know this winning strategy, in order to guarantee the win, you need to start the game as player $2$, since it is impossible for player $1$ to move the rook onto one of the winning squares. To answer the question we posed at the beginning: player $2$ has the winning strategy in the game, and the winning strategy is to always move the rook onto one of the diagonal squares until they are able to move the rook onto the winning square, a$8$.

This method of deductive reasoning is called backwards induction, where you start from the “end of the game” and retrace the steps that lead to that particular ending. In this case, we were concerned with finding the winning strategy.

Logic Coin Game

This logic coin game is another $2$-player turn-based strategy game in which two players take turns removing coins from an initial pile of coins. There are many variations on the rules of the game, and we will adhere to the rules below.

There are $25$ coins in a coin pile. The players take turns removing coins from the pile. On each turn, a player can remove $1$, $2$, or $3$ coins. The player that takes the last coin wins.

Before reading any further, try playing this game with an opponent, or head to this geogebra page and set the number of coins in the pile to $25$ to play the game. Can you use backwards induction to deduce the winning strategy?

Suppose there are $4$ coins left in the pile, and it is your opponent’s turn. In this scenario, it is impossible for your opponent to win. Since the win condition is to take the last coin, if your opponent:

• Takes $1$ coin, you can take $3$ coins and win.

• Takes $2$ coins, you can take $2$ coins and win.

• Takes $3$ coins, you can take $1$ coin and win.

Therefore, if you can leave your opponent with $4$ coins remaining in the pile after your turn (by taking the $5$^th last coin and no more than that), you have secured the win condition.

Using this logic, taking the $5$^th last coin is the same as taking the last coin, where you can guarantee victory.

How do you make sure you can take the $5$^th last coin? Using a similar thought process as above, if you leave your opponent with $8$ coins, you can guarantee that you can take the $5$^th last coin. If your opponent:

• Takes $1$ coin, you can take $3$ coins to bring the pile down to $4$ coins.

• Takes $2$ coins, you can take $2$ coins to bring the pile down to $4$ coins.

• Takes $3$ coins, you can take $1$ coin to bring the pile down to $4$ coins.

Continuing this pattern, leaving your opponent with $8$, $12$, $16$, $20$, or $24$ coins are also win conditions.

Notice that $4$, $8$, $12$, $16$, $20$, and $24$ are all multiples of $4$. This is important and related to the possible number of coins a player can remove on any given turn. The winning strategy for this game is to make the number of remaining coins a multiple of $4$ after your turn, and you can accomplish that by taking the $1$^st coin as player $1$ (leaving $24$ coins remaining in the pile), then matching the coins you remove with your opponent as follows.

• If your opponent takes $1$ coin, you take $3$ coins.

• If your opponent takes $2$ coins, you take $2$ coins.

• If your opponent takes $3$ coins, you take $1$ coin.

Here is an example game played by two players. Each row shows the number of coins that each player removes, as well as the remaining coins in the pile. We can see that even if both players know the strategy, player $1$ is guaranteed to win. All player $1$ needs to do on the first turn is to take $1$ coin, and then on the subsequent turns, bring the remaining coin pile to a multiple of $4$.

The logic coin game works exactly the same way as the game of rooks we played earlier, although they look very different. Leaving the opponent to play from a diagonal square is essentially the same as leaving the opponent with a coin pile that is a multiple of $4$. Both of these strategies are possible because of the restriction on the possible moves during one turn - whether it is moving the rook in a single direction toward the opposite corner, or how many coins you are able to remove.

A Game With Pirates

There once were a group of $5$ pirates that found $100$ gold coins. These pirates are very rational and think logically, and they also follow a strict order of seniority A, B, C, D, and E, where pirate A is more senior than pirate B, and so on. They must figure out how to distribute the $100$ gold coins among them.

In the world of pirates, the most senior pirate would propose a plan of distribution on how to split the coins. The pirates, including the proposer, then vote on whether or not to accept this distribution. If the majority accepts the plan, then the coins are distributed and the game ends. In case of a tie vote (if there are an even number of pirates), the proposer of the plan has the casting vote (a casting vote is essentially “one extra vote” that is used to break ties). If the majority rejects the plan, the proposer is thrown overboard from the pirate ship and dies, and the next most senior pirate can make a new proposal to be voted on again. This cycle continues until either a plan is accepted, or until there is only $1$ pirate (pirate E) left on the ship.

The pirates, being rational and intelligent, base their decisions on three factors.

• Survival is the top priority.

• Given that I survive, I want to maximize the number of gold coins distributed to me.

• If the payoffs (number of gold coins) I gain are equal whether I accept or reject the proposed plan, I would prefer to throw another pirate overboard by rejecting the proposal.

Suppose you were pirate A, the most senior of the pirates. What distribution plan would you propose?

You may be surprised to find out that the optimal coin distribution plan for pirate A is the following:

• A: $98$ coins

• B: $0$ coins

• C: $1$ coin

• D: $0$ coins

• E: $1$ coin

In order to arrive at this surprising result, we must first understand that based on the rules of the game, we can accurately predict how each pirate will vote in a particular scenario. Since the decision of each pirate casting a vote is directly tied to the payoff of the next scenario, we can use backwards induction once again, and work from the final possible scenario.

The final time that a vote would be cast is when all other pirates except D and E are thrown overboard. Since D is senior to E, D has the casting vote. In this scenario, D would simply propose to keep all $100$ coins to himself, since pirate E can do nothing to stop this proposal. The final payoff in this scenario would be D:$100$ and E:$0$.

If there are three pirates left (C, D, and E), pirate C can predict that the payoff would be the situation above if they get voted off, where pirate E will get $0$ coins. In order to win the majority vote, all pirate C needs to do is to give $1$ coin to pirate E and take the other $99$ coins for themselves. Pirate C knows that pirate E will not refuse this proposal, since $1$ coin is better than none. The final payoff in this scenario would be C:$99$, D:$0$, and E:$1$.

If there are four pirates left (B, C, D, and E), pirate B has the casting vote. Therefore, only one other vote is required for the proposal to pass. Therefore, pirate B should offer $1$ coin to pirate D, which is better than the $0$ coins D would receive in the next scenario. (Pirate B could offer $1$ coin to pirate E instead of pirate D since $1$ coin is all pirate E could hope to get, but based on the third decision factor, pirate E would prefer to throw pirate B overboard and obtain $1$ coin in the next scenario, so B should offer $1$ coin to D instead.) The final payoff in this scenario would be B:$99$, C:$0$, D:$1$, and E:$0$.

With all pirates having this knowledge, we have come to the current scenario. Looking at the payoff of the next scenario, all pirate A needs to do is to offer $1$ coin each to pirate C and pirate E, and gain the majority vote, which leads to the distribution plan above.