Nash equilibrium

From DDWiki

The short definition provided in Non-Cooperative Game states that the Nash equilibrium is the state of such a game where players cannot change their profit by changing their strategy. John Nash published his work on Non-Cooperative Games in 1951. He expands the theory on zero-sum games provided by Von Neumann and Morgenstern who published their work in "Theory of Games and Economic Behavior". According to Nash, this book analyzes cooperative games, where players are allowed to form coalitions and make decisions with knowledge of other player's strategies (Nash, 1951). Nash's expansion focuses on the Non-Cooperative Game in which players make their decision without knowledge of other player's strategies.

1 Formal Description
2 Calculations of Nash Equilibrium
3 Existence and Uniqueness of Nash Equilibrium
4 References

Formal Description

Before we describe the formal derivation of the Nash Equilibrium we need to define a few terms that will be used below.

Finite Game

A game consisting of n persons each one with a finite set of pure strategies and each player "i" has a payoff function $p i$ .

Mixed Strategy

Defined as "a collection of non-negative numbers with a unit sum". Formally this can be written as:

$\quad s_i = \sum_{\alpha} c_{i,\alpha}$

where $\quad \sum_{\alpha} c_{i,\alpha} = 1$ and $α$ = one pure strategy.

Payoff Function

There is one payoff (utility) function characteristic to each strategy describing the benefit of each strategy.

$u_i(\mathbf{s}) = u_i (s_1,s_2,...,s_n)$

Nash says that the equilibrium is the "set of all pairs of opposing good strategies" which means in plain language that every player has reached a point where his strategy good. That means nobody feels the need for improvement.

Mathematically, this can be described as $u_i = \max( \mathbf{s} ,r_i)$ for all $\ qual r_i 's$ or in words each player's mixed strategy maximizes his payoff if the strategies of the others are held fixed.

Calculations of Nash Equilibrium

The formulation of the Nash Equilibrium shows that its solution is simply a maximum of a certain payoff function. This fact makes it solvable by basic numerical gradient based methods or gradient free methods. Both methods require that two conditions are met by the payoff function at a stationary point $\mathbf{s_0}$ .

The first (necessary) condition states that $\nabla p = \frac{\partial{p}}{\partial{\mathbf{s}}}$ (the gradient of the payoff function) is zero for identification of a critical point.

The second (sufficient) condition states that $\nabla ( \nabla p) = \frac {\partial{}}{\partial{\mathbf{s}}}(\frac {\partial{p}}{\partial{\mathbf{s}}})$ (the "Hessian Matrix") is negative definite for the critical point to be a maximum (that means all Eigenvalues are less than zero). If the Hessian is positive definite $\mathbf{s_0}$ is a minimum (and thus not a Nash Equilibrium point). If the Hessian is equal to 0 at $\mathbf{s_0}$ , we cannot draw any information about the nature of the stationary point and need to investigate higher order terms.

McKelvey and McLennan offer a variety of more advanced and refined algorithms for calculations of single or multiple Nash Equilibriums in Computation of Nash Equilibria published in 1996 (using the incorrect plural of Equilibrium was their idea)

Existence and Uniqueness of Nash Equilibrium

Author	Strategy assumptions for NE existence	Payoff assumptions for NE existence	Conditions for NE uniqueness
Nash (1951)^[1]	Simplexes	Bilinear functions of the strategies
Rosen (1965)^[2]	Nonempty, compact and convex in Rⁿ	Each player's individual payoff function is concave in his own strategy sets	Jacobian J is negative quasi-definite for all strategies
Karamadian (1969)^[3]	Nonempty, convex and non-negative orthant Rⁿ₊ (removed compactness from Rosen)	Each player's individual payoff function is concave in his own strategy sets	Payoff function is continuous and strongly monotone on strategies
Gabay and Moulin (1980) ^[4]	Nonempty, convex and non-negative orthant Rⁿ₊	1) Twice continuously differentiable on strategies X; 2) Pseudoconcave with respect to X; 3) First-order derivative is coercive in 'X'.	Jacobian is strictly diagonally dominant.

Note:

The elements in the Jacobian matrix J(x) are $\frac{\partial^2 u_i(x)}{\partial x_i(x)x_j(x)}; \forall i,j \in{1,....,n}$
A diagonally dominant Jacobian means: $\|\frac{\partial^2 u_i}{\partial x_i^2}\| > \sum_{j \neq i}\|\frac{\partial^2 u_i}{\partial x_ix_j}\|; \forall i,j \in{1,....,n}$

References

↑ J. Nash, 1951, "Non-Cooperative Games," The Annals of Mathematics, 54(2), 286-295.
↑ J.B. Rosen, 1965, "Existence and Uniqueness of Equilibrium Points for Concave N-Person Games," Econometrica, 33(3), 520-534.
↑ S. Karamardian, 1969, "The nonlinear complementarity problem with applications," J. Optimization Theory Appl. 4, Part I, 87-98, Part II, 167-181.
↑ D. Gabay and H. Moulin., 1980, "On the uniqueness and stability of Nash equilibria in non-cooperative games, eds." A. Bensoussan, P. Kleindorfer, and C.S. Tapiero, Applied Stochastic Control of Econometrics and Management Science (North-Holland, Amsterdam, 1980).