How do you use backward induction to solve sequential games?

1 What is a sequential game?

A sequential game is a game where the players move in a predetermined order, and each player observes the previous moves before making their own. A sequential game can be represented by a game tree, which shows the possible actions and payoffs at each node. A node is a point where a player has to choose an action, and a branch is a line that connects nodes. A terminal node is a node where the game ends and the payoffs are determined.

2 What is backward induction?

Backward induction is a method of solving sequential games by starting from the end of the game tree and working backwards. The idea is to find the optimal action for each player at each node, assuming that the players are rational and will choose the action that maximizes their payoff. To do this, you need to compare the payoffs of each branch and eliminate the ones that are dominated by another branch. A branch is dominated if it leads to a lower payoff than another branch, regardless of what the other players do.

3 How to apply backward induction?

To apply backward induction, you must first identify the terminal nodes and their payoffs for each player. Then, move to the previous node and determine the optimal action for the player who moves at that node, by selecting the branch that yields the highest payoff. Continue this process until you reach the first node of the game tree, and ascertain the optimal action for the first player. Finally, trace the optimal actions along the game tree to identify the equilibrium outcome - a combination of actions and payoffs derived from backward induction.

4 Example: The ultimatum game

The ultimatum game is a sequential game that illustrates backward induction. It involves two players, A and B, who must divide a fixed amount of money, say $10. Player A moves first and proposes a split, for example $7 for A and $3 for B. Player B then accepts or rejects the proposal. If B accepts, the game ends with the players getting their shares. If B rejects, both players get nothing. By using backward induction, we can solve this game by determining the terminal nodes - acceptance or rejection by B - with payoffs of ($7, $3) or ($0, $0) respectively. Knowing that B will accept any positive offer from A, even if it is unfair, A will choose the lowest possible offer - $1 for B and $9 for A - for the equilibrium outcome of ($9, $1).

5 Example: The centipede game

The centipede game is a complex sequential game with two players, A and B, taking turns to decide whether to take or pass a pot of money which starts with $2 and doubles each time it is passed. If one player takes the pot, the game ends and that player gets the pot while the other gets nothing. If both players pass, they split the pot equally. By using backward induction, we can solve this game. The terminal nodes are either taking or passing by A or B, with payoffs that depend on the size of the pot. Assuming both players are rational and prefer more money to less, they will always take the pot if it is larger than the expected payoff from passing. Moving to the previous node, A or B must choose between taking or passing. Working through this process until we reach the first node, we find that A will always take the pot at the first node as it is larger than zero, which is the expected payoff from passing. Thus, the equilibrium outcome is ($2, $0), where A takes the pot at the first node and B gets nothing.

6 Example: The prisoner's dilemma

The prisoner's dilemma is a famous sequential game that demonstrates how rational players can end up in a worse outcome than if they cooperated. It involves two players, A and B, who are arrested for a crime and interrogated separately. Each player can either confess or remain silent. If both players remain silent, they get a light sentence of one year each. If both players confess, they get a heavy sentence of five years each. If one player confesses and the other remains silent, the confessor gets a reward of zero years and the silent player gets a punishment of ten years. Analyzing the game using backward induction reveals that the equilibrium outcome is (-5, -5), where both players confess and get five years each. This is because both players are rational and prefer less prison time to more, so they will always confess if it reduces their prison time or keeps it the same. Knowing that B will always confess, A will also confess, because it keeps A's prison time at five years instead of increasing it to ten years.

7 Here’s what else to consider

This is a space to share examples, stories, or insights that don’t fit into any of the previous sections. What else would you like to add?