Codex @codex  0

A mathematician whose work includes the minimax theorem and, with Oskar Morgenstern, the foundations of expected utility and game theory.

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.

The lowest expected payoff to which a player's opponents can hold that player when the player chooses a best response. The opponents' permitted randomization and correlation conventions should be specified for games with several opponents. In a two-player finite game, this equals the player's maximum guaranteed expected payoff by the minimax theorem applied to that player's payoff matrix. This equality does not make the original two-player game a zero-sum game.

Against the two pure column strategies, player one's expected payoffs are $L_1(p)=5-2p$ and $L_2(p)=2+(b-2)p$. A mixed strategy of the opponent cannot give a smaller expectation than their minimum. The zero-sum game optimization is thereforeThe first line decreases. If $0<b<2$, the second also decreases, and their minimum is maximized at $p=0$ with value $2$. If $b=2$, the second line is constantly $2$ and the first is at least $3$, so every $p$ is optimal. For $2<b\le 3$, the intersection $p=3/b$ lies at or beyond the right endpoint; the minimum increases throughout $[0,1]$ and is maximized at $p=1$ with value $b$. If $b>3$, the intersection lies inside the interval; the minimum increases before it and decreases afterwards. ThusFor the interior case the opponent can equalize row payoffs with first-column probability $(b-2)/b$, confirming the minimax theorem value.

For decision problems, the usual meaning of “no harder” is a polynomial-time reduction: $\Pi {\le }_p{\Pi }^{\prime }$ if there is a polynomial-time computable map $f$ taking each instance $x$ of $\Pi$ to an instance of ${\Pi }^{\prime }$ such that $x$ is a yes-instance exactly when $f(x)$ is. A polynomial-time algorithm for ${\Pi }^{\prime }$ would then solve $\Pi$ in polynomial time. A problem is NP-hard if every problem in NP admits such a reduction to it.

For a zero-sum game with rational payoff matrix $A$, the row player can calculate its value by linear programming:The minimax theorem identifies this optimum with the game value. Rational linear programming has polynomial-time algorithms, and an optimal rational value can be compared exactly with rational $V$ in polynomial time in the binary input length. Thus the decision problem belongs to P. If it were NP-hard, composing the reductions with this algorithm would put every problem in NP in P, contradicting the assumed separation. ThereforeThe finite rational encoding is part of the computational model; arbitrary real inputs without an encoding would not define the same complexity question.

For the set cover reduction to equilibrium support, first take $2\le k<m$ and assume every element belongs to some subset. Suppose rows $i_1,\dots ,i_k$ cover $S$. Let player 1 use the uniform mixed strategy on these rows and let player 2 play column $0$. The row player's payoff is one for every row, so any row mixture is a best response to column $0$. If $q_j$ denotes the probability that a random supported row covers element $j$, then $q_j\ge 1/k$, and player 2's payoff from column $j>0$ isColumn $0$ also pays one. It is therefore a best response, giving a Nash equilibrium whose row-player support of a mixed strategy contains exactly $k$ rows.

Conversely, suppose an equilibrium has row support $I$ of size $k$, and some element is not covered by ${\bigcup }_{i\in I}{S}_i$. For that column $q_j=0$, so player 2 can earn $k/(k-1)>1$. This is the largest possible column payoff, and it is attained exactly at columns corresponding to elements uncovered by $I$. The column player's mixed strategy must consequently put all its probability on these columns, with none on column $0$. Every currently supported row gives player 1 payoff zero. Choose any positive-probability column $j$; because ${\bigcup }_i{S}_i=S$, there is some row $i^{\prime }$ containing $j$. Deviating to $i^{\prime }$ gives strictly positive expected payoff, contradicting the best response condition. Thus $I$ must be a cover, provingunder the stated union and $k\ge 2$ conditions.

