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
• A3 = free gifts

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

• B1 = internet
• B2 = newspaper
• B3 = magazine

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

Solution.

On small screens, use horizontal scrollbar to view full calculation

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:

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 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₁, p2/V = x₂, p3/V = x₃

In order to maximize V, company A can

Minimize 1/V = x₁+ x₂+ x₃
subject to

6x₁ + 4x₂ + x₃ ≥ 1
-x₁ - 4x₂ + 7x₃ ≥ 1
5x₁ + 0x₂ + 10x₃ ≥ 1

and x₁, x₂, x₃ ≥ 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₁, q2/V = y₂, q3/V = y₃

In order to minimize V, company B can

Maximize 1/V = y₁+ y₂+ y₃
subject to

6y₁ - y₂ + 5y₃ ≤ 1
4y₁ - 4y₂ + 0y₃ ≤ 1
y₁ + 7y₂ + 10y₃ ≤ 1

and y₁, y₂, y₃ ≥ 0

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

Maximize y₁ + y₂ + y₃ + 0y₄ + 0y₅ + 0y₆

6y₁ - y₂ + 5y₃ + y₄ = 1
4y₁ - 4y₂ + y₅ = 1
y₁ + 7y₂ + 10y₃ + y₆ = 1

Initial Basic Feasible Solution

y₁ = 0, y₂ = 0, y₃ = 0, z = 0
y₄ = 1, y₅ = 1, y₆ = 1

Table 1

Use Horizontal Scrollbar to View Full Calculation

Key column = y₁ column
Minimum positive value = 1/6
Key row = y₄ row
Pivot element = 6
y₄ departs and y₁ enters.

Table 2

Final Table: Linear Programming Method

The values for y₁, y₂ & y₃ are 8/43, 5/43 & 0 respectively.

I/V = y₁ + y₂ + y₃ = 8/43 + 5/43 + 0 = 13/43
or V = 43/13

Company B's optimal strategy
q1 = V X y₁ = 43/13 X 8/43 = 8/13
q2 = V X y₂ = 43/13 X 5/43 = 5/13
q3 = V X y₃ = 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₁, x₂ & x₃ can be obtained from the final simplex table.

x₁ = 6/43, x₂ = 0 & x₃ = 7/43
p1 = V X x₁ = 43/13 X 6/43 = 6/13
p2 = V X x₂ = 43/13 X 0 = 0
p3 = V X x₃ = 43/13 X 7/43 = 7/13

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