Nash equilibrium

A Nash equilibrium is a strategy profile in which no player can increase their expected payoff by changing only their own strategy.

A finite nondegenerate bimatrix game has a finite odd number of Nash equilibria. After shifting to positive payoffs, fully labelled vertex pairs in the bounded best-response polytopes correspond to equilibria plus one artificial zero pair. Dropping a fixed label gives a finite path graph whose endpoints are exactly these pairs. The number of endpoints is even, leaving an odd number of genuine equilibria. This is the endpoint-parity argument underlying the Lemke-Howson algorithm.

A symmetric equilibrium of a symmetric game has every player use the same strategy or the same distribution of strategies. Symmetry between players does not require identical behavior across contests with different prizes.

In a nondegenerate symmetric bimatrix game, player interchange pairs every nonsymmetric Nash equilibrium with a distinct swapped equilibrium. The equilibrium oddness theorem gives an odd total; the remaining fixed points, which are the symmetric equilibria, therefore also number an odd amount.

The continuous gain map takes a probability simplex to itself. The Brouwer fixed-point theorem supplies a fixed point, whose positive gains would contradict the zero strategy-weighted average payoff excess. Thus all gains vanish, giving a strategy that is a best response to itself. In a symmetric bimatrix game, this produces a symmetric equilibrium.

For a symmetric bimatrix game with payoff matrices $P,P^{\mathsf{T}}$, any nonzero $x$ satisfying these equations gives the symmetric Nash equilibrium $(x/{\sum }_i{x}_i,x/{\sum }_i{x}_i)$. Every positive coordinate attains the same maximal payoff. This one-vector construction differs from a two-vector Lemke-Howson algorithm path, which can return asymmetric equilibria.

The Lemke-Howson algorithm follows an almost completely labeled path in the product of two best-response polytopes of a bimatrix game. Drop one label at the artificial zero pair, then alternately pivot away the duplicated label until the dropped label returns. A nonzero completely labeled endpoint, after normalization, gives a Nash equilibrium. The two players' vectors must be kept separate even in a symmetric game.

Complementary pivoting follows adjacent bases while maintaining all but one label of a complementarity system. The Lemke-Howson algorithm for a bimatrix game follows the duplicated label between two tableaux until it restores the dropped label at a nonzero completely labelled pair. Normalization then gives a Nash equilibrium.

Nash's theorem states that every finite game has at least one Nash equilibrium in mixed strategies.

Normalize each player's positive pure-strategy payoff improvements to define a continuous self-map of the product of their mixed-strategy simplices. At a Brouwer fixed point every positive improvement must vanish, giving a Nash equilibrium.