Nash equilibrium (${\sigma }^{\ast }$)

A Nash equilibrium is a strategy profile in which every player's strategy is a best response to the others. For a finite game and mixed strategies, its precise condition isThe opponents' strategies ${\sigma }_{-i}^{\ast }$ are held fixed while testing each unilateral deviation. Equality is allowed: a player may have other equally good best responses. Because expected payoff is a linear function of the player's own mixture, it suffices to test every pure strategy. Equivalently, every choice in the support of a mixed strategy must attain the largest pure-choice expected payoff, and no unused choice may exceed it.

The two worked examples illustrate different uses of this condition. Matching pennies has no pure strategy Nash equilibrium, but its unique mixed strategy Nash equilibrium removes each player's vulnerability to predictable play. The asymmetric coordination example has three Nash equilibria, and its mixed one fails Pareto efficiency. A Nash equilibrium tests individual incentives, whereas Pareto efficiency compares feasible outcomes that may require several players to change together. In the prisoner's dilemma, for example, mutual defection is a Nash equilibrium even though mutual cooperation gives both players a larger payoff because $R>P$.

Existence in a finite game is guaranteed by Nash's theorem. The theorem does not select one Nash equilibrium, promise Pareto efficiency, or assert convergence of a learning process. Nash's ^[ref] used the Kakutani fixed-point theorem; his ^[ref] gave a proof using the Brouwer fixed-point theorem. The connection to a fixed point captures the idea of choices that remain mutually optimal when considered together.

A Nash equilibrium in which every player's mixed strategy is a fully mixed strategy. Every available action must therefore give the same maximal expected payoff against the others' choices. These indifference equations, together with strictly positive probabilities summing to one, suffice to verify such a Nash equilibrium.

Given a Boolean game and a query propositional formula $\varphi$, decide whether some pure strategy Nash equilibrium satisfies $\varphi$. The problem is complete for the existential second level of the polynomial hierarchy.

For membership, existentially choose a Boolean valuation and universally check every player's every unilateral deviation. The goal must remain false under all such deviations for each player whose goal is currently false. Each individual check takes polynomial time.

For hardness, start with a two-block quantified Boolean formula $\exists X\forall Y\psi (X,Y)$. Give player 1 control of $X$ and the constant true goal. Give player 2 control of $Y$ and goal $\neg \psi$, and use $\psi$ as the query. A queried Nash equilibrium exists exactly when some choice of $X$ leaves player 2 unable to falsify $\psi$ by changing $Y$. This is precisely the input quantified statement, and the construction is a polynomial-time reduction.

There are $mq$ distinctly ranked students and $m$ labelled universities with $q$ seats each. Each student applies to one university; each university selects the greatest ranks, and admitted students receive their admitted cohort's average rank. At a pure Nash equilibrium, every student is admitted: any rejected student could move to a university with a vacancy. The university with the largest average must contain the top $q$ ranks, since any omitted higher rank could displace its lowest rank and improve. Repeat on the remaining students to obtain consecutive rank blocks. Assigning these blocks to the labelled universities gives exactly $m!$ pure equilibria.

In a game invariant under permuting players, a symmetric Nash equilibrium gives every player the same strategy, which may be a mixed strategy. Independent randomization does not require realized resource loads to be equal. When resource delays are affine, a player's expected delay depends on their own certain resource use plus the expected use by the other players; replacing all loads by unconditional total expected loads loses that own-player correction.

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 finite game, pure-action expected payoffs $e(i,p)$ against independent identical opposing mixed strategies are continuous. The displayed map takes the probability simplex continuously into itself. At a Brouwer fixed-point theorem fixed point, put $r_i=[e(i,p)-e(p){]}_{+}$ and $S={\sum }_i{r}_i$. The fixed-point equations give $r_i=p_{i}S$. If $S>0$, every supported action has strictly positive excess payoff, contradicting ${\sum }_i{p}_i(e(i,p)-e(p))=0$. Hence $S=0$ and every supported action is a best response, proving a symmetric Nash 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.

For each player in a finite bimatrix game, add the positive pure-strategy gains to its current mixed strategy and normalize. This gives a continuous self-map of the product of probability simplices. At a Brouwer fixed-point theorem fixed point, the gain coordinates equal the current strategy times their total gain. If that total were positive, every supported action would beat the current average payoff, contradicting that average. Thus every pure deviation has nonpositive gain for both players, proving a Nash equilibrium.

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.