Math: How to Easily Find a Nash Equilibrium in Game Theory
I studied applied mathematics, in which I did both a bachelor's and a master's degree.
What Is Game Theory?
Game theory is a field in mathematics that deals with problems in which multiple actors, called players, take a decision. The name suggests that it has to do with board games, or computer games. Originally game theory was used to analyse board game strategies; however, nowadays it is used for a lot of reals world problems.
In a mathematical game, the payoff of a player is not only determined by his own choice of strategy, but also by the strategies chosen by the other players. Therefore it is important to anticipate the other players' actions. Game theory tries to analyse the optimal strategy for multiple types of games.
Non-Cooperative Game Theory
A sub-field of game theory is the non-cooperative game theory. This field deals with problems where the players cannot cooperate and have to decide on their strategy without being able to discuss with the other players.
There are two types of games in non-cooperative game theory:
- In simultaneous games, both players make their decision at the same moment.
- In sequential games, the players have to act in order. Whether they know what strategies the previous players have chosen can differ per game. If they do, it is called a game with complete information, else it is called a game with incomplete information.
John Forbes Nash Jr.
John Forbes Nash Jr. was an American mathematician that lived from 1928 until 2015. He was a researcher at the University of Princeton. His work was mainly in the field of game theory, in which he made numerous important contributions. In 1994 he won the Nobel Prize for Economics for his applications of game theory in economics. The Nash equilibrium is a part of an entire equilibrium theory that Nash proposed.
An Example: The Prisoner's Dilemma
The prisoner's dilemma is one of the most well-known examples of non-cooperative game theory. Two friends are arrested for committing a crime. The police asks them independently whether they have done it or not. If both lie and say they didn't, and they both get three years in prison because the police has only a little evidence against them.
If both tell the truth that they are guilty, they will get seven years each. If one tells the truth and the other lies, then the one who tells the truth gets one year in prison and the other gets ten. This game is displayed in the matrix below. In the matrix, the strategies for player A are displayed vertically, and the strategies of player B horizontally. The payoff x,y means that player A gets x and player B gets y.
| Lie | Tell Truth |
Lie | 3,3 | 10,1 |
Tell Truth | 1,10 | 7,7 |
What Is a Nash Equilibrium and How Do You Find One?
The definition of a Nash equilibrium is an outcome of a game in which none of the players wants to switch strategies if the others don't. The prisoner's dilemma has one Nash equilibrium, namely 7,7 which corresponds to both players telling the truth. If player A would switch to lie while player B stays with telling the truth player A would get 10 years in prison, so he won't switch. The same holds for player B.
It seems like 3,3 is a better solution than 7,7. However, 3,3 is not a Nash equilibrium. If the players end up in 3,3 then if a player switches from lie to tell truth he reduces his penalty to 1 year if the other stays with lie.
Games With Multiple Nash Equilibria
It is possible for a game to have multiple Nash equilibria. An example is shown in the table below. In this example payoffs are positive. So a higher number is better.
| Left | Right |
Top | 5,4 | 2,3 |
Bottom | 1,7 | 4,9 |
In this game, both (Top,Left) and (Bottom,Right) are Nash equilibria. If A and B choose (Top,Left) then A can switch to Bottom, but this would reduce his payoff from 5 to 1. Player B can switch from left to right, but this would reduce his payoff from 4 to 3.
If the players are in (Bottom,Right) player A can switch, but then he reduces his payoff from 4 to 2 and player B can only reduce his payoff from 9 to 7.
Games Without a Nash Equilibrium
Besides having one or multiple Nash equilibria, it is also possible for a game to have no Nash equilibrium. An example of a game that has no Nash equilibrium is shown in the table below.
| Left | Right |
Top | 5,4 | 2,6 |
Bottom | 4,6 | 5,3 |
If the players end up in (Top,Left), player B would want to switch to Right. If they end up in (Top,Right) player A wants to switch to Bottom. Furthermore, if they end up in (Bottom, left) player A would rather have taken Top, and if they end up in (Bottom,Right) player B would be better off choosing Left. Hence none of the four options is a Nash equilibrium.
Mixed Strategies
Until now we only looked at pure strategies, meaning a player chooses only one strategy. However, it is also possible for a player to make a strategy in which he chooses every strategy with certain probability. For example, he plays Left with probability 0.4 and right with probability 0.6.
John Forbes Nash Jr. proved that every game has at least one Nash equilibrium when a mixed strategy is allowed. So when using mixed strategies the game above that was said to have no Nash equilibrium will actually have one. However, determining this Nash equilibrium is a very difficult task.
Nash Equilibria in Practice
An example of a Nash equilibrium in practice is a law that nobody would break. For example red and green traffic lights. When two cars drive to a crossroads from different directions there are four options. Both drive, both stop, car 1 drives and car 2 stops, or car 1 stops and car 2 drives. We can model the decisions of the drivers as a game with the following payoff matrix.
| Drive | Stop |
Drive | -5,-5 | 2,1 |
Stop | 1,2 | -1,-1 |
If both players drive they will crash, which is the worst outcome for both. If both stop they are waiting while no body is driving, which is worse than waiting while another person is driving. Therefore both situations in which exactly one car is driving are Nash equilibria. In the real world, this situation is created by traffic lights.
A game like this can be used to model a lot of other situations. For example visitors in a hospital. It is bad for a patient if too many people come to visit him. It is better when nobody comes, because then he can rest. However, he will be alone then. Therefore it is best when only one visitor comes. This is enforced by setting a maximum of one visitor.
Final Notes on the Nash Equilibrium
As we have seen, a Nash equilibrium refers to a situation that no player wants to switch to another strategy. However, this does not mean that there are not better outcomes. In practice, a lot of situations can be modeled as a game. When players act according to a Nash equilibrium strategy, no one would want to break with his decision.
© 2020 John