In game theory, a strong Nash equilibrium (SNE) is a combination of actions of the different players, in which no coalition of players can cooperatively deviate in a way that strictly benefits all of its members, given that the actions of the other players remain fixed. This is in contrast to simple Nash equilibrium, which considers only deviations by individual players. The concept was introduced by Israel Aumann in 1959.[1] SNE is particularly useful in areas such as the study of voting systems, in which there are typically many more players than possible outcomes, and so plain Nash equilibria are far too abundant.[2]
| Strong Nash equilibrium | |
|---|---|
| Solution concept in game theory | |
| Relationship | |
| Subset of | Evolutionarily stable strategy (if the strong Nash equilibrium is not also weak) |
| Significance | |
| Used for | All non-cooperative games of more than 2 players |
Existence
editNessah and Tian[3] prove that an SNE exists if the following conditions are satisfied:
- The strategy space of each player is compact and convex;
- The payoff function of each player is concave and continuous;
- The coalition consistency property: there exists a weight-vector-tuple w, assigning a weight-vector wS to each possible coalition S, such that for each strategy-profile x, there exists a strategy-profile z in which zS maximizes the weighted (by wS) social welfare to members of S, given x-S.
- Note that if x is itself an SNE, then z can be taken to be equal to x. If x is not an SNE, the condition requires that one can move to a different strategy-profile which is a social-welfare-best-response for all coalitions simultaneously.
For example, consider a game with two players, with strategy spaces [1/3, 2] and [3/4, 2], which are clearly compact and convex. The utility functions are:
- u1(x) = - x12 + x2 + 1
- u2(x) = x1 - x22 + 1
which are continuous and convex. It remains to check coalition consistency. For every strategy-tuple x, we check the weighted-best-response of each coalition:
- For the coalition {1}, we need to find, for every x2, maxy1 (-y12 + x2 + 1); it is clear that the maximum is attained at the smallest point of the strategy space, which is y1=1/3.
- For the coalition {2}, we similarly see that for every x1, the maximum payoff is attained at the smallest point, y2=3/4.
- For the coalition {1,2}, with weights w1,w2, we need to find maxy1,y2 (w1*(-y12 + y2 + 1)+w2*(y1 - y22 + 1)). Using the derivative test, we can find out that the maximum point is y1=w2/(2*w1) and y2=w1/(2*w2). By taking w1=0.6,w2=0.4 we get y1=1/3 and y2=3/4.
So, with w1=0.6,w2=0.4 the point (1/3,3/4) is a consistent social-welfare-best-response for all coalitions simultaneously. Therefore, an SNE exists, at the same point (1/3,3/4).
Here is an example in which the coalition consistency fails, and indeed there is no SNE.[3]: Example.3.1 There are two players, with strategy space [0,1]. Their utility functions are:
- u1(x) = -x1 + 2*x2;
- u2(x) = 2*x1 - x2.
There is a unique Nash equilibrium at (0,0), with payoff vector (0,0). However, it is not SNE as the coalition {1,2} can deviate to (1,1), with payoff vector (1,1). Indeed, coalition consistency is violated at x=(0,0): for the coalition {1,2}, for any weight-vector wS, the social-welfare-best-response is either on the line (1,0)--(1,1) or on the line (0,1)--(1,1); but any such point is not a best-response for the player playing 1.
Nessah and Tian[3] also present a necessary and sufficient condition for SNE existence, along with an algorithm that finds an SNE if and only if it exists.
Properties
editEvery SNE is a Nash equilibrium. This can be seen by considering a deviation of the n singleton coalitions.
Every SNE is weakly Pareto-efficient. This can be seen by considering a deviation of the grand coalition - the coalition of all players.
Every SNE is in the weak alpha-core and in the weak-beta core.[3]
Criticism
editThe strong Nash concept is criticized as too "strong" in that the environment allows for unlimited private communication. As a result of these requirements, Strong Nash rarely exists in games interesting enough to deserve study. Nevertheless, it is possible for there to be multiple strong Nash equilibria. For instance, in Approval voting, there is always a strong Nash equilibrium for any Condorcet winner that exists, but this is only unique (apart from inconsequential changes) when there is a majority Condorcet winner.
A relatively weaker yet refined Nash stability concept is called coalition-proof Nash equilibrium (CPNE)[2] in which the equilibria are immune to multilateral deviations that are self-enforcing. Every correlated strategy supported by iterated strict dominance and on the Pareto frontier is a CPNE.[4] Further, it is possible for a game to have a Nash equilibrium that is resilient against coalitions less than a specified size k. CPNE is related to the theory of the core.
Confusingly, the concept of a strong Nash equilibrium is unrelated to that of a weak Nash equilibrium. That is, a Nash equilibrium can be both strong and weak, either, or neither.
References
edit- ^ R. Aumann (1959), Acceptable points in general cooperative n-person games in "Contributions to the Theory of Games IV", Princeton Univ. Press, Princeton, N.J..
- ^ a b B. D. Bernheim; B. Peleg; M. D. Whinston (1987), "Coalition-Proof Equilibria I. Concepts", Journal of Economic Theory, 42: 1–12, doi:10.1016/0022-0531(87)90099-8.
- ^ a b c d Nessah, Rabia; Tian, Guoqiang (2014-06-15). "On the existence of strong Nash equilibria". Journal of Mathematical Analysis and Applications. 414 (2): 871–885. doi:10.1016/j.jmaa.2014.01.030. ISSN 0022-247X.
- ^ D. Moreno; J. Wooders (1996), "Coalition-Proof Equilibrium", Games and Economic Behavior, 17: 80–112, doi:10.1006/game.1996.0095, hdl:10016/4408.