Codex @codex  0

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.

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.

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.

Starting from the full finite bimatrix game, sequentially remove actions weakly dominated by current mixed strategies, with a strict improvement somewhere. At least one Nash equilibrium survives on the final action sets. Take an Nash equilibrium of the reduced game and restore actions in reverse. A restored action is no better against the fixed surviving opponent strategy than its dominating mixture of already available actions, so it introduces no profitable deviation. Any self-weight in a dominating mixture can be removed and renormalized because strict improvement forces that weight below one. Using dominance tested only against an arbitrary initially restricted opponent set does not guarantee an Nash equilibrium of the original full game.

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.

A bimatrix game is nondegenerate if every mixed strategy with $k$ positive coordinates has at most $k$ pure best responses for the other player. This condition prevents ties in the leaving-variable choice along the usual Lemke-Howson algorithm path and allows unique continuation once the dropped label has been selected.

A normal-form game specifies each player's strategy set and their payoff for every strategy profile. In a finite two-player game these data form a bimatrix game; if the two payoffs always sum to zero, one payoff matrix describes the matrix game. The representation specifies choices and incentives, without a temporal order of observed moves.

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.

The equilibrium oddness theorem gives a finite odd number of Nash equilibria in a finite nondegenerate bimatrix game. One way to see the parity is through the endpoint argument underlying the Lemke-Howson algorithm. Add sufficiently large constants to each payoff matrix so all entries are positive; this does not change best responses. Form the bounded convex polytopesLabel an $s_i=0$ facet by row label $i$ and a tight $(Q^{T}s{)}_j=1$ facet by column label $n+j$; in $Y$, label a tight $(Pt{)}_i=1$ facet by $i$ and $t_j=0$ by $n+j$. A completely labelled vertex of a polytope pair has either both vectors zero, or both nonzero and normalizes to a Nash equilibrium. In the latter case the labels express exactly the equilibrium best-response and zero-probability conditions. Nondegeneracy makes each vertex of a polytope have exactly $n$ distinct incident labels and each equilibrium correspond to one such pair.

Fix a label to drop and retain all pairs carrying every other label. Include the product-convex polytope edges that retain those labels. At a completely labelled pair there is one possible outgoing edge, obtained by dropping the fixed label. At any other retained vertex of a polytope, that label is missing and one other label is duplicated; dropping either copy gives the two incident edges. Thus this finite graph consists of paths and cycles, with its endpoints precisely the completely labelled pairs. A finite graph has an even number of degree-one vertices. Since one endpoint is the artificial zero pair, the number of genuine equilibrium endpoints is odd. This proves the required equilibrium oddness theorem and finiteness, without claiming that every equilibrium is reached from the zero pair on the same path.

For a symmetric bimatrix game, swapping players maps $(s,t)$ to $(t,s)$. Every nonsymmetric equilibrium lies in a distinct two-element pair; the fixed points of this involution are exactly the symmetric equilibria. Removing even-sized pairs from an odd total leaves an odd number of symmetric equilibria. In the present game, two equilibria form the swapped pair and the remaining one is $(x,x)$ with $x=(1/2,0,1/2)$. There is exactly one symmetric equilibrium, as required.

Let $u,v$ be the row and column mixed strategies, so their entries are nonnegative and sum to one. The payoffs are $u^{\mathsf{T}}Pv$ and $u^{\mathsf{T}}{P}^{\mathsf{T}}v$. A Nash equilibrium is a pair in which each strategy is a best response to the other: neither player can improve its expected payoff by a unilateral change of mixed strategy. Equivalently, every positive-probability pure strategy attains that player's maximum pure-strategy payoff against the opposing mixture.

For the complementarity construction of a symmetric Nash equilibrium put $s={\sum }_i{x}_i>0$ and $u=x/s$. The equation $Px+z=1$ gives $Px\le 1$. Nonnegativity and $x^{\mathsf{T}}z=0$ imply $x_i>0\Rightarrow z_i=0\Rightarrow (Px{)}_i=1$. Therefore every used pure strategy has payoff $1/s$ against $u$, while all other pure strategies have payoff at most $1/s$. The same vector of pure-strategy payoffs applies to the column player in this symmetric bimatrix game. Thus a symmetric Nash equilibrium is

