Past exam of the mathematics course of the University of Cambridge / 2017 / ib / Paper 3 / 21H (Optimisation)

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.

In this consecutive-number antisymmetric game, with the row player's number denoted $i$, the payoff matrix isIt is an antisymmetric matrix, so the matrix game has value zero for every $n\ge 3$. For $n=3$,satisfies $Ap=0$ and $p^{T}A=0$, proving optimality for both players.

For any larger $n$, extend the same strategy by zero probabilities:Indeed, the first three coordinates of $Ap$ are zero. For $i=4$, $(Ap{)}_4=-2/4-2/2+1/4=-5/4$; for $i\ge 5$, all three supported numbers are at least two below $i$, so $(Ap{)}_i=-2$. Hence $Ap\le 0$ and, by antisymmetry, $p^{T}A\ge 0$. The column player using $p$ prevents positive payoff, while the row player using $p$ prevents negative payoff, a mixed-strategy optimality certificate for a matrix game. This explicitly checks all the additional strategies rather than assuming the three-number subgame remains optimal.