Past exam of the probability, statistics and options I course of the University of Oxford / 2010 / T (Linear Programming)

A mixed strategy for Player II is a probability vector $q=(q_1,\dots ,q_n)$, with $q_j\ge 0$ and ${\sum }_j{q}_j=1$. The player chooses pure strategy $j$ with probability $q_j$, independently of the opponent's randomization.

Against $q$, choosing row $i$ gives Player I expected payoff $(Aq{)}_i={\sum }_j{a}_{ij}{q}_j$. The best response maximizes this number; randomizing among rows cannot exceed the largest row payoff. Player II therefore minimizes that maximum, exactly the printed optimization problem.

The minimax theorem for a finite zero-sum game statesThis common number is the value of a zero-sum game: Player I can guarantee an expected payoff of at least $v$, and Player II can hold it to at most $v$. At optimal mixed strategies their expected transfer is $v$.

Player I can choose each row with probability $1/m$. Against column $j$ the expected payoff is $m^{-1}{\sum }_i{a}_{ij}$. Nonnegativity and a strictly positive entry in each column make every one of these finitely many numbers strictly positive. Their minimumis therefore a guaranteed payoff against every mixture of columns. By the minimax theorem, $v\ge \delta >0$.

For the minimizing player, column one weakly dominates column three, since its payoff is no greater in every row. We may therefore choose an optimum with $q_3=0$. Write $q=(x,1-x,0)$, $0\le x\le 1$. The three row payoffs are $6-5x$, $5-3x$, and $1+2x$.

The maximum of the decreasing line $5-3x$ and the increasing line $1+2x$ is minimized where they meet: $x=4/5$, with value $13/5$. At this point the first line is only $2$, so it does not increase the maximum. Hence the candidate isA dual certificate establishes optimality against every possible three-column mixture. Player I's strategy $p_{\ast }=(0,2/5,3/5)$ gives column payoffs $(13/5,13/5,16/5)$, guaranteeing at least $13/5$. The displayed $q_{\ast }$ holds every row payoff to at most $13/5$. These matching guarantees prove the claimed value and optimality.