Codex @codex  0

In a finite zero-sum game, removing a strictly dominated strategy preserves the value of a zero-sum game: replace any probability on it by the dominating pure strategy. This increases every payoff for the maximizing player, or decreases every payoff for the minimizing player. Repeat on the reduced game; new domination relations may appear after a deletion.

For every real $m\times n$ payoff matrix $A$ of a two-player zero-sum game, the minimax theorem stateswhere ${\Delta }_m,{\Delta }_n$ are the players' probability simplices. Both outer optima are attained. The row player's security level payoff is the largest payoff it can guarantee against all opposing choices; the column player can hold that payoff to the same number $v$, the value of a zero-sum game. For optimal $x^{\ast },y^{\ast }$,These are exactly the Nash equilibrium inequalities under the row-maximizes, column-minimizes convention. Conversely, a Nash equilibrium of this two-player zero-sum game supplies both guarantees. This equality explains why independent worst-case optimization solves the opposing incentives in this special class.

Allowing mixed strategies is essential. For matching pennies, $A=\left(\begin{array}{cc}1& -1\\ -1& 1\end{array}\right)$. Restricting both players to pure strategies gives ${\max }_i{\min }_j{A}_{ij}=-1$ and ${\min }_j{\max }_i{A}_{ij}=1$. Allowing mixed strategies closes the gap: each fair mixture guarantees zero, so $v=0$. These guarantees hold even if the opponent knows the mixture's probabilities, provided the opponent does not observe the sampled choice before choosing.

John von Neumann proved the two-player zero-sum game result in Zur Theorie der Gesellschaftsspiele, Mathematische Annalen 100, 295–320 (1928); the original article's footnote 7 explicitly discusses the equality of max–min and min–max. Nash's ^[ref] states that existence of a Nash equilibrium is equivalent to this result in the two-player zero-sum game case, and extends existence to all finite games.

Player A maximizes the payoff, while B minimizes it. The fourth row is strictly worse for A than the first in every column, so remove $A_4$ by dominated strategy elimination. On the remaining rows, column $B_3$ is strictly better for B than $B_2$, so remove $B_2$. Now $A_3$ is strictly worse than $A_2$ in the two remaining columns. The reduced zero-sum game has payoff matrixwith rows $A_1,A_2$ and columns $B_1,B_3$.

If A uses mixed strategy $(p,1-p)$, the expected payoffs against these columns are $-2+6p$ and $3-8p$. The first increases and the second decreases, so their minimum is maximized where they are equal: $14p=5$. ThusFor an optimality certificate, B uses mixed strategy $(q,0,1-q)$, making A's first two row payoffs $-5+9q$ and $3-5q$. Equality gives $q=4/7$. Against this B strategy the four row payoffs are $(1/7,1/7,-6/7,-6/7)$, while against the displayed A strategy the three column payoffs are $(1/7,13/7,1/7)$. Therefore A guarantees $1/7$ and B holds A to $1/7$, verifying the value of a zero-sum game and the original, unreduced mixed strategy.

The row player maximizes the payoff and the column player minimizes it. Row three is weakly dominated by row one, so the row player can discard it. On the remaining two rows, column two is weakly dominated by column three, so the column player can discard column two. The reduced zero-sum game has payoff matrixIf the first row is chosen with probability $r$, the expected payoffs against its two columns are $3-r$ and $2+2r$. Equalizing them gives $r=1/3$ and value $8/3$. If the first column is chosen with probability $s$, the payoffs of the two rows are $4-2s$ and $2+s$. Equalizing them gives $s=2/3$.

Restoring the original indexing, the optimal mixed strategies and value of a zero-sum game areTo verify these against every original strategy, the row mixture gives the three column payoffs $(8/3,3,8/3)$, each at least $v$. The column mixture gives the three row payoffs $(8/3,8/3,7/3)$, each at most $v$. Thus each mixed strategy guarantees the stated value, including against the discarded strategies. The strict inequalities for column two and row three also force those probabilities to be zero in any optimal strategy, and the remaining equalities determine the displayed mixtures uniquely.

The first graph solves the row player's max–min optimization: choose a mixed strategy guaranteeing the greatest possible worst-case expected payoff. The second solves the column player's min–max optimization: choose a mixed strategy placing the smallest upper bound on the row player's expected payoff. Their optimal heights agree, illustrating the minimax theorem.

There is also a direct Nash equilibrium certificate, so the conclusion does not depend on reading coordinates from a plot. At $p^{\ast }=2/7$, both opposing pure columns give row expected payoff $-1/7$; at $q^{\ast }=4/7$, both pure rows give row expected payoff $-1/7$. By linearity, every unilateral deviation, including an arbitrary mixed strategy, leaves the deviator's expected payoff unchanged against the fixed opposing equilibrium mixture. Neither player can improve it. This is a mixed-strategy optimality certificate for a matrix game.

The equilibrium outcome is a probability distribution over cells, rather than one deterministic cell. Independent randomization givesThe resulting row expected payoff is $(16-18-20+15)/49=-1/7$. Finally, each envelope has a unique optimum, so any Nash equilibrium must use the displayed optimal mixed strategies. In particular there is no pure strategy Nash equilibrium.

Against $q$, choosing row $i$ gives Player I expected payoff $(Aq{)}_i={\sum }_j{a}_{ij}{q}_j$. The best response maximizes this number; randomizing among rows cannot exceed the largest row payoff. Player II therefore minimizes that maximum, exactly the printed optimization problem.

The minimax theorem for a finite zero-sum game statesThis common number is the value of a zero-sum game: Player I can guarantee an expected payoff of at least $v$, and Player II can hold it to at most $v$. At optimal mixed strategies their expected transfer is $v$.

With choices ordered rock, scissors, paper and winner payoff $1$, the row-player payoff matrix is $\left(\begin{array}{ccc}0& 1& -1\\ -1& 0& 1\\ 1& -1& 0\end{array}\right)$. Both the row and column sums vanish. Thus the uniform mixed strategy guarantees expected payoff zero against every opposing strategy; the value of a zero-sum game is zero. A player responding to a known nonuniform mixture can instead optimize its linear expected payoff over pure responses and their ties.

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.