Nash equilibrium
The Nash equilibrium, partly ( as in English ) Nash Equilibrium called, is a central concept of mathematical game theory. It describes in non- cooperative games, a combination of strategies, each player chooses a strategy exactly, from which it is useful for any player to deviate from its chosen strategy. In a Nash equilibrium, therefore, each player agrees also afterwards with his strategy choice, he would meet them again the same way. The strategies of the players are therefore mutually best responses. The Nash equilibrium is a fundamental solution concept in game theory. Definition and proof of existence of Nash equilibrium back to the dissertation issued in 1950 by the mathematician John Forbes Nash Jr.. The Nash equilibrium is, inter alia, a central role in economics areas such as microeconomics, in the distribution of goods and pricing.
- 5.1 Example
- 6.1 Example
- 8.1 Market Economy
- 8.2 Prisoner's Dilemma
Idea
The main objective of mathematical game theory is for conflict, but also for cooperation situations to characterize rational decisions and to determine. The difficulty here is that none of the decision makers ( " player " ) knows what plans follow the other players and how they will decide accordingly. Thus, it is uncertain for a single player, as his concrete decision shall work together for an action plan ( " Strategy"). He can think through the situation from the perspective of the other players to form an expectation of what will do this.
The Nash equilibrium is now the following idea: We start with all possible combinations that include a strategy for each player. Such a strategy combination is called a Nash equilibrium if its a degree of stability can be assumed due to the fact that no single player has an incentive to deviate from his strategy. Formally, this means that the payout to those players who changes his strategy as an individual, because of this change must not increase.
Definition
A Nash equilibrium is a strategy pair (or, if more than two players, a strategy N- tuples ) in which it pays for any player, single (alone) deviate from its strategy. Strategically, from the perspective of a player, this means: "I'm doing the best I can, considering what you're doing. " And " you're doing, taking account of what I do, the best thing you can do. "
In the study of Nash equilibria three kinds of strategies can be identified, dominant strategies, pure and mixed strategies strategies. It should be noted that, in some games, no Nash equilibrium exists when only pure strategies are used. The use of mixed strategies, however, there is always one or more equilibria ( when starting from a finite number of pure strategies ).
Dominant strategies: "What I do, is quite independent of what you do, for me the best." Such dominant strategies rarely exist, since it is usually the other depends on the decisions of what is " best for me " is. Sometimes - for example in prisoner's dilemma - but each player has a dominant strategy, then a so-called " equilibrium in dominant strategies " constitute.
Pure strategies: "I (the player ) meet a particular decision. "
Mixed strategies: "I (the player ) meet a random choice between two or more possible courses of action ( the pure strategies ), but with certain probabilities for pure strategies. "
Formal definition with different strategies
Nash equilibrium in pure strategies
Denote the set of strategies ( alternatives ) of the -th player and the Cartesian product of the strategy sets.
Under a Nash equilibrium in pure strategies is defined as a strategy profile in which each player's strategy is a best response to the strategies chosen the other players. If all other players stick to their chosen strategies, the Nash equilibrium in pure strategies is formally characterized in that it therefore not available for players that promises players a higher payout:
It is also said that players can not improve his payoff by a unilateral deviation. A Nash equilibrium is characterized therefore by the fact that no player can improve by a unilateral change in its strategy.
Nash equilibrium in mixed strategies
In some cases, it allows that the player is not set to a particular strategy, but on a probability distribution, with which are drawn at random. Is finite or at least countable, the probability distribution can be described by a vector, where the probability is that the strategy is chosen.
The mixed strategy is a Nash equilibrium if and only if no player can achieve a better payoff by the sole deviation, ie if and only if
Existence
With the help of the fixed point theorem of Kakutani, one can show that at least one Nash equilibrium must exist if the following conditions are met:
Often games are designed so that the are finite, however, finite sets can not be convex. However, in this case, the amount of the mixed strategies on compact is convex and the corresponding extension of multi- linear. While the existence of a Nash equilibrium in pure strategies therefore can not be guaranteed, there exists at least one Nash equilibrium in a game in mixed strategies (if it is assumed that a finite number of pure strategies ).
A simple algorithm for identifying Nash equilibria
Is a game in strategic form, then all Nash equilibria in pure strategies determined by the following algorithm:
Then are exactly the strategy combinations Nash equilibria, in which all payments are highlighted. This approach is only suitable for a small number of players and strategies.
Example
Be given the following game in normal form:
Then, the algorithm works as follows:
- If player 2 plays Right: For player 1 is optimal up - select the 2 (" Above is the best response to law " )
- If player 2 plays center: top and middle is optimal - mark the two 1s
- If Player 2 plays Left: above is optimal - mark the 4
- If player 1 plays above: For player 2 is optimal links - mark the 2
- If player 1 plays center: Right is optimal - mark the 4
- If player 1 plays below: Right is optimal - mark the 3
The only Nash equilibrium is therefore the strategy, leading to the payment 4, 2: (top, left ).
If it is to check whether a tuple of mixed strategies is a Nash equilibrium, the above algorithm works only partially, since an infinite number would have to be checked in mixed strategies.
An algorithm for the identification of the Nash equilibria in mixed strategies
For the identification of the Nash equilibria in mixed strategies, it is helpful to identify those mixed strategies that make the opponent indifferent between its alternatives. Is such a strategy found, all the actions of the opponent are best responses. Meeting such mixed strategies on each other so they are therefore mutually best responses, there is no reason for unilateral deviation, and the mixed strategies constitute a Nash equilibrium.
Example
Given the following matrix Bi:
Then, the algorithm works as follows:
Does Player 2 with a probability of Opera and with the counter probability of football, so result for player 1 following expected utility (expected utility):
Player 1 is thus indifferent between his two strategies when
For player 2 can be determined analogously that he is indifferent, if Player 1 plays with a probability of opera and football.
Since all responses of the opponent are the best answers to these two strategies, they are specifically each also mutually best responses. It can thus be identified as a Nash equilibrium in mixed strategies.
Special cases
A special case of Nash's existence theorem for equilibria is valid for two-person zero-sum games min-max theorem, which was proved in 1928 by John von Neumann. Unlike in the general case, this corresponds to each game a unique payoff vector, where the value of the game is called.
For two-person zero-sum games with perfect information, including board games like chess and mill belong even exists always a minimax equilibrium in pure strategies that can be determined using the minimax algorithm recursively. This theorem was proved in 1912 by Ernst Zermelo.
Practice examples
Market economy
Strategy development based on Nash equilibria can be applied to prices and quantities alike. In the market economy, a situation is conceivable in which several suppliers have lowered their prices in a market competing products so much that they just work economically. For each provider an evasive strategy would not be possible: it lowers its price to increase its sales, it falls within the economy; he raised it, buyers will switch to its competitors and its profit also decreases. A way out can now approximately be to ( almost ) the same time introduce a competitors product innovation in order to justify a higher price. The term coopetition such scenarios were discussed mid-1990s broad, most notably the dispute between the U.S. airlines has been cited as a striking example.
Prisoner's Dilemma
Another example is the Prisoner's Dilemma, a game- theoretical problem, in which there is exactly one Nash equilibrium.
To this end, imagine following situation you imagine: Two prisoners are suspected of having committed a crime together. The maximum penalty for the crime is 10 years in prison. Both prisoners a trade is now being offered, what both are informed. If one confesses alone ( witness ), and thus his partner mitbelastet, he gets a light sentence of 1 year in prison - the other has to serve the full 10 years. Decide both to remain silent, only circumstantial evidence, but sufficient to imprison both for 2 years remain. But confess both the act, is served each a prison sentence of 5 years. Now the prisoners are interviewed independently. Neither before nor during the survey, the two will have the opportunity to consult with each other.
While it is optimal for the two prisoners when they mention both. This strategy combination is not stable, because a single prisoner can obtain a confession by an advantage for themselves. Stable in the sense of a Nash equilibrium is the strategy combination in which both prisoners confess: Then can gain no individual by a silence an advantage, so that there is a Nash equilibrium. This Nash equilibrium but provides for both prisoners worse results than the two-sided silence that can be fixed only through cooperation.