In addition to this, I want to know which one of these two is better in terms of computational complexity and with respect to the game.
Thank you.
Dear Amar,
a first order answer to your questions could be what follows.
Nash equilibrium is probably the most widely used method of predicting the outcome of a strategic interaction in the social sciences. Remembering that every game consists of 3 types of elements (a set of players, a set of actions or pure-strategies, a set of payoff), in a Nash Equilibrium (NE), each player chooses a strategy that maximizes their expected payoff given the strategies employed by other players: each player’s equilibrium strategy is a best response to the equilibrium strategy of the other player.
Basically, respect to the case of unique NE, to predict the likely outcome of multiple equilibrium we must use additional criteria.
This concept can best be understood using some examples. Consider first a game involving 2 players, each of whom has 2 available actions, which we call A and B. If the players choose different actions, they each get a payoff of 0. If they both choose A, they each get 2, and if they both choose B, they each get 1. The action profile (B, B) is an equilibrium, since a unilateral deviation to A by any one player would result in a lower payoff for the deviating player. Similarly, the action profile (A, A) is also an equilibrium.
Now consider the so called “matching pennies,”: 2 players, each with 2 actions. Each player can choose either heads (H) or tails (T); player 1 wins a dollar from player 2 if their choices are the same, and loses a dollar to player 2 if they are not. This last game has no pure-strategy Nash equilibrium.
In some cases, instead of simply choosing an action, players may be able to choose probability distributions over the set of actions available to them. Such randomizations over the set of actions are referred to as mixed strategies. Any profile of mixed strategies induces a probability distribution over action profiles in the game.
So, a pure-strategy Nash equilibrium is an action profile with the property that no single player can obtain a higher pay off by deviating unilaterally from this profile. A mixed strategy Nash-equilibrium is a mixed strategy profile with the property that no single player can obtain a higher value of expected utility by deviating unilaterally from this profile.
Nash equilibrium can sometimes correspond to outcomes that are inefficient, in the sense that there exist alternative outcomes that are both feasible and preferred by all players. This is the case, for instance, with the equilibrium (B, B) of the first example, in the first game presented above.
An even more clear example is the well-known prisoner’s dilemma game, in which each player can either “cooperate” or “defect” with the police, and payoffs are as follows: we have 2 players, each of whom has 2 available actions, (Cooperate and Defeat). If the players cooperate, they each get a payoff of 2 years in prison. If they both choose to Defect, they each get 1 year. in the other 2 cases, each player risks 3 years in prison if he decides not to cooperate and the other player cooperates.
The resulting unique Nash equilibrium is C, namely the mutual cooperation with the police, an outcome that is worse for both players than D, the mutual defection.
Obviously, the result depends on the formulation of the problem. In this case, it is assumed that each prisoner is only interested in the risks he runs personally.
Furthermore, there are several important issues (like incomplete information for the players); in the follows I suggest some reference:
Harsanyi, John C., and Reinhard Selten. 1998. A General Theory of Equilibrium Selection in Games. Cambridge, MA: MIT Press.
Kreps, David, Paul Milgrom, John Roberts, and Robert Wilson. 1982. Rational Cooperation in the Finitely Repeated Prisoner’s Dilemma. Journal of Economic Theory 27: 245–252.
Osborne, Martin J., and Ariel Rubinstein. 1994. A Course in Game Theory. Cambridge, MA: MIT Press.
Uniqueness of Nash Equilibrium is a desired property of games, but in most cases not ensured. Even for games in extensive form there may be multiple Nash Equilibria. Some of them may be not very plausible, because they inherit incredible threats. Therefore, additional features of equilibria have been considered, such as subgame perfectness (proposed by R. Selten as far as I know). This concept is also useful under computational aspects. Decision trees (of games in extensive form) can be efficiently inspected by the "Backward Induction Algorithm". In case of strict preferences of players on the terminal nodes of the decision tree subgame perfect equilibrium is unique. Nevertheless, even in this case, there may exist other (not subgame perfect) equilibria, which might be interesting, because they require some coordination between players. It may be attractive for specific groups of players to deviate from the subgame perfect solution in order to achieve a preferred outcome. Normally, this works only, if the threat posed by the player group is strong enough.
The answer of Marco rao is very accurate.
I just wanted to add that this issue of multiple Nash equilibria is of major importance in bi-level models. In this sense, when multiple equilibria exist in the lower level the results of the bi-level problem can be distorted. Therefore, apart from introducing probabilities to reach an unique equilibrium, for bi-level models a pessimistic approach can be followed in which the upper level choses the worst realization of the lower level and therefore lead to an unique solution.
Just in case you are also interested in bi-level modelling.
Multiple pure strategy NE will be very frequent in games with many pure strategies. This likely explains why few experimenters have run game experiments with a large number of pure strategies.
- Badges
- Science topic
- Similar topics
- Computer Communications (Networks)
- Simulators