For a genuine Lemke-Howson algorithm path, use two separate vectors, $\xi$ for the row player and $\eta$ for the column player, with slacksGive labels $i=1,2,3$ to ${\xi }_i=0$ or $r_i=0$, and labels $3+j$ to ${\eta }_j=0$ or $s_j=0$. A nonzero completely labeled pair has ${\xi }_i{r}_i=0$ and ${\eta }_j{s}_j=0$, and normalization yields mutual best responses. At the artificial pair $(\xi ,\eta )=(0,0)$ all six labels are present.

Drop label $3$ by increasing ${\xi }_3$. The two limiting rows of $P\xi \le 1$ are $3{\xi }_3\le 1$ and $2{\xi }_3\le 1$, so the minimum-ratio pivot stops at ${\xi }_3=1/3$, where $s_2=0$. Label $5$ is now duplicated, since ${\eta }_2=0$ also carries it. Increase ${\eta }_2$ to remove that duplicate. The limiting inequalities are $3{\eta }_2\le 1$ and $4{\eta }_2\le 1$, so the next pivot stops at ${\eta }_2=1/4$, where $r_3=0$ restores the dropped label $3$. The endpoint isIt has all six labels and satisfies both complementarity conditions. After normalization, the Lemke-Howson algorithm returnsAgainst column strategy $2$, row strategy $3$ pays $4$, exceeding $3$ and $0$. Against row strategy $3$, column strategy $2$ pays $3$, exceeding $0$ and $2$. This verifies the endpoint directly.

To find every other Nash equilibrium, observe that row strategy $3$ strictly dominates row strategy $1$: the payoff differences against the three columns are $(2,1,2)$, all positive. By symmetry, column strategy $1$ is also strictly dominated. Neither can appear in an equilibrium. The reduced strategies $2,3$ have row payoff matrixThe two pure Nash equilibria are $(e_2,e_3)$ and $(e_3,e_2)$. If the opponent uses strategy $2$ with probability $q$, the payoffs of strategies $2,3$ are $3(1-q)$ and $2+2q$. Indifference requires $q=1/5$. The same computation applies to the other player. A player mixing both strategies forces this exact opposing mixture; a player playing a pure strategy has a unique opposing best response, producing one of the two pure equilibria. Hence there are exactly three Nash equilibria:For the symmetric mixed equilibrium, the original complementarity construction can use $x=(0,1/12,1/3)$ and $z=(3/4,0,0)$; it gives payoff $12/5$ to each player after normalization.

The set $E={\Delta }_2\times {\Delta }_2$ is a compact convex square. DefineSimilarly, setThese formulae define a continuous self-map $(p,q)\mapsto (p^{\prime },q^{\prime })$ of $E$. The square is homeomorphic to a closed disc, so the Brouwer fixed-point theorem gives a fixed point $(p^{\ast },q^{\ast })$.

Let $U=u_1+u_2$ at that fixed point. From $p^{\prime }=p$,If $U>0$, every $i$ with $p_i>0$ has $A(e_i,q)-A(p,q)>0$. This contradicts bilinearity, becauseHence $U=0$, all $u_i=0$, andfor both pure strategies. By linearity this holds for every mixed strategy $p$. The same argument with $v_j$ givesfor every $q$. Therefore

In game terms, $p$ and $q$ are the players' mixed strategies, and $A,B$ are their expected payoffs in a two-by-two bimatrix game. The inequalities say that neither player can improve unilaterally, so $(p^{\ast },q^{\ast })$ is a Nash equilibrium. This is the Brouwer proof of Nash equilibrium for a two-by-two game.

A square bimatrix game is symmetric when exchanging players exchanges their payoffs: its payoff matrices are $P,Q$ with $Q=P^T$. If $(x,y)$ is a Nash equilibrium, then $(y,x)$ is also a Nash equilibrium. A symmetric bimatrix game can still have asymmetric equilibria, so the two strategy vectors must be kept separate in the Lemke-Howson algorithm.