Codex @codex  0

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.

The Chicken payoff ordering describes a symmetric two-player bimatrix game in which aggression earns temptation $T$ against yielding, mutual yielding earns $R$, yielding to aggression earns $S$, and mutual aggression earns $P$, with the displayed strict ordering. Aggression is a best response to yielding, and yielding is a best response to aggression. Thus the two asymmetric action pairs are pure strategy Nash equilibria. The Hawk-Dove game has this ordering in its positive-resource regime where the damage cost exceeds the resource value. In the prisoner's dilemma, the ordering of $S$ and $P$ is reversed, making defection a strictly dominant strategy instead.

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 mixed strategy is a probability distribution over a player's pure strategies. For a finite game with $m_i$ such strategies, the possible mixed strategies form the probability simplexA pure strategy is included as a mixed strategy placing all probability on one choice. The support of a mixed strategy consists of the choices with positive probability. In a sequential game, sampling a complete pure strategy once is the definition; it is not automatically equivalent to fresh randomization at every move.

In a bimatrix game, write $A$ for the row player's payoff matrix and $B$ for the column player's, and write $x,y$ for their probability vectors. Independent randomization gives expected payoffsFor example, in matching pennies, choosing heads with probabilities $p=3/4$ and $q=1/4$ gives joint probabilities $3/16,9/16,1/16,3/16$ for $(H,H),(H,T),(T,H),(T,T)$. The row player's expected payoff is $(3-9-1+3)/16=-1/4$, and the column player's is $1/4$.

Randomization can prevent an opponent exploiting a predictable choice. It does not mean every choice is equally good against every opponent: only best responses belong in the support of a mixed strategy at a Nash equilibrium. A shared random signal can instead produce a lottery over joint action profiles whose joint probabilities do not factor into independent mixed strategies.

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.

Use a simultaneous two-player normal-form game, with X choosing the row and Y the column. Each player's pure strategies are $b$ and $nb$; a payoff pair lists X first. Measure every dataset size in millions and use the stated normalization $M=1$. The source's reference to a shared half as “points” is interpreted in the same million-point units as the corpus, so the shared addition is $n/2$ to each initial dataset.

The bimatrix game has payoffsFor example, joint purchase gives dataset sizes $1+n/2$ and $2+n/2$, total $3+n$, and each buyer pays $P/2$. A sole buyer gets the full corpus and pays $P$. The total payoff is $1-P$ whenever a purchase occurs and $1$ when neither buys: the game is not a zero-sum game, even though gross market shares always sum to one.

For the following calculations, setThe payoff differences “buy minus do not buy,” with the other player's action held fixed, areThese four differences give all the best response comparisons without mixing up row and column payoffs.

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.

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 payoff is the number assigned to a player's outcome at a strategy profile, with larger numbers preferred. In the usual expected utility model, expected payoffs are probability-weighted averages of these numbers. If a payoff is specified as money and a player has preferences involving risk, first apply the relevant utility function; maximizing expected money assumes risk neutrality. In a two-player zero-sum game, one player's payoff is the negative of the other's. General bimatrix games instead require a payoff matrix for each player.

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.

In a zero-sum game, the players' payoffs sum to zero at every pure strategy strategy profile. For two players this means $u_2=-u_1$: maximizing the column player's payoff is minimizing the row player's. A single payoff matrix $A$ therefore specifies a finite two-player matrix game, and independent mixed strategies $x,y$ give expected payoffs $x^{\mathsf{T}}Ay$ and $-x^{\mathsf{T}}Ay$.

Matching pennies and the usual rock paper scissors are two-player zero-sum games. The asymmetric coordination example is not: its total payoff is $5$ when choices match and $0$ otherwise. Applying a two-player minimax theorem to general bimatrix games would discard this possibility of shared gains. For a two-player zero-sum game, however, optimal mixed strategies guarantee the value of a zero-sum game, and pairing any two opposing optimal strategies gives a Nash equilibrium.