Nash equilibrium

John F. Nash (2006)

The Nash equilibrium (abbreviated as NGG or NGGW ) is a central term in game theory . It describes a combination of strategies in non-cooperative games , with each player choosing exactly one strategy from which it makes no sense for any player to deviate from his chosen strategy as the only one. In a Nash equilibrium, every player agrees with his choice of strategy, even retrospectively, he would hit it again in the same way. The strategies of the players are therefore mutually best answers . The Nash equilibrium is an elementary solution concept in game theory. Definition and proof of existence of the Nash equilibrium go to the 1950 published dissertation of mathematician John Forbes Nash Jr. back. The Nash equilibrium finds u. a. a central importance in economic areas such as microeconomics , in the distribution of goods and pricing.

idea

The main goal of mathematical game theory is to characterize and determine rational decisions for conflict, but also for cooperation situations. The difficulty is that none of the decision makers ("players") knows what plans the other players are pursuing and how they will decide accordingly. It is therefore uncertain for an individual player how his specific decision for a plan of action (“strategy”) will affect. But he can think through the situation from the perspective of the other players in order to form an expectation of what they will do.

The Nash equilibrium is based on the following idea: You start from all possible combinations that contain a strategy for each player. Such a strategy combination is called Nash equilibrium if it can be assumed to have a certain stability due to the fact that no individual player has an incentive to deviate from his strategy. Formally, this means that the payout to the player who changes his strategy as an individual may not increase due to this change.

definition

A Nash equilibrium is a pair of strategies (or a strategy tuple if there are more than two players), in which it is not worthwhile for any player to deviate from his strategy one-sided (alone). Strategically, from a player's point of view, this means: I do the best I can, taking into account what you are doing; you do the best that you can, considering what i do.

When studying Nash equilibria, three types of strategies can be distinguished: dominant strategies, pure strategies, and mixed strategies. It should be noted that some games do not have a Nash equilibrium if only pure strategies are used. When using mixed strategies, on the other hand, there is always one or more equilibria if a finite number of pure strategies is assumed.

Dominant strategies : What a player does is best for him regardless of what the others are doing. Such dominant strategies rarely exist, as it mostly depends on the decisions of others what is best for a player. Sometimes - for example in the prisoner's dilemma - every player has a dominant strategy, which then constitutes a so-called balance in dominant strategies.

Pure strategies : the player makes a very specific decision.

Mixed strategies : The player makes a random decision between two or more possible courses of action (the pure strategies), but with certain probabilities for the pure strategies.

Formal definition for different strategies

Nash equilibrium in pure strategies

It denotes the set of strategies ( alternative courses of action) of the -th player and the Cartesian product of these sets of strategies. ${\displaystyle \Sigma _{i}}$ ${\displaystyle i}$ ${\displaystyle \Sigma :=\Sigma _{1}\times \dotsb \times \Sigma _{n}}$

Under a Nash equilibrium in pure strategies is defined as a strategy profile in which each player's strategy is a best response is to the selected strategies of the other players. If all other players adhere to their chosen strategies, the Nash equilibrium in pure strategies is formally characterized by the fact that there is no one that promises the player a higher payout: ${\displaystyle \sigma ^{*}=(\sigma _{1}^{*},\dotsc ,\sigma _{n}^{*})\in \Sigma }$ ${\displaystyle i}$ ${\displaystyle i}$ ${\displaystyle \sigma _{i}\neq \sigma _{i}^{*}}$ ${\displaystyle i}$

${\displaystyle \forall \sigma _{i}\in \Sigma _{i}:u_{i}(\sigma _{1}^{*},\dotsc ,\sigma _{i}^{*},\dotsc ,\sigma _{n}^{*})\geq u_{i}(\sigma _{1}^{*},\dotsc ,\sigma _{i},\dotsc ,\sigma _{n}^{*})}$.

It is also said that a unilateral deviation does not improve the player's payout . A Nash equilibrium is characterized by the fact that no player can improve himself by changing his strategy unilaterally. If a Nash equilibrium consists only of dominant strategies, it is also known as a strict equilibrium . ${\displaystyle i}$

Nash equilibrium in mixed strategies

In some cases it can be that the players are not bound by any particular strategy, but a probability distribution with which the out be drawn at random. If finite or at least countable , the probability distribution can be described by a vector , the probability being that the strategy is chosen. ${\displaystyle \sigma _{i}}$ ${\displaystyle \Sigma _{i}}$ ${\displaystyle \Sigma _{i}}$ ${\displaystyle s_{i}}$ ${\displaystyle s_{i,j}}$ ${\displaystyle \sigma _{i,j}\in \Sigma _{i}}$

