The linear programming technique is used for solving mixed strategy games of dimensions greater than (2 X 2) size. The following simple example is used to explain the procedure.

Two companies are competing for the same product. To improve its market share, company A decides to launch the following strategies.

- A1 = give discount coupons
- A2 = home delivery services
- A3 = free gifts

The company B decides to use media advertising to promote its product.

- B1 = internet
- B2 = newspaper
- B3 = magazine

Company B | ||||
---|---|---|---|---|

Company A | B1 | B2 | B3 | |

A1 | 3 | -4 | 2 | |

A2 | 1 | -7 | -3 | |

A3 | -2 | 4 | 7 |

Use linear programming to determine the best strategies for both the companies.

Solution.

Company B | Minimum | ||||
---|---|---|---|---|---|

Company A | B1 | B2 | B3 | ||

A1 | 3 | -4 | 2 | -4 | |

A2 | 1 | -7 | -3 | -7 | |

A3 | -2 | 4 | 7 | -2 | |

Maximum | 3 | 4 | 7 |

Minimax = -2

Maximin = 3

This game has no **saddle point**. So the value of the game lies
between –2 and +3. It is possible that the value of game may be
negative or zero. Thus, a constant k is added to all the elements of
pay-off matrix. Let k = 3, then the given pay-off matrix becomes:

Company B | ||||
---|---|---|---|---|

Company A | B1 | B2 | B3 | |

A1 | 6 | -1 | 5 | |

A2 | 4 | -4 | 0 | |

A3 | 1 | 7 | 10 |

Let

V = value of the game

p1, p2 & p3 = probabilities of selecting strategies A1, A2 & A3 respectively.

q1, q2 & q3 = probabilities of selecting strategies B1, B2 & B3 respectively.

Company B | Probability | ||||
---|---|---|---|---|---|

Company A | B1 | B2 | B3 | ||

A1 | 6 | -1 | 5 | p1 | |

A2 | 4 | -4 | 0 | p2 | |

A3 | 1 | 7 | 10 | p3 | |

Probability | q1 | q2 | q3 |

Company A's objective is to maximize the expected gains, which can be achieved by maximizing V, i.e., it might gain more than V if company B adopts a poor strategy. Hence, the expected gain for company A will be as follows:

6p1 + 4p2 + p3 ≥ V

-p1 - 4p2 + 7p3 ≥ V

5p1 + 0p2 + 10p3 ≥ V

p1 + p2 + p3 = 1

and p1, p2, p3 ≥ 0

Dividing the above constraints by V, we get

6p1/V + 4p2/V + p3/V ≥ 1

-p1/V - 4p2/V + 7p3/V ≥ 1

5p1/V + 0p2/V + 10p3/V ≥ 1

p1/V + p2/V + p3/V = 1/V

To simplify the problem, we put

p1/V = x_{1}, p2/V = x_{2}, p3/V = x_{3}

In order to maximize V, company A can

Minimize 1/V = x_{1}+ x_{2}+ x_{3}

subject to

6x_{1} + 4x_{2} + x_{3} ≥ 1

-x_{1} - 4x_{2} + 7x_{3} ≥ 1

5x_{1} + 0x_{2} + 10x_{3} ≥ 1

and x_{1}, x_{2}, x_{3} ≥
0

Company B's objective is to minimize its expected losses, which can
be reduced by minimizing V, i.e., company A adopts a poor strategy.
Hence, the expected loss for company B will be as follows:

6q1_{} - q2 + 5q3 ≤ V

4q1 - 4q2 + 0q3 ≤ V

q1 + 7q2 + 10q3 ≤ V

q1 + q2 + q3 = 1

and q1, q2, q3 ≥ 0

Dividing the above constraints by V, we get

6q1/V_{} - q2/V + 5q3/V ≤ 1

4q1/V - 4q2/V + 0q3/V ≤ 1

q1/V + 7q2/V + 10q3/V ≤ 1

q1/V + q2/V + q3/V = 1/V

To simplify the problem, we put

q1/V = y_{1}, q2/V = y_{2}, q3/V = y_{3}

In order to minimize V, company B can

Maximize 1/V = y_{1}+ y_{2}+ y_{3}

subject to

6y_{1} - y_{2} + 5y_{3} ≤
1