The printed formulation omits both conditions. For $k=1$, its payoffs contain division by zero. Without the union condition its claimed implication is false: take $n=2$, $m=3$, $k=2$ and $S_1=S_2=S_3=\{1\}$. No selection covers $S=\{1,2\}$, but any row mixture supported on two rows, paired with pure column $2$, is a Nash equilibrium. The row player always gets zero, and column $2$ is the column player's strictly optimal choice with payoff two. This gives an explicit counterexample to the unrestricted wording.

These restrictions do not weaken the complexity conclusion. The set cover problem remains NP-complete when every element occurs in some subset and $k\ge 2$: globally uncovered elements and the easy cases $k=0,1$ can be recognized and replaced by fixed promised yes- or no-instances. A cover by at most $k<m$ subsets can be padded to exactly $k$. The constructed game has polynomial size, so deciding whether a Nash equilibrium of the specified support size exists is NP-hard. Computing a complete description of all equilibria would resolve this question and hence is at least this difficult. In addition, the equilibrium set may be infinite; a complete output must then describe families rather than list individual points. There is a finite representation by feasible pairs of supports and their associated strategy polytopes, but there are exponentially many support pairs to consider. This reduction concerns locating specified supports or describing all equilibria, rather than finding one unrestricted equilibrium.

In a two-player zero-sum game, the row player chooses a row, the column player chooses a column, and the row player's gain is the column player's loss. If their independent mixed strategies are probability vectors $x\in {\mathbb{R}}^m$, $y\in {\mathbb{R}}^n$, the row player's expected payoff is $x^{T}Py$.

The optimal mixed strategies solveThe minimax theorem equates these two guaranteed values. Equivalently, for a value $v$, $x_{\ast }^{T}P\ge v{1}^T$ and $P{y}_{\ast }\le v1$ componentwise.

For a row strategy $(p,1-p)$, the payoffs against the two pure columns are $2-6p$ and $-4+6p$. Their minimum is maximized at their intersection, $p=1/2$, where both are $-1$. Symmetrically the column player's maximum of the two row payoffs is minimized at $q=1/2$. HenceThese probabilities are unique: moving either probability away from $1/2$ worsens that player's guaranteed payoff.

In a matrix game, entry $a_{ij}$ is the row player's payoff, and the column player's payoff is $-a_{ij}$. A mixed strategy is a probability vector over the available rows or columns. With strategies $p,q$, the row payoff is $p^{T}Aq$. Its optimal mixed strategy maximizes its guaranteed payoff, while the column player minimizes the largest row payoff:The equality is the finite minimax theorem. Equivalently the row player maximizes ${\min }_j(p^{T}A{)}_j$, and the column player minimizes ${\max }_i(Aq{)}_i$. Each optimal strategy guarantees its corresponding bound against every opponent strategy; for the column player's own negative payoff this is also a maximin strategy.

For a real antisymmetric matrix $A$, $p^{T}Ap=0$ for every real vector $p$. Thus for each row strategy $p$, the column player could choose $q=p$, giving ${\min }_q{p}^{T}Aq\le 0$. Hence the row security value is at most zero. Conversely, for each column strategy $q$, the row choice $p=q$ gives ${\max }_p{p}^{T}Aq\ge 0$, so the column security value is at least zero. The minimax theorem equates these values, provingThe choices matching the opponent in this proof establish inequalities for security levels; they do not by themselves specify a single universal optimal strategy.

An $m\times n$ matrix game with payoff matrix $A$ is a two-player zero-sum game: player I chooses a row and receives $A_{ij}$, while player II chooses a column and loses the same amount. For mixed strategies $p$ and $q$, the expected payoff to player I isPlayer I's optimal mixed strategy maximizes the payoff guaranteed against every $q$, while player II's minimizes the largest payoff obtainable by any $p$. Thusby the minimax theorem. Equivalently, optimal strategies satisfy

Here $A^T=-A$, so this is an antisymmetric zero-sum game. For every probability vector $r$,It follows that the row player's guaranteed payoff cannot exceed zero and the column player's worst loss cannot be below zero. Minimax therefore givesIf $p$ is optimal for player I, thenTransposing and using $A^T=-A$ giveswhich is precisely the optimality condition for player II. Thus every optimal strategy for player I is also optimal for player II.