The mixed strategy is a Nash equilibrium if and only if no player can achieve a better payout by deviating alone, that is if and only if ${\displaystyle s=(s_{1}^{*},\dotsc ,s_{n}^{*})}$

${\displaystyle \forall i\in \{1,\dotsc ,n\}\;\;\forall s_{i}\in S_{i}\;\;u_{i}(s_{1}^{*},\dotsc ,s_{i-1}^{*},s_{i},s_{i+1}^{*},\dotsc ,s_{n}^{*})\leq u_{i}(s_{1}^{*},\dotsc ,s_{i-1}^{*},s_{i}^{*},s_{i+1}^{*},\dotsc ,s_{n}^{*})}$.

A Nash equilibrium in mixed strategies is characterized by the fact that any strategy played as part of an equilibrium has the same expected payoff.

existence

With the help of Kakutani's fixed point theorem , one can show that at least one Nash equilibrium must exist if the following conditions are met:

1. The payout functions are continuous and quasi-concave in . ${\displaystyle H_{i}(\sigma _{1},\ldots ,\sigma _{n})}$ ${\displaystyle \sigma _{i}}$
2. The strategy sets are convex and compact . ${\displaystyle \Sigma _{1},\ldots ,\Sigma _{n}}$

Games are often constructed in such a way that they are finite, but finite sets with more than one element cannot be convex. However, in this case, the amount of the mixed strategies via compact and convex and the corresponding extension of multi-linear. While the existence of a Nash equilibrium in pure strategies cannot be guaranteed, at least one Nash equilibrium exists in a game in mixed strategies (if a finite number of pure strategies is assumed). ${\displaystyle \Sigma _{i}}$ ${\displaystyle S_{i}}$ ${\displaystyle \Sigma _{i}}$ ${\displaystyle H}$

A simple algorithm for identifying Nash equilibria

If a game is in strategic form, all Nash equilibria can be determined in pure strategies using the following algorithm:

1. Optimize the player's decision with (arbitrarily) fixed strategies of all other players: Mark the highest payouts that can be achieved for players under these circumstances (the so-called "best answers" to the strategy combination of the other players). Repeat this for all possible strategy combinations of the other players. ${\displaystyle i=1,\dotsc ,n}$ ${\displaystyle i}$
2. Perform 1. for all players.

Then precisely those strategy combinations are Nash equilibria, with the payouts marked for all players. If there is no strategy combination that is marked for all players, the game will not have a Nash equilibrium in pure strategies either. - This approach is only suitable for a small number of players and strategies.

example

Let the following game be given in normal form :

	Left	center	right
above	4 , 2	1 , 1	2 , 0
center	2, 3	1 , 1	1, 4
below	3, 0	0, 2	1, 3
Payout bimatrix for player 1 and player 2

Then the algorithm works as follows (marked with bold):

• ${\displaystyle i=1:}$
  • given player 2 plays right: for player 1 above is optimal - mark 2 ("above is the best answer to the right")
  • given player 2 plays middle: top and middle is optimal - mark the two 1's
  • given player 2 plays left: above is optimal - mark the 4

• ${\displaystyle i=2:}$
  • given player 1 plays above: For player 2, left is optimal - mark the 2
  • given player 1 plays in the middle: right is optimal - mark the 4
  • given player 1 plays below: right is optimal - mark the 3

So the only Nash equilibrium is the pair of strategies (top, left) that lead to the payoff (4, 2).

If it is necessary to check whether a tuple of mixed strategies is a Nash equilibrium, the above algorithm only works to a limited extent, since an infinite number of mixed strategies would have to be checked. Alternatively, the game can also be solved with iterative elimination of strictly dominated strategies .

An algorithm for identifying Nash equilibria in mixed strategies

When identifying Nash equilibria in mixed strategies, it is helpful to identify those mixed strategies that make the opponent indifferent between his alternative courses of action. Once such a strategy is found, all actions of the opponent are the best answers. If such mixed strategies meet, then they are mutually best answers, there is no reason to deviate one-sided, and the mixed strategies form a Nash equilibrium.

For any two-person zero-sum games with a finite set of strategies ( matrix game ), the determination of Nash equilibria in mixed strategies can be represented as a linear optimization problem that can be solved with the help of the simplex algorithm .

