Converting games to linear programming problemsAQA A-Level Further Maths: Revision notes

A graphical solution only works when one player has two strategies. For a higher order game (for example $3\times3$), Rowan's optimal mixed strategy is found by turning the game into a linear programming problem and solving it with the simplex algorithm.

The idea: Rowan chooses probabilities $p_1,p_2,p_3,\ldots$ for his rows. Against each of Colin's columns his expected pay-off is a linear expression in the $p_i$. Colin will choose the column that is worst for Rowan, so Rowan wants to maximise the smallest of these expected pay-offs. Calling that smallest value $V$, this becomes a linear programme.

The simplex algorithm requires $V\geq0$, so first make the value of the game non-negative by adding a constant $k$ to every entry. The usual choice is the least integer that makes every entry non-negative (the negative of the smallest entry).

• Adding $k$ to every entry raises every expected pay-off by $k$ (because the probabilities sum to 1), so Rowan's optimal strategy does not change.
• The value of the game increases by $k$. After solving, subtract $k$ to get the value of the original game.

Example: if the smallest entry is $-3$, add $3$. If the adjusted game has value $2$, the original game has value $2-3=-1$, which means Colin wins $1$ per play on average.

For the adjusted matrix with entries $a_{ij}$ (row $i$, column $j$), Rowan plays row $i$ with probability $p_i$.

• Against column $j$ his expected pay-off is $\sum_i a_{ij}p_i$, and $V\leq$ this, so each column gives a constraint $V-a_{1j}p_1-a_{2j}p_2-\ldots\leq0$.
• The probabilities cannot total more than 1: $p_1+p_2+p_3\leq1$.
• All variables are non-negative: $p_i\geq0$ and $V\geq0$.
• Maximise $P=V$.

Example: adjusted matrix $\begin{pmatrix} 3 & 1 \\ 0 & 5 \end{pmatrix}$ gives: maximise $P=V$ subject to $V-3p_1\leq0$, $V-p_1-5p_2\leq0$, $p_1+p_2\leq1$. (Solving gives $p_1=\frac57$, $p_2=\frac27$, $V=\frac{15}{7}$.)

Some questions use $x_i=\frac{p_i}{V}$ instead: minimise $x_1+x_2+\ldots$ subject to $\sum_ia_{ij}x_i\geq1$ for every column, and then $V=\frac{1}{\sum x_i}$. Use the form the question asks for.

Introduce a slack variable for each constraint, set up the initial simplex tableau, and pivot until there are no negative entries in the objective row. The final tableau gives $V$ and each $p_i$.

• The value of the original game is $V-k$.
• Rowan's optimal strategy is the set of probabilities $p_i$ (a probability of $0$ means that row is never played).
• To find the number of times to play a row in $n$ plays, calculate $n\times p_i$.
• Colin's optimal strategy can be read from the objective row of the final tableau, under the slack variables of the column constraints. A column whose constraint is not tight (its expected pay-off is greater than $V$) is never played by Colin.

Check the answer: with Rowan's strategy, the expected pay-off against every column should be at least $V$, and equal to $V$ for the columns Colin does play.