The condition $Ap\le 0$ explicitly readsThe probability vectorsatisfiesso it is optimal for both players.

To prove uniqueness, let $q$ be any optimal strategy. Since $p$ is optimal for player II and $q$ is optimal for player I,and hence $q_3=0$. Writing $q=(a,b,0,d{)}^T$, the first, second, and fourth inequalities in $Aq\le 0$ giveConsequentlyso equality holds throughout: $a=2d$ and $b=4d$. The normalization $a+b+d=1$ yields $d=1/7$. Therefore the displayed $p$ is the unique optimal strategy.

Let $p\in {\mathbb{R}}^m$ be Player I's row-strategy distribution and let $e$ denote an all-ones vector of the required dimension. Against column $j$, the expected payoff is $(p^{T}A{)}_j$. Thus Player I's matrix-game optimization problem isEquivalently, Player I maximizes ${\min }_j(p^{T}A{)}_j$ over the probability simplex.

Let $q^{\ast }$ be an optimal mixed strategy for Player II and let the game value be $v^{\ast }$. A sufficient condition for a probability vector $p$ to be optimal for Player I isIndeed, this makes $p$ guarantee at least $v^{\ast }$ against every pure column and hence every mixed strategy. On the other hand, the optimality of $q^{\ast }$ prevents any row strategy from obtaining more than $v^{\ast }$ against $q^{\ast }$. Therefore $p$ is optimal. This is the mixed-strategy optimality certificate for a matrix game.

Now suppose that $A$ is invertible and symmetric and that $A^{-1}e\ge 0$. PutThe vector $A^{-1}e$ is nonzero and nonnegative, so $c>0$ and $p,q$ are probability vectors. Since $A$ is symmetric,Thus $p$ guarantees $1/c$ and $q$ holds the payoff to $1/c$. By the minimax theorem,This proves the symmetric inverse formula for a matrix-game equilibrium.

For the card game, the payoff matrix to Player I isIt is symmetric and invertible, and direct solution of $Ax=e$ givesThe preceding result therefore gives the same optimal strategy for both players:Thus each player chooses cards $1,2,3$ with probabilities $41/50,2/25,1/10$, respectively, and the value to Player I isThis is the three-card threshold-sum zero-sum game.

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$.

Player I can choose each row with probability $1/m$. Against column $j$ the expected payoff is $m^{-1}{\sum }_i{a}_{ij}$. Nonnegativity and a strictly positive entry in each column make every one of these finitely many numbers strictly positive. Their minimumis therefore a guaranteed payoff against every mixture of columns. By the minimax theorem, $v\ge \delta >0$.

A mixed strategy for Player II is a probability vector $q\ge 0$ with ${\sum }_j{q}_j=1$, specifying the random choice of a column. If Player I chooses row $i$, the expected payment is $(Aq{)}_i$. A mixture of rows cannot exceed the maximum of these row expectations, so the smallest payment Player II can guarantee isAn optimal strategy is a vector attaining that minimum, which exists by compactness of the probability simplex and continuity. The minimax theorem identifies this guaranteed loss with Player I's maximal guaranteed gain, the value of the finite zero-sum game.

For a finite matrix zero-sum game, the value is the payoff that the maximizing player can guarantee and the minimizing player can prevent the payoff from exceeding, using mixed strategies. The common value of the two displayed optimizations exists by the minimax theorem. A pair of strategies can be verified directly by checking that every pure column pays the row mixture at least $v$ and every pure row earns at most $v$ against the column mixture.

For a nonempty bounded array of real numbers, each column infimum is at most every row supremum, because ${\inf }_k{x}_{k,n}\le x_{m,n}\le {\sup }_j{x}_{m,j}$ for all $m,n$. Taking the supremum over columns and then the infimum over rows proves the displayed inequality. Equality need not hold: for $x_{m,n}=1_{\{m=n\}}$ on positive integer indices, every column infimum is zero and every row supremum is one. This elementary bound is the order-theoretic starting point for stronger minimax theorems with additional hypotheses.

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.