Past exam of the Probability, statistics and options II course of the University of Oxford / 2008 / T (Linear Programming)

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.

Strictly positive entries imply $v>0$. If $q$ is an optimal strategy, set $x=q/v$. Then $Ax\le 1$ and $1^{\mathsf{T}}x=1/v$. Conversely, a nonzero feasible $x$ with $s=1^{\mathsf{T}}x$ gives a strategy $q=x/s$ satisfying ${\max }_i(Aq{)}_i\le 1/s$. Thus $v\le 1/s$, or $s\le 1/v$. The optimal objective is therefore $s_{\ast }=1/v$, andA nonzero feasible point exists by taking a sufficiently small positive multiple of a probability vector, and positivity of $A$ bounds the feasible objective, so the optimum is attained.

For general entries choose a constant $c$ so that $A^{\prime }=A+c11^{\mathsf{T}}$ is strictly positive. Every pair of strategies has its payoff increased by exactly $c$, so optimal strategies are unchanged. Solve the positive problem for $A^{\prime }$, recover $v^{\prime }=1/s_{\ast }^{\prime }$, and then $\boxed{v=v^{\prime }-c}$ for the original game.

The dual isFor positive payoffs and an optimal solution $y_{\ast }$, strong duality gives $1^{\mathsf{T}}{y}_{\ast }=1/v$. Normalizing gives Player I's optimal row strategy $p_{\ast }=y_{\ast }/(1^{\mathsf{T}}{y}_{\ast })$. Its expected payoff against every column is at least $v$. Thus the primal represents Player II's minimization of worst loss and the dual represents Player I's maximization of guaranteed gain.

The proposed vectors are nonnegative, and direct multiplication givesThus $Ax\le 1$ and $A^{\mathsf{T}}y\ge 1$, proving primal and dual feasibility.

Both objectives equal $1/4$: $1^{\mathsf{T}}x=1/12+1/6=1/4$ and $1^{\mathsf{T}}y=1/6+1/12=1/4$. Weak duality bounds the value of every primal feasible point above by every dual feasible objective. Equality for this feasible pair therefore proves both are optimal, without needing to solve either problem further.

Normalize each optimal vector by its sum $1/4$. Player I's row strategy and Player II's column strategy are respectivelyAs a direct check $Aq=(4,4{)}^{\mathsf{T}}$ and $p^{\mathsf{T}}A=(4,5,4)$, so Player II guarantees a loss of at most four and Player I guarantees a gain of at least four.