Finding Nash Equilibrium in Games in the Extensive Form*

*technical note: to be technically correct when I say “Nash Equilibrium” here I actually refer to the so called Subgame Perfect Nash Equilibrium (SPNE) which we find by means of backward induction, and not “just a Nash equilibrium.” SPNE is the Nash Equilibrium which can be described as “most likely,” “most feasible,” or “best prediction equilibrium.” So when I ask you to find Nash equilibrium, I ask you to use backward induction to find the SPNE but you should be aware that there can be also other Nash equilibria (most of which are degenerate/not feasible).

Consider, for example, the following game in an extensive form:

GAME DESCRIPTION:

There are two players in the game: Player 1 and Player 2.

Player 1 has two possible actions A and B.

Player 2 also has two possible actions C and D (for both Player 1 choosing A and Player 1 choosing B).

Notice, that the moves are sequential: Player 1 moves first, Player 2 moves second – which implies that Player 2 will know Player 1’s choice (A or B).

The game has four final nodes – four outcomes – which are the result of different actions by players (A-C, A-D, B-C, and B-D). For example, if Player 1 chooses B and Player 2 chooses D, the outcome is (1, 3).

Each outcome describes players’ utilities. For example, if the (1, 3) outcome is realized, Player 1 gets utility = 1, Player 2 gets utility = 3.

FINDING NASH EQUILIBRIUM BY MEANS OF BACKWARD INDUCTION:

To find Nash Equilibrium by means of backward induction we start from the last stage (bottom) and move upward, to the top.

In the game, the last move is by player 2. He chooses C or D for the two cases (two states of the world: one state is achieved if Player 1 chooses A, another if player 1 chooses B).

First case (Player 1 chooses A), Player 2 compares his utility when he chooses C (=3) vs utility when he chooses D (=4). Since 4>3, action D is the best response should player 1 choose A. We put backward arrow for the action D.

Second case (Player 1 chooses B), Player 2 compares his utility when he chooses C (=2) vs utility when he chooses D (=3). Since 3>2, action D is the best response should player 1 choose B. We put backward arrow for the action D.

Now it’s Player 1’s time to make a move. Player 1 knows the structure of the game and he also knows that Player 2 is rational. This means that he knows that Player 2 will play his best responses (in the example, D is the best response for A, and D is also the best response for B).

As a result, Player 1 in reality compares the following two options (A-D vs B-D):

Since 2 > 1, action A is the best choice for Player 1. We put backward arrow for action A:

(2, 4) outcome is the Nash equilibrium outcome of the game. It is achieved when player 1 chooses A and player 2 chooses D. Formally, your answer should be something like this:

Nash equilibrium: (Player 1: A, Player 2: D).

            Nash equilibrium outcome: (2, 4).

EXERCISE:

The method can be easily applied for more complex games. For example, try to find Nash equilibrium using backward induction in the following game (the answer is below but try to solve for NE on your own first; don’t give up early):

SOLUTION:

(hint/note: player 3 utility is the third number in each outcome – this is the only number he cares about; player 2 – second number, player 1 – first number; last move is by the third player, next to last is by the second player, the first move is by the first player…)

Nash equilibrium: (Player 1: A, Player 2: D, Player 3: E).

Nash equilibrium outcome: (7, 4, 8).

Please let me know if you have any questions.

/Oleg Smirnov