Past exam of the mathematics course of the University of Cambridge / 2022 / ib / Paper 4 / 18H (Optimisation)

A two-player zero-sum game has a payoff gained by one player and lost by the other. A pure strategy chooses one action deterministically; a mixed strategy is a probability distribution over pure actions.

A pure optimum is a saddle point: an entry minimal in its row and maximal in its column. In $A_1$, $c$ at $(2,1)$ is a saddle; in $A_2$, $c$ at $(2,2)$ is a saddle. Matrix $A_3$ has row maximin $b$ and column minimax $c$, so no saddle exists. Thus

Every payoff is positive, so every pair of mixed strategies has positive expected payoff and the game value satisfies $v>0$. Player 1 maximizes $v$ subject to $A^{T}p\ge ve$, $e^{T}p=1$, $p\ge 0$. Setting $x=p/v$ turns these intoMaximizing $v$ is therefore equivalent to the stated minimization of $e^{T}x$.

The dual iswhich is in standard maximization form after adding nonnegative slack variables. The simplex pivots first introduce the variable with coefficient seven and then the remaining payoff column; the optimum occurs where both constraints bind:Thus $y=(1/16,3/16)$ and the dual value is $1/4$. Complementary slackness gives $x=(1/8,1/8)$. Hence $v=4$ and the normalized optimal strategies are