# Linear Programming: Game Theory

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.

## Example: Linear Programming method of Game Theory

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

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.

On small screens, use horizontal scrollbar to view full calculation

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 = x1, p2/V = x2, p3/V = x3

In order to maximize V, company A can

Minimize 1/V = x1+ x2+ x3
subject to

6x1 + 4x2 + x3 ≥ 1
-x1 - 4x2 + 7x3 ≥ 1
5x1 + 0x2 + 10x3 ≥ 1

and x1, x2, x3 ≥ 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 = y1, q2/V = y2, q3/V = y3

In order to minimize V, company B can

Maximize 1/V = y1+ y2+ y3
subject to

6y1 - y2 + 5y3 ≤ 1
4y1 - 4y2 + 0y3 ≤ 1
y1 + 7y2 + 10y3 ≤ 1

and y1, y2, y3 ≥ 0

Company B's problem is the dual of company A's problem.

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

Maximize y1 + y2 + y3 + 0y4 + 0y5 + 0y6

6y1 - y2 + 5y3 + y4 = 1
4y1 - 4y2 + y5 = 1
y1 + 7y2 + 10y3 + y6 = 1

##### Initial Basic Feasible Solution

y1 = 0, y2 = 0, y3 = 0, z = 0
y4 = 1, y5 = 1, y6 = 1

Table 1

Use Horizontal Scrollbar to View Full Calculation

cj 1 1 1 0 0 0
cB Basic Variables
B
y1 y2 y3 y4 y5 y6 Solution values
b (=XB)
0 y4 6 -1 5 1 0 0 1
0 y5 4 -4 0 0 1 0 1
0 y6 1 7 10 0 0 1 1
zj-cj   -1 -1 -1 0 0 0

Key column = y1 column
Minimum positive value = 1/6
Key row = y4 row
Pivot element = 6
y4 departs and y1 enters.

Table 2

cj 1 1 1 0 0 0
cB Basic Variable
B
y1 y2 y3 y4 y5 y6 Solution values
b (=XB)
1 y1 1 -1/6 5/6 1/6 0 0 1/6
0 y5 0 -10/3 -10/3 -2/3 1 0 1/3
0 y6 0 43/6 55/6 -1/6 0 1 5/6
zj-cj   0 -7/6 -1/6 1/6 0 0

### Final Table: Linear Programming Method

cj 1 1 1 0 0 0
cB Basic Variable
B
y1 y2 y3 y4 y5 y6 Solution values
b (=XB)
1 y1 1 0 45/43 7/43 0 1/43 8/43
0 y5 0 0 40/43 -32/43 1 20/43 31/43
1 y2 0 1 55/43 -1/43 0 6/43 5/43
zj-cj   0 0 57/43 6/43 0 7/43

The values for y1, y2 & y3 are 8/43, 5/43 & 0 respectively.

I/V = y1 + y2 + y3 = 8/43 + 5/43 + 0 = 13/43
or V = 43/13

Company B's optimal strategy
q1 = V X y1 = 43/13 X 8/43 = 8/13
q2 = V X y2 = 43/13 X 5/43 = 5/13
q3 = V X y3 = 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 x1, x2 & x3 can be obtained from the final simplex table.

x1 = 6/43, x2 = 0 & x3 = 7/43
p1 = V X x1 = 43/13 X 6/43 = 6/13
p2 = V X x2 = 43/13 X 0 = 0
p3 = V X x3 = 43/13 X 7/43 = 7/13

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