## Converting a Two Player Zero Sum Mixed Strategy Game Into a Linear Programming Problem

We need to convert the zero sum game with payoff matrix into a linear programming problem.
 A\B $B_1$ $B_2$ $B_3$ $A_1$ -1 0 1 $A_2$ 3 2 -1 $A_3$ -3 1 0
Player A will use the maximin - the strategy for which the row minimum is the maximum. For strategies
$A_1, \: A_2, \: A_3$
the minimums are -1, -1, -3 respectively. The maximin is -1. B will use the minimax strategy - the strategy for which the column maximum is the minimum. The column maximums for strategies
$B_1, \: B_2, \: B_3$
are 3, 2, 1 respectively. The maximin for A does not equal the minimax for B so the game has no saddle point. Also, there are no dominant strategies. It is an irreducible game and cannot be solved by graphical methods because it is a 3 x 3 matrix.
Let A play strategies
$A_1, \: A_2, \: A_3$
with probabilities
$p_1, \: p_2, \: p_3$
respectively. If B plays strategy
$B_1$
the value of the game to A is
$-p_1+3p_2-3p_3$
. The value of the game
$V$
must be at most equal to this, so
$-p_1+3p_2-3p_3 \ge V \rightarrow - \frac{p_1}{V} +3 \frac{p_2}{V}-3 \frac{p_3}{V} \ge \frac{1}{V}$
.
This is also the case for B choosing strategies
$B_2, \: B_3$
. Hence
$2p_2+p_3 \ge v \rightarrow 2 \frac{p_1}{V}+\frac{p_1}{V} \ge 1$

$p_1-p_2 \ge v \rightarrow \frac{p_1}{V}- \frac{p_2}{V} \ge 1$

Now let
$x_1=\frac{p_1}{V}, \: x_2=\frac{p_2}{V}, \: x_3=\frac{p_3}{V}$
.
The three above equations become
$-x_1+3x_2-3x_3 \ge 1$

$2x_2+x_3 \ge 1$

$x_1-x_2 \ge 1$

Also,
$p_1+p_2+p_3 = 1 \rightarrow \frac{p_1}{V}+\frac{p_2}{V}+\frac{p_3} = \frac{1}{V} \rightarrow x_1+x_2+x_3 = \frac{1}{V}$

The above problem is now equivalent to the linear programming problem:
Minimise
$\frac{1}{V}=x_1+x_2+x_3$
(since we want to maximise
$V$
)subject to
$-x_1+3x_2-3x_3 \ge 1$

$2x_2+x_3 \ge 1$

$x_1-x_2 \ge 1$

$x_1, \: x_2, \: x_3 \ge 0$

From B's point of view the value of the game is
$-V$
Let B play strategies
$B_1, \: B_2, \: B_3$
with probabilities
$q_1, \: q_2, \: q_3$
respectively. If A plays strategy
$A_1$
the value of the game to B is
$-q_1+q_3$
. The value of the game
$-V$
must be at most equal to this, so
$-q_1+q_3 \ge -V \rightarrow - \frac{q_1}{V} + \frac{q_3}\ge - \frac {1}{V}$
.
This is also the case for A choosing strategies
$A_2, \: A_3$
. Hence
$3q_1+2q_2-q_3 \ge -v \rightarrow 3 \frac{q_1}{V}+2\frac{q_1}{V} -\frac{q_3}{V}\ge 1$

$p_1-p_2 \ge v \rightarrow \frac{p_1}{V}- \frac{p_2}{V} \ge 1$

Now let
$y_1=\frac{q_1}{V}, \: y_2=\frac{q_2}{V}, \: q_3=\frac{q_3}{V}$
.
The three above equations become
$-y_1+y_3 \ge -1$

$-x_1+3x_2-3x_3 \ge -1$

$-3y_1+y_2 \ge -1$

Also,
$q_1+q_2+q_3 = 1 \rightarrow \frac{q_1}{V}+\frac{q_2}{V}+\frac{q_3} = \frac{1}{V} \rightarrow y_1+y_2+y_3 = \frac{1}{V}$

The above problem is now equivalent to the linear programming problem:
Minimise
$\frac{1}{V}=y_1+y_2+y_3$
(since we want to minimise
$V$
) subject to
$-y_1+y_3 \ge -1$

$-x_1+3x_2-3x_3 \ge -1$

$-3y_1+y_2 \ge -1$

$y_1, \: y_2, \: y_3 \ge 0$