Nash Equilibrium and Dominant Strategies
Nash Equilibrium is a term used in game theory to describe an equilibrium where each player's strategy is optimal given the strategies of all other players. A Nash Equilibrium exists when there is no unilateral profitable deviation from any of the players involved. In other words, no player in the game would take a different action as long as every other player remains the same. Nash Equilibria are self-enforcing; when players are at a Nash Equilibrium they have no desire to move because they will be worse off.
The following game doesn't have payoffs defined:
In order for (T,L) to be an equilibrium in dominant strategies (which is also a Nash Equilibrium), the following must be true:
In order for (T,L) to be a Nash Equilibrium, only the following must be true:
Prisoners' Dilemma (Again)
If every player in a game plays his dominant pure strategy (assuming every player has a dominant pure strategy), then the outcome will be a Nash equilibrium. The Prisoners' Dilemma is an excellent example of this. It was reviewed in the introduction, but is worth reviewing again. Here's the game (remember that in the Prisoners' Dilemma, the numbers represent years in prison):
In this game, both players know that 10 years is better than 20 and 0 years is better than 5; therefore, C is their dominant strategy and they will both choose C (cheat). Since both players chose C, (10,10) is the outcome and also the Nash Equilibrium. To check whether this is a Nash Equilibrium, check whether either player would like to deviate from this position. Jack wouldn't want to deviate, because if he chose NC and Tom stayed at C, Jack would increase his prison time by 10 years.
Iterated Deletion of Dominated Strategies
Here's another game that doesn't have dominant pure strategies, but that we can solve by iterated deletion of dominated strategies. In other words, we can eliminate strategies that are dominated until we come to a conclusion:
Let's find the dominant strategies. The first strategy that is dominated, is Right. Player 2 will always be better off by playing Middle, so Right is dominated by Middle. At this point the column under Right can be eliminated since Right is no longer an option. This will be shown by crossing out the column:
Remember that both players understand that player 2 has no reason to play Right--player 1 understands that player 2 is trying to find an optimum, so he also no longer considers the payoffs in the Right column. With the Right column gone, Up now dominates Down for player 1. Whether player 2 plays Left or Middle, player 1 will get a payoff of 1 as long as he chooses Up. So now we no longer consider Down:
Down 0,3 0,1 2,0
Now we know that player 1 will choose Up, and player 2 will choose Left or Middle. Since Middle is better than Left (a payoff of 2 vs. 0), player 2 will choose Middle and we have solved the game for the Nash Equilibrium:
Down 0,3 0,1 2,0
To ensure that this answer (Up, Middle) is a Nash Equilibrium, check to see whether either player would like to deviate. As long as player 1 has chosen Up, player 2 will choose Middle. On the other hand, as long as player 2 has chosen Middle, player 1 will choose up.
Multiple Nash Equilibria
Here's a game that demonstrates multiple Nash Equilibria: Two drivers are traveling towards each other on a road. Should they drive on the left or the right side? They don't want to wreck...
Both (Left,Left) and (Right,Right) are Nash Equilibria. As long as they're on opposite sides of the road, the drivers are happy and don't want to deviate. Games like this are often solved by social convention--beforehand all the players agree on a strategy so that everyone is better off. Of course, everyone knows that the right side is the best side to drive on, so the game should look more like this:
In this case, the game itself gives the players a clue as to where the other player will be, even though there are two Nash Equilibria.
Here's a game with three Nash Equilibria and no dominated strategies:
The Nash Equilibria are (A,a), (B,b), and (C,c).