display | more...

A concept in game theory conceived of by mathematician John Nash.

A Nash equilibrium is the best choice of strategy in a game, regardless of the strategies of opposing parties.

An example of a Nash equilibrium can be found in the game known as the Prisoner's Dilemma, where it is better for each prisoner to choose to betray his/her partner in crime, rather than cooperate with the authorities and risk being betrayed (though the same does not apply to iterated versions of this game).

The Nash Equilibrium (due to John Nash) is one way (the most popular) to predict the outcome of a particular game. It's the central concept in noncooperative game theory, and what most people mean when they refer to game theory. Informally, the Nash equilibrium is the situation in a game when your move is the best possible one given everyone else's moves, and everyone else's moves are the best possible given your move, etc.

More formally, a Nash equilibrium is the ordered set of strategies—one for each player in the game—such that no single player can get a higher utility by choosing a different strategy.

There’s two kinds of Nash equilibria. A pure strategy Nash equilibrium is one in which everyone chooses a simple action as their strategy. A mixed strategy Nash equilibrium is one in which the players choose probabilities with which each of their strategies will be played and then back off and let chance make the actual move.

In the latter case, no player can choose a better probability function. The pure strategy case is technically a special case of the mixed strategy, with a probability of one on a single action.

The Nash equilibrium is applied to games in strategic form or normal form, which means to games in which everyone makes exactly one move, and does so simultaneously. For dynamic games (frequently meaning extensive form games), where players make moves sequentially, there are a large number of equilibrium refinements. Nash proved that a mixed strategy equilibrium exists for any game which has a finite number of players, each with a finite set of possible strategies. There can often be multiple equilibria for a game. There isn’t always a pure strategy equilibrium. Reportedly, John von Neumann wasn’t very impressed with the proof, saying, "That's trivial, you know. That's just a fixed-point theorem."

A particularly strong kind of Nash equilibrium is an equilibrium in dominant strategies. That’s when every player has a single best move regardless of the other players’ moves. The Prisoner's Dilemma is an example of a Nash equilibrium in dominant strategies.

Broadly speaking, a set of players following specific strategies are in Nash equilibrium if no one participant can guarantee an advantage by changing strategy. Whilst the outcome of an equilibrium strategy may not be the best conceivable for any given player, to follow the strategy is their best plan in the absence of knowledge of their opponents' plays. The Nash Equilibrium is one of the most fundamental results in non-cooperative game theory, providing a significant generalisation to John Von Neumann's earlier notion of value in zero-sum games, a part of his Minimax theorem for such games.

Adopting the notation of strategic form games, we may make this notion precise as follows. For an n-player general sum strategic form game X1,...,Xn, each strategy space Xi, consisting of strategies {x1, . . . , xmi} will give rise to a space of mixed strategies SXi. These consist of mi-tuples (pi1, . . . , pimi) which describe the probability of player i picking strategy xj ∈ Xi as pij . For these probabilities to be valid, we additionally require that for each i the sum of the pij's is 1, with each being in the range 0 to 1.

Further, we can simplify notation by identifying the strategy sets Xi with the integers {1, . . . ,mi}- that is, playing '1' corresponds to a strategy of x1 and so on.

Thus the expected return to player j when each player has mixed strategy pj is given by

Ej(p1,...,pn)= Σi1=1:m1...Σin=1:mnp1i1...pninaj(i1,...,in)

Where each ai is the appropriate payoff function.

Nash's Theorem

With the above notation,
Definition: A set of mixed strategies (p1, . . . , pn) ∈ SX1 × ... × SXn is an n-player Nash equilibrium for the game given by strategic form X1, . . . ,Xn if no player gains by unilaterally deviating from the equilibrium.
More formally, if ∀ i from 1 to n and for any p'∈ SXi,

Ej(p1,...,pi-1,pi,pi+1,...,pn) ≥ Ej(p1,...,pi-1,p',pi+1,...,pn)

Then (p1, . . . , pn) is a Nash equilibrium (since no player j benefits from changing from strategy pj to any other strategy p').

Existence of a unique Nash equilibrium in any two player zero-sum game follows from the Minimax theorem; this is demonstrated directly for the 2×2 case in the saddle point writeup and follows by dominated strategies or linear programming techniques for games with larger strategy sets.

The Prisoner's dilemma gives rise to a Nash equilibrium (mutual defection, see dominated strategy for discussion), as does the iterated version, indicating that the zero-sum condition is not necessary. In his 1950 dissertation, John Nash proved that much more was true:

(Nash's theorem) Any finite n-player game in strategic form has a Nash equilibrium.

It is worth noting what this theorem does not say alongside what it does; there is no claim of uniqueness, nor can there be, as the Stag Hunt demonstrates.

The proof of this result depends on some topology and delicate notation, which I won't attempt in raw HTML (the definitions earlier in this writeup are ugly enough!). The interested reader can find a proof in section 4.2.1 of the print version of this work described on the homenode.

Part of A survey of game theory- see project homenode for details and links to the print version.

Log in or register to write something here or to contact authors.