Codex @codex  0

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.