Finding Nash equilibrium (in pure strategies in a strategic form)*
* note for those who are familiar with game theory: we do not consider mixed strategies in this class.
Definition: Nash equilibrium is a combination of strategies such that no player has an incentive to deviate (choose another strategy) unilaterally.
|
4, 4 |
1, 3 |
|
3, 1 |
2, 2 |
This is an abbreviate version of the following:
|
|
Player 2 (column player) |
||
|
Action C |
Action D |
||
|
Player 1 (row player) |
Action A |
4, 4 |
1, 3 |
|
Action B |
3, 1 |
2, 2 |
|
To find Nash equilibrium in this game we use the method of “stars for best responses.” Here is how it works.
1) Assume that player 2 chooses Action C. So we are looking at the first column:
|
4, 4 |
|
|
3, 1 |
|
We need to find the best response for player 1 for Action C by player 2. Recall that the first number in each cell is utility of the first/row player, second number is the utility of the second/column player. To find the best response, player 1 compares his own utilities, which means he compares:
|
4, |
|
|
3, |
|
Clearly, 4 > 3, therefore Action A is the best response to Action C:
|
4*, |
|
|
3, |
|
2) Now assume that player 2 chooses action D. We are looking at the second column now:
|
4*, |
1, 3 |
|
3, |
2, 2 |
Since player 1 cares only about his own utilities he compares 1 and 2:
|
4*, |
1, |
|
3, |
2, |
Clearly, 2 > 1, therefore Action B is the best response to Action D:
|
4*, |
1, |
|
3, |
2*, |
We are done with the first/row player since we just found all of his best responses.
3) Now we need to do the same for player 2.
Assume that player 1 choose Action A which means that we are looking at the first row:
|
4*, 4 |
1, 3 |
|
3, |
2*, |
Don’t forget that we are now looking for a best response for player 2, which means we compare the second numbers in each cell (second player’s utilities). In this case it’s 4 and 3; clearly 4 > 3, therefore:
|
4*, 4* |
1, 3 |
|
3, |
2*, |
Action C is the best response to Action A.
4) Finally, assume that player 1 chooses Action B. Now we are looking at the second row:
|
4*, 4* |
1, 3 |
|
3, 1 |
2*, 2 |
Comparing player 2’s utilities (1 and 2), we establish that 2 > 1, i.e., Action D is the best response to Action B. Thus,
|
4*, 4* |
1, 3 |
|
3, 1 |
2*, 2* |
We are done. We found the best responses for both players. Nash equilibrium is a cell with two stars (meaning that this outcome is achieved when the two players do their best). In our example, there are two such cells (4*,4* and 2*,2*) which means that the game has two Nash equilibria.
It is easy to check that for each Nash equilibrium that we found “no player has an incentive to deviate unilaterally.”
Some other notes:
1) There are cases when we have games with no Nash equilibria in pure strategies.
2) There are cases when we have games with two or more Nash equilibria in pure strategies.
3) If two actions give a player the same utility then both actions are best responses (meaning you put stars for each of them). For example, for the row player the best responses to column player are:
|
1*, |
2, |
|
1*, |
3*, |
If player 2 chooses Action C (first column), both Action A and Action B are best responses for player 1 (1* and 1*).
The method allows us to find Nash equilibria in a matter of seconds for highly complex games. For example try to find NE in the following game without looking at the answer:
|
3, 3 |
6, 4 |
3, 0 |
9, 4 |
|
4, 5 |
5, 3 |
2, 2 |
8, 4 |
|
2, 2 |
1, 2 |
7, 3 |
9, 3 |
This may look very challenging and without game theoretic tools it really is!
ANSWER:
Using our “method of stars for best responses” you will need less than a minute to establish that the game has 5(!) Nash equilibria in pure strategies:
|
3, 3 |
(6*, 4*) |
3, 0 |
(9*, 4*) |
|
(4*, 5*) |
5, 3 |
2, 2 |
8, 4 |
|
2, 2 |
1, 2 |
(7*, 3*) |
(9*, 3*) |
Please let me know if you have any questions.
/Oleg Smirnov