Converting a Two Player Zero Sum Mixed Strategy Game 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 |
\[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\]
