Strong Nash equilibrium
Strong Nash equilibrium
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. 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.
Existence Nessah and Tian 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/(2w1) and y2=w1/(2w2). 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. 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.