4y_{1} - 4y_{2} + 0y_{3} ≤
1

y_{1} + 7y_{2} + 10y_{3} ≤
1

and y_{1}, y_{2}, y_{3} ≥
0

To solve this problem, we introduce slack variables to convert inequalities to equalities. The problem becomes

Maximize y_{1} + y_{2} + y_{3} + 0y_{4} + 0y_{5} + 0y_{6}

6y_{1} - y_{2} + 5y_{3} + y_{4} = 1

4y_{1} - 4y_{2} + y_{5} = 1

y_{1} + 7y_{2} + 10y_{3} + y_{6} = 1

y_{1} = 0, y_{2} = 0, y_{3} = 0, z = 0

y_{4} = 1, y_{5} = 1, y_{6} = 1

Table 1

c_{j} |
1 | 1 | 1 | 0 | 0 | 0 | ||
---|---|---|---|---|---|---|---|---|

c_{B} |
Basic Variables B |
y_{1} |
y_{2} |
y_{3} |
y_{4} |
y_{5} |
y_{6} |
Solution values b (=X _{B}) |

0 | y_{4} |
6 | -1 | 5 | 1 | 0 | 0 | 1 |

0 | y_{5} |
4 | -4 | 0 | 0 | 1 | 0 | 1 |

0 | y_{6} |
1 | 7 | 10 | 0 | 0 | 1 | 1 |

z_{j}-c_{j} |
-1 | -1 | -1 | 0 | 0 | 0 |

Key column = y_{1 }column

Minimum positive value = 1/6

Key row = y_{4} row

Pivot element = 6

y_{4} departs and y_{1} enters.

Table 2

c_{j} |
1 | 1 | 1 | 0 | 0 | 0 | ||
---|---|---|---|---|---|---|---|---|

c_{B} |
Basic Variable B |
y_{1} |
y_{2} |
y_{3} |
y_{4} |
y_{5} |
y_{6} |
Solution values b (=X _{B}) |

1 | y_{1} |
1 | -1/6 | 5/6 | 1/6 | 0 | 0 | 1/6 |

0 | y_{5} |
0 | -10/3 | -10/3 | -2/3 | 1 | 0 | 1/3 |

0 | y_{6} |
0 | 43/6 | 55/6 | -1/6 | 0 | 1 | 5/6 |

z_{j}-c_{j} |
0 | -7/6 | -1/6 | 1/6 | 0 | 0 |

c_{j} |
1 | 1 | 1 | 0 | 0 | 0 | ||
---|---|---|---|---|---|---|---|---|

c_{B} |
Basic Variable B |
y_{1} |
y_{2} |
y_{3} |
y_{4} |
y_{5} |
y_{6} |
Solution values b (=X _{B}) |

1 | y_{1} |
1 | 0 | 45/43 | 7/43 | 0 | 1/43 | 8/43 |

0 | y_{5} |
0 | 0 | 40/43 | -32/43 | 1 | 20/43 | 31/43 |

1 | y_{2} |
0 | 1 | 55/43 | -1/43 | 0 | 6/43 | 5/43 |

z_{j}-c_{j} |
0 | 0 | 57/43 | 6/43 | 0 | 7/43 |

The values for y_{1}, y_{2} & y_{3} are
8/43, 5/43 & 0 respectively.

I/V = y_{1} + y_{2} + y_{3 }= 8/43 + 5/43 +
0 = 13/43

or V = 43/13

Company B's optimal strategy

q1 = V X y_{1} = 43/13 X 8/43 = 8/13

q2 = V X y_{2} = 43/13 X 5/43 = 5/13

q3 = V X y_{3} = 43/13 X 0 = 0

Hence, company B's optimal strategy is (8/13, 5/13, 0).

Company A's optimal strategy

The values for x_{1}, x_{2} & x_{3} can
be obtained from the final simplex table.

x_{1} = 6/43, x_{2} = 0 & x_{3} = 7/43

p1 = V X x_{1} = 43/13 X 6/43 = 6/13

p2 = V X x_{2} = 43/13 X 0 = 0

p3 = V X x_{3} = 43/13 X 7/43 = 7/13

Hence, company A's optimal strategy is (6/13, 0, 7/13).