Nash Equilibrium

prisoner's dilemma in game theorySee all videos for this article

Nash equilibrium, also called Nash solution, in game theory, an outcome in a noncooperative game for two or more players in which no player’s expected outcome can be improved by changing one’s own strategy. The Nash equilibrium is a key concept in game theory, in which it defines the solution of N-player noncooperative games. It is named for American mathematician John Nash, who was awarded the 1994 Nobel Prize for Economics for his contributions to game theory.

Game theory uses mathematics to model and analyze situations in which decisions are interdependent. While it can be used to model recreational games such as Monopoly or poker, it is often used to analyze topics of real-world interest, including economics and military strategy. In game theory, a game may be any situation in which there are interdependent decisions, and the players are all the decision-making entities.

A game is noncooperative as long as no mechanism exists for the players to make binding agreements with one another. For example, in the famous prisoner’s dilemma, two prisoners have been accused of a crime and are asked to confess. If one confesses and the other does not, the one who confesses will be released, and the one who does not will receive a harsh sentence. If both confess, both will receive a serious, but not harsh, sentence. If neither confesses, both will receive a very light sentence. Because there is no outside authority enforcing any agreement between the prisoners, the game is noncooperative; neither prisoner suffers a penalty for betraying the other.

A payoff matrix is often used to help determine the optimal strategy for the players in the game. In the payoff matrix, each row represents one possible strategy for one player, and each column represents one possible strategy for the other. In the example above, the matrix would look like the figure below.

Each player (prisoner A or prisoner B) will attempt to adopt the strategy (confess or remain silent) that results in the least amount of jail time (0, 1, 5, or 20 years). The best outcome for the prisoners is for both to remain silent, as this results in a total sentence of only 2 years (as opposed to 20, if only one chooses to remain silent, or 10, if both choose to confess). This collection of strategies results in the best payoff for the players collectively. However, it is not the Nash equilibrium, because either prisoner’s payoff can be improved by choosing a different strategy.

If prisoner A remains silent, then prisoner B can either remain silent and receive a 1-year sentence or confess and go free. Prisoner B’s own payoff therefore can be improved by confessing. However, one prisoner confessing and the other remaining silent is also not a Nash equilibrium, because the payoff of the prisoner who remains silent can be improved by changing strategies. If prisoner A confesses, then prisoner B can either remain silent and face a 20-year sentence or confess and face a 5-year sentence. Thus, prisoner B’s payoff can be improved by switching from remaining silent to confessing.

The only collection of strategies in which no player’s payoff can be improved by switching strategies is if both prisoners confess. In this scenario, either prisoner choosing to switch strategies will result in a lower payoff. Despite this being worse for both players (resulting in a total 10-year sentence) than if both were to remain silent, it is the Nash equilibrium.

It is possible for there to be multiple Nash equilibria to a given problem. For example, suppose two friends wish to see a movie together but disagree on which movie. If both would rather see either movie together than see a movie alone, then both friends seeing either movie constitutes a Nash equilibrium, as neither can opt to see the other film without suffering a worse outcome.

It is also possible that a Nash equilibrium is a “mixed” equilibrium, meaning that at least one player should employ a specific mix of strategies rather than employing the same strategy consistently (a “pure” Nash equilibrium). For example, in the game rock-paper-scissors, the Nash equilibrium is that each player should choose each option exactly one-third of the time, because if a player chooses one option more than the others, the other player can exploit that tendency to win a greater percentage of the matches.

Nash equilibria may be found for situations involving many players (such as individual use of common resources) or for asymmetrical situations (such as contract negotiations between an individual and a business). Nash proved that if mixed strategies are allowed, then there is at least one Nash equilibrium for every noncooperative game with a finite number of players choosing from a finite number of strategies.