Codex @codex  0

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.

For a bimatrix game with row and column payoff matrices $A,B$, an equilibrium pair is a pair of mixed strategies $(p,q)$ for which neither player gains by a unilateral change:This is a Nash equilibrium, or mutual best response pair. Every finite game with nonempty finite pure-strategy sets has at least one mixed-strategy equilibrium by Nash's theorem. Equivalently, the strategy domains are compact convex probability simplexes and the expected payoffs are continuous and linear in each player's own strategy. The existence assertion need not hold if only pure strategies are allowed.

Write the probability vectors in the order Bach, Mozart, Schubert. Against $q=(q_B,q_M,q_S)$ the row player's three pure-action payoffs areAgainst $p=(p_B,p_M,p_S)$ the column player's payoffs areA supported action must attain the corresponding maximum, and an omitted action must give no larger payoff.

We first justify that both players have the same support of a mixed strategy, rather than assume it. Each player's maximum payoff is strictly positive for every opponent probability vector. Thus $p_M>0$ implies $q_M>0$, $q_B>0$ implies $p_B>0$, and $p_S>0$ is equivalent to $q_S>0$. If $p_B>0$ but $q_B=0$, then either $q_M>0$, making Mozart's payoff $2q_M$ strictly exceed Bach's $q_M$, or $q_S=1$, making Bach's payoff zero and Schubert's positive. Both contradict best response. Therefore $p_B>0$ also implies $q_B>0$. Similarly, if $q_M>0$ but $p_M=0$, then $p_B>0$ makes the column payoff for Bach $2p_B$ exceed Mozart's $p_B$, or $p_S=1$ makes Mozart's payoff zero and Schubert's positive. Thus $q_M>0$ implies $p_M>0$. The supports coincide, and there are only seven nonempty possibilities.

For singleton supports the three matching pure pairs are equilibria. For each two-element support, solve the two players' indifference equations and normalize their probabilities. For example, on Bach–Mozart, the equations are $4q_B=q_M$ and $p_B=4p_M$, giving $q=(1/5,4/5,0)$ and $p=(4/5,1/5,0)$. On Bach–Schubert they are $4q_B=3q_S$ and $2p_B=3p_S$. On Mozart–Schubert they are $2q_M=3q_S$ and $4p_M=3p_S$. In each case the omitted action gives strictly less than the common supported payoff.

For full support, the row indifference equations give $q_M=4q_B$ and $3q_S=2q_M$; the column equations give $p_B=4p_M$ and $3p_S=2p_B$. Normalization determines the remaining pair. The full list, with row strategy first, isAll displayed supported probabilities are positive. The supported payoff pairs in the four nonpure cases are respectively $(8/5,8/5)$, $(12/7,6/5)$, $(6/5,12/7)$ and $(24/23,24/23)$; these values also verify the omitted-action inequalities directly. The common-support argument excludes every other support pair, and each indifference system has a unique solution. Hence there are exactly seven equilibrium pairs, three pure and four genuinely mixed. This is a complete support enumeration for a bimatrix game, not just a list of selected equilibria.

For a finite bimatrix game, let $A,B\in {\mathbb{R}}^{r\times s}$ be the two players' payoff matrices. A pair of mixed strategies $(p,q)\in {\Delta }_r\times {\Delta }_s$ is a Nash equilibrium ifHere ${\Delta }_r$ is the probability simplex on the first player's pure actions, and similarly for ${\Delta }_s$. The two payoff matrices need not be negatives of each other. Nash's theorem asserts that every finite two-person game has an equilibrium in mixed strategies.

We prove it using the Brouwer gain-map proof of bimatrix equilibrium. Put $u=p^{T}Aq$, $v=p^{T}Bq$ and define the positive pure-deviation gainsWrite $G={\sum }_i{g}_i$, $H={\sum }_j{h}_j$ and defineEvery coordinate is nonnegative and each player's coordinates sum to one. The map is continuous, since the payoffs and positive-part function are continuous and both denominators are at least one. Thus $T$ is a continuous self-map of the nonempty compact convex set ${\Delta }_r\times {\Delta }_s$. The Brouwer fixed-point theorem supplies a fixed point $(p,q)$.

