Finding Nash Equilibria

When a game does not have any dominant or dominated strategies, or when the iterated deletion of dominated strategies does not yield a unique outcome, cell-by-cell inspection is used. Simply put, each cell of the game box is checked, each time asking “does either player have incentive to change their strategy unilaterally” or “are both players playing a best response.” The problem with this approach is that it can take quite a while. If there are two players, one with N strategies and the other with M, we need to check NxM cells which, for many games, can be quite large.

In this note, you will learn a simpler technique for conducting cell-by-cell inspection. This method, called “strategy-by-strategy inspection” requires only N+M inspections, and is less likely to result in mistakes.

Consider a two-player game with five strategies for each player:
   

Player 1

Player 2

  

V

W

X

Y

Z

A

9 , 9

7 , 1

5 , 6

3 , 4

1 , 1

B

7 , 8

5 , 2

3 , 6

1 , 4

3 , 3

C

5 , 6

3 , 3

1 , 8

9 , 7

1 , 5

D

3 , 9

1 , 9

9 , 4

7 , 9

5 , 9

E

1 , 2

9 , 8

7 , 7

5 , 6

3 , 7



Since each player has five strategies, in order to perform cell-by-cell inspection, you could have to check 5x5=25 inspections. Instead, using the best-response method, only 5+5=10 checks have to be performed.

Start with Player 1. For each of Player 1’s strategies, select the strategy/strategies that would maximize Player 2’s payoff. For example, if Player 1 plays V, Player 2’s best response is to play A, earning a payoff of 9. Underline this payoff in the game box:

 

 

Player 1

Player 2

 

V


A

9 , 9






Proceed with Player 1’s other strategies.



Player 1

Player 2


V

W

X

Y

Z

A

9 , 9

7 , 1

5 , 6

3 , 4

1 , 1

B

7 , 8

5 , 2

3 , 6

1 , 4

3 , 3

C

5 , 6

3 , 3

1 , 8

9 , 7

1 , 5

D

3 , 9

1 , 9

9 , 4

7 , 9

5 , 9

E

1 , 2

9 , 8

7 , 7

5 , 6

3 , 7

Now, we can do the same thing for Player 1’s best response to Player 2.

If Player 2 plays D, Player 1 is indifferent between V,W,Y, and Z. Note that a best response is not necessarily unique. A player can have a number of strategies that are all best responses if they all earn the same payoffs, and earn greater payoffs than other strategies. In cases such as these, underline all of the best responses. Continue for the rest of Player 2’s strategies:



Player 1

Player 2


V

W

X

Y

Z

A

9 , 9

7 , 1

5 , 6

3 , 4

1 , 1

B

7 , 8

5 , 2

3 , 6

1 , 4

3 , 3

C

5 , 6

3 , 3

1 , 8

9 , 7

1 , 5

D

3 , 9

1 , 9

9 , 4

7 , 9

5 , 9

E

1 , 2

9 , 8

7 , 7

5 , 6

3 , 7

Recall that an equilibrium is defined by both players simultaneously playing their best replies, so that neither player has an incentive to deviate. This is equivalent to saying that a pair of strategies is in equilibrium if both payoffs are underlined.

In the above, we find three equilibria:

     {A,V}      {E,W}     {D,Z}

You should convince yourself that in all three cases, neither player has an incentive to deviate, or change their strategy unilaterally.