Past exam of the mathematics course of the University of Cambridge / 2023 / ib / Paper 4 / 18H / Solution

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.