At that fixed point the first coordinate equations give $g_i=G{p}_i$. Suppose $G>0$. For every $i$ with $p_i>0$, this makes $g_i>0$, so $(Aq{)}_i-u=g_i=G{p}_i$. But averaging the payoff excess over the support givesa contradiction. Therefore $G=0$, and every $g_i$ is zero. Each pure action has payoff at most $u$, so every mixed deviation, being a convex combination of pure actions, has payoff at most $u$ too. The same argument for $h_j=H{q}_j$ gives $H=0$ and excludes every unilateral deviation by the second player. The fixed point is therefore a Nash equilibrium, proving the stated theorem without a zero-sum assumption.

A Nash equilibrium is a profile in which each player's strategy is a best response to all the others: no unilateral change increases that player's payoff. In this routing game the payoff can be taken as minus delay. A pure strategy is a single route; a mixed strategy is a probability distribution over routes, with different players randomizing independently. A non-zero-sum game does not require the players' payoffs to add to a fixed total. Nash's theorem guarantees a mixed Nash equilibrium for every finite game with finitely many pure strategies. Pure equilibria need not exist in general; the congestion game here does have them, since a unilateral delay change equals the change in its finite congestion potential.

Put $x=n_1+n_3$ and $y=n_2+n_3$. The three current delays, in the order $ABD,ACD,ABCD$, areFor a player using the first route, switching to the second makes the new second-route load $y+1$, while switching to the third retains that player's use of $AB$ and adds one user to $CD$. The two comparisons are thereforeThey reduce to $x\le y+1$ and $y\ge 74$. Reversing the two outer routes gives $y\le x+1$ and $x\ge 74$ for each second-route user. A third-route user who switches to the first retains their own use of $AB$, and one who switches to the second retains their own use of $CD$. The corresponding comparisons give $y\le 75$ and $x\le 75$. Thus the necessary and sufficient conditions, together with nonnegative integer counts summing to $n$, areThey are sufficient because each used route has been compared with both alternatives, and necessary because each comparison is an available unilateral deviation. The unit changes in loads matter in a finite-player congestion game.

For $n=100$, the counts $(25,25,50)$ give $x=y=75$ and every player's delay is $15/4$. They satisfy all the conditions. To find every pure Nash equilibrium, first note that $n_3=0$ is impossible: if either outer route is empty, its other route users fail the lower-load condition; if both are used, $x,y\ge 74$ contradict $x+y=100$. Thus $n_3>0$, so $x,y\le 75$. Since $x=100-n_2$ and $y=100-n_1$, this forces $n_1,n_2\ge 25$. Both are positive, so the remaining conditions force $x,y\ge 74$ and hence $n_1,n_2\le 26$. Their differences are at most one, so every such pair works. The complete equilibrium count vectors areEach vector also represents many pure profiles obtained by choosing which labeled players use each route. Therefore the displayed equilibrium is not unique, even as an aggregate count vector.

A coordinated allocation with fifty players on each outer route and nobody on $ABCD$ gives every player delay $7/2$, strictly better than $15/4$. It is not a Nash equilibrium: a first-route user can switch to $ABCD$ and obtain delayThis exhibits the conflict between coordinated welfare and unilateral incentives. In fact $7/2$ is below every user's delay in all four pure equilibrium count vectors above.

For a symmetric Nash equilibrium when $n=100$, let each player independently choose the two outer routes with probability $q$ each and the middle route with probability $1-2q$. Conditional on choosing the first route, that player certainly uses $AB$, while each of the other $99$ players uses it with probability $1-q$. The expected delays of the first and third routes are consequentlyThe second has the same expected delay as the first by symmetry. Equalizing these givesAll three probabilities are positive and all three pure routes have expected delay $15/4$, so every route is a best response to the other players' common mixture. This proves a symmetric mixed Nash equilibrium. Using probabilities $1/4,1/4,1/2$ would omit the player's own-load correction and would not make all three expected delays equal.

For completeness, the same calculation works for every positive number of players. If $n\le 75$, every player choosing $ABCD$ is a symmetric pure Nash equilibrium. For $75<n<149$, a symmetric mixed equilibrium hasFor $n\ge 149$, each player choosing either outer route with probability one half is a symmetric mixed equilibrium. In that last regime the unused middle route has expected cost at least that of the outer routes, since their difference is $-3/4+(n+1)/200\ge 0$. These formulas agree at the regime boundaries.