example

The following bimatrix is ​​given :

	Opera	Soccer
Opera	3, 2	2, 3
Soccer	1, 3	4, 1
Payout matrix for player 1 and player 2

Then the algorithm works as follows:

Player 2 plays with a probability of Opera and with the remote likelihood of football, so arise for player 1, the following expected utility ( Expected Utility ): ${\displaystyle q}$ ${\displaystyle (1-q)}$

${\displaystyle \operatorname {E} [U_{1}(O)]=3q+2(1-q)}$

${\displaystyle \operatorname {E} [U_{1}(F)]=1q+4(1-q)}$

Player 1 is therefore indifferent between his two strategies if

${\displaystyle {\begin{array}{cl}&3q+2(1-q)\;=\;1q+4(1-q)\\\Leftrightarrow &3q+2-2q\;=\;1q+4-4q\\\Leftrightarrow &1q+2\;=\;4-3q\\\Leftrightarrow &4q\;=\;2\\\Leftrightarrow &q\;=\;1/2\end{array}}}$

For player 2 it can be determined in an analogous way that he is indifferent if player 1 plays with a probability of opera and soccer. ${\displaystyle p=2/3}$ ${\displaystyle (1-p)=1/3}$

Since all of the opponent's answers to these two strategies are the best answers, they are also mutually best answers. Thus it can be identified as a Nash equilibrium in mixed strategies. ${\displaystyle [(2/3;1/3),(1/2;1/2)]}$

Special cases

A special case of Nash's existence theorem for equilibria is the Min-Max theorem , valid for two-person zero-sum games , which was proven by John von Neumann in 1928 . Unlike in the general case, each game has a unique payout vector , where the value of the game is called. ${\displaystyle (v,-v)}$ ${\displaystyle v}$

For two-person zero-sum games with perfect information , including board games like chess and mill , there is always a minimax equilibrium in pure strategies that can be determined recursively with the minimax algorithm . This theorem was already proven in 1912 by Ernst Zermelo .

Practical examples

Market economy

Strategy finding based on Nash equilibria can be applied equally to prices and quantities . In a market economy , a situation is conceivable in which several providers in a market have lowered the prices of their competing products to such an extent that they are just barely working economically. An evasive strategy would not be possible for the individual provider: If he lowers his price in order to increase his sales, he falls under profitability; if he increases it, buyers will switch to competing products and his profit will also decrease. One way out could be to introduce a product innovation (almost) simultaneously with a competitor in order to justify a higher price. Such scenarios were discussed more broadly under the term coopetition in the mid-1990s , with the dispute between the US airlines being cited as a striking example.

Prisoner's Dilemma

→ Main article : Prisoner's Dilemma

Another example is the prisoner's dilemma, a game theory problem in which there is exactly one Nash equilibrium.

	confesses	does not confess
confesses	-5, -5	-1, -10
does not confess	-10, -1	-2, -2
Payout matrix for player 1 and player 2

To do this, imagine the following situation: Two prisoners are suspected of having committed a crime together. The maximum sentence for the crime is 10 years in prison. A deal is now offered to both prisoners, about which both are informed. If one confesses alone (key witness) and thus also incriminates his partner, he gets a mild sentence of 1 year imprisonment - the other has to serve the full 10 years. If both decide to remain silent, only circumstantial evidence remains, but this is sufficient to lock both of them for 2 years. But if both confess the act, each expects a prison sentence of 5 years. Now the prisoners are questioned independently of one another. Neither before nor during the survey, the two of them have the opportunity to talk to each other.

It is true that it is optimal for the two prisoners if they are both silent. However, this combination of strategies is not stable because a single prisoner can gain an advantage for himself through a confession. The strategy combination in which both prisoners confess is stable in the sense of a Nash equilibrium: Then no individual can gain an advantage through silence, so that there is a Nash equilibrium. But this Nash equilibrium delivers worse results for both prisoners than the mutual silence, which can only be fixed through cooperation. In other words: The Nash equilibrium in the prisoner's dilemma is not Pareto-optimal , since both players can improve against it together.

See also

• A variety of related concepts can be found under Balance (Game Theory)

Web links

• Game theory and Nash - Derivation and Examples (English)
• Minimax strategy in practice: Simple two-person bluff game against the computer

Individual evidence

1. ^ John Forbes Nash: Non-cooperative games. Dissertation, Princeton University 1950 ( online version ; PDF; 1.2 MB).