Given a zero sum game with two players, each with a choice of strategies, and a payoff matrix representing the winnings or losses of one player for every possible combination of strategies, we can find the optimal strategy that player should produce to maximise their winnings (or minimise therir losses) by expressing the game as a linear programming problem and solving it graphically or using the simplex algorithm.
Example: Given the two player game with payoff matrix (for player A) given below, with strategies highlighted:
|
B |
||||
|
A |
Strategy |
1 |
2 |
3 |
|
1 |
-3 |
3 |
1 |
|
|
2 |
1 |
-4 |
-1 |
|
|
3 |
-5 |
2 |
4 | |
First test the game for stability by finding the row maximin and the column minimax. If these are not the same, the game is not stable.
|
B |
Row Minimum |
||||
|
A |
Strategy |
1 |
2 |
3 |
|
|
1 |
-3 |
3 |
1 |
-3 |
|
|
2 |
1 |
-4 |
-1 |
-4 |
|
|
3 |
-5 |
2 |
4 |
-5 |
|
|
Column Maximum |
1 |
3 |
4 |
||
The row maximin, the maximum value of the row minima, is -3. The column minimax, the minimum value of the column maxima, is 1. Since these are not the same the game is not stable.
To use the simplex algorithm to solve the game we need to make all the entries positive. We can do this by adding 6 to each element in the payoff matrix to give the matrix below.
|
B |
||||
|
A |
Strategy |
1 |
2 |
3 |
|
1 |
3 |
9 |
7 |
|
|
2 |
7 |
2 |
5 |
|
|
3 |
1 |
8 |
10 |
|
Let
and
be the probabilities of player A choosing strategies 1 , 2 and 3 respectively. Obviously,
Let
be the value of the game to player A after 6 has been added to each element of the matrix. Obviously we seek to maximise
The constraints are given below.
If player B chooses strategy 1,
where
is a slack variable.
If player B chooses strategy 2,
where
is a slack variable.
If player B chooses strategy 3,
where t is a slack variable.