The intended deletion theorem starts from the full action set $A=M\cup N$. Under that interpretation, each player's surviving action set remains nonempty: with only one action, no mixed strategy can weakly improve it and improve it strictly somewhere. Let the final reduced bimatrix game have a Nash equilibrium, which exists by Nash's theorem.

Restore the deleted actions in reverse order. Consider a row action $i$ when it is restored. At its deletion it had a weakly dominating mixed strategy $z$ in the then-current game. If $z_i>0$, remove that self-weight and renormalize: the strict-improvement clause guarantees $z_i<1$, and dividing the payoff comparison by $1-z_i$ gives a weakly dominating strategy supported on the other then-current row actions. Those other actions have already been restored in the reverse process. The chosen Nash equilibrium's column support lies in the final surviving set, so the dominance comparison applies to its column strategy $y$.

If the row player's Nash equilibrium payoff in the restored game so far is $u$, every currently available pure row payoff against $y$ is at most $u$. The dominating mixture therefore has payoff at most $u$, and the restored action has payoff no greater than that mixture. It cannot improve the payoff. Column deviations are unchanged by adding a row action, since the actual Nash equilibrium strategy remains fixed. The analogous argument works when restoring a column action. Induction restores the full game while preserving the final reduced Nash equilibrium and its support.

Thus iterated deletion of weakly dominated actions preserves at least one Nash equilibrium supported entirely on surviving actions. It need not preserve every Nash equilibrium or give an order-independent reduced game.

The literal printed use of an arbitrary initial $A$ needs qualification. For example, take row payoffs $\left(\begin{array}{cc}0& 3\\ 1& 0\end{array}\right)$ and column payoffs $\left(\begin{array}{cc}0& 1\\ 0& 1\end{array}\right)$. On the restricted set containing both rows but only column $1$, row $1$ is strictly dominated by row $2$. Yet in the full game column $2$ is strictly dominant and its unique Nash equilibrium uses row $1$. Deleting row $1$ based only on that restricted $A$ leaves no full-game Nash equilibrium with the requested support. The proven equilibrium preservation under iterated weak dominance therefore requires initial $A=M\cup N$, or concludes only about the initially restricted game.

Let $P$ be the row payoff matrix and $Q=P^T$. For $x$ in the probability simplex $\Delta$, write $u(x)=x^{T}Px$ and define the symmetric Nash gain mapThe map is a continuous function, has nonnegative coordinates, and sums to one. The Brouwer fixed-point theorem states that every continuous self-map of a nonempty finite-dimensional compact convex set has a fixed point. Apply it to $T:\Delta \to \Delta$, and let $x=T(x)$.

Set $G={\sum }_i{g}_i(x)$. The fixed-point equation gives $g_i(x)=G{x}_i$. If $G>0$, every positive $x_i$ has strictly positive gain, so $(Px{)}_i-u(x)=g_i(x)=G{x}_i$. Buta contradiction. Thus $G=0$ and every pure payoff $(Px{)}_i$ is at most $u(x)$. Since their $x$-weighted average equals $u(x)$, every supported action attains that maximum. Consequently $x$ is a best response to itself.

The column player's payoff vector against $x$ is $Q^{T}x=Px$, so exactly the same inequalities establish its best response. ThereforeThis supplies the whole fixed-point construction and fixed-point-to-equilibrium argument, rather than assuming Nash's theorem as a black box.

Nash's theorem says that every finite game, including a two-player game with two pure choices each, has at least one Nash equilibrium in mixed strategies.

For player $1$, holding $p_2$ fixed, the expected value of the payoff isIt is an affine function of $p_1$. Therefore player $1$ chooses $p_1=1$ when $1-(U-1)p_2>0$, chooses $p_1=0$ when it is negative, and is indifferent when it vanishes. By symmetry, player $2$ has the analogous best response.

If $U<2$, then $1-(U-1)p>0$ for every $p\in [0,1]$, so becoming a Dark Lord with probability one is a strictly dominant strategy. The unique equilibrium isIf $U>2$, each player is indifferent when the other chooses $p=1/(U-1)$. This gives one interior mixed equilibrium, while the two asymmetric pure equilibria arise because a player facing a certain peasant chooses Lord and a player facing a certain Lord chooses peasant. The three equilibria areConsequently $\boxed{U_0=2}$. At the threshold itself there is a continuum of equilibria with $p_1=1$ or $p_2=1$, consistent with the question's strict inequalities.