Home > Operation Research calculators > Game Theory >> LPP method example

9. Linear programming method example ( Enter your problem )
 Method & Example-1Example-2 Other related methods

1. Method & Example-1

Method
 linear programming method Steps (Rule) Step-1: The linear programming technique is used for solving mixed strategy games of dimensions greater than (2xx2) size. Step-2: The example is used to explain the procedure.

Example-1
1. Find Solution of game theory problem using linear programming method
 Player A\Player B B1 B2 B3 A1 3 -4 2 A2 1 -7 -3 A3 -2 4 7

Solution:
Players
 Player B B_1 B_2 B_3 Player A A_1 3 -4 2 A_2 1 -7 -3 A_3 -2 4 7

We apply the maximin (minimax) principle to analyze the game.

 Player B B_1 B_2 B_3 RowMinimum Player A A_1 (3) -4 2 -4 A_2 1 -7 -3 -7 A_3 [-2] 4 7 [-2] ColumnMaximum (3) 4 7

Select minimum from the maximum of columns
Column MaxiMin = (3)

Select maximum from the minimum of rows
Row MiniMax = [-2]

Here, Column MaxiMin != Row MiniMax

:. 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:
 Player B B_1 B_2 B_3 Player A A_1 6 -1 5 A_2 4 -4 0 A_3 1 7 10

Let V = value of the game
p_1,p_2,p_3 = probabilities of selecting strategies A_1,A_2,A_3 respectively.

q_1,q_2,q_3 = probabilities of selecting strategies B_1,B_2,B_3 respectively.

 Player B B_1 B_2 B_3 Probability Player A A_1 6 -1 5 p_1 A_2 4 -4 0 p_2 A_3 1 7 10 p_3 Probability q_1 q_2 q_3

player 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.
The expected gain for player A will be as follows
6p_1+4p_2+p_3>=V

-p_1-4p_2+7p_3>=V

5p_1+0p_2+10p_3>=V

Dividing the above constraints by V, we get
6(p_1/V)+4(p_2/V)+(p_3/V)>=1

-(p_1/V)-4(p_2/V)+7(p_3/V)>=1

5(p_1/V)+0(p_2/V)+10(p_3/V)>=1

To simplify the problem, we put
p_1/V=x_1,p_2/V=x_2,p_3/V=x_3

In order to maximize V, player A can
Minimize Z_p=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

player B's objective is to minimize its expected losses, which can be reduced by minimizing V, i.e., player A adopts a poor strategy.
The expected loss for player B will be as follows
6q_1-q_2+5q_3<=V

4q_1-4q_2+0q_3<=V

q_1+7q_2+10q_3<=V

Dividing the above constraints by V, we get
6(q_1/V)-(q_2/V)+5(q_3/V)<=1

4(q_1/V)-4(q_2/V)+0(q_3/V)<=1

(q_1/V)+7(q_2/V)+10(q_3/V)<=1

To simplify the problem, we put
q_1/V=y_1,q_2/V=y_2,q_3/V=y_3

In order to minimize V, player B can
Maximize Z_q=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

Now, solve this problem using simplex method.

Problem is
 Max Z_q =   y_1  +   y_2  +   y_3
subject to
  6 y_1  -   y_2  +  5 y_3 ≤ 1  4 y_1  -  4 y_2 ≤ 1   y_1  +  7 y_2  +  10 y_3 ≤ 1
and y_1,y_2,y_3 >= 0;

The problem is converted to canonical form by adding slack, surplus and artificial variables as appropiate

1. As the constraint 1 is of type '<=' we should add slack variable S_1

2. As the constraint 2 is of type '<=' we should add slack variable S_2

3. As the constraint 3 is of type '<=' we should add slack variable S_3

After introducing slack variables
 Max Z_q =   y_1  +   y_2  +   y_3  +  0 S_1  +  0 S_2  +  0 S_3
subject to
  6 y_1  -   y_2  +  5 y_3  +   S_1 = 1  4 y_1  -  4 y_2  +   S_2 = 1   y_1  +  7 y_2  +  10 y_3  +   S_3 = 1
and y_1,y_2,y_3,S_1,S_2,S_3 >= 0

 Iteration-1 C_j 1 1 1 0 0 0 B C_B X_B y_1 Entering variable y_2 y_3 S_1 S_2 S_3 MinRatio (X_B)/(y_1) S_1 Leaving variable 0 1 (6)  (pivot element) -1 5 1 0 0 (1)/(6)=1/6-> S_2 0 1 4 -4 0 0 1 0 (1)/(4)=1/4 S_3 0 1 1 7 10 0 0 1 (1)/(1)=1 Z_q=0 0=Z_j=sum C_B X_B Z_j Z_j=sum C_B x_j 0 0=0xx6+0xx4+0xx1Z_j=sum C_B y_1 0 0=0xx(-1)+0xx(-4)+0xx7Z_j=sum C_B y_2 0 0=0xx5+0xx0+0xx10Z_j=sum C_B y_3 0 0=0xx1+0xx0+0xx0Z_j=sum C_B S_1 0 0=0xx0+0xx1+0xx0Z_j=sum C_B S_2 0 0=0xx0+0xx0+0xx1Z_j=sum C_B S_3 C_j-Z_j 1 1=1-0uarr 1 1=1-0 1 1=1-0 0 0=0-0 0 0=0-0 0 0=0-0

Positive maximum C_j-Z_j is 1 and its column index is 1. So, the entering variable is y_1.

Minimum ratio is 1/6 and its row index is 1. So, the leaving basis variable is S_1.

:. The pivot element is 6.

Entering =y_1, Departing =S_1, Key Element =6

R_1(new)= R_1(old)-: 6

R_2(new)= R_2(old)- 4 R_1(new)

R_3(new)= R_3(old)- R_1(new)

 Iteration-2 C_j 1 1 1 0 0 0 B C_B X_B y_1 y_2 Entering variable y_3 S_1 S_2 S_3 MinRatio (X_B)/(y_2) y_1 1 1/6 1/6=1-:6R_1(new)= R_1(old)-: 6 1 1=6-:6R_1(new)= R_1(old)-: 6 -1/6 -1/6=(-1)-:6R_1(new)= R_1(old)-: 6 5/6 5/6=5-:6R_1(new)= R_1(old)-: 6 1/6 1/6=1-:6R_1(new)= R_1(old)-: 6 0 0=0-:6R_1(new)= R_1(old)-: 6 0 0=0-:6R_1(new)= R_1(old)-: 6 --- S_2 0 1/3 1/3=1-4xx1/6R_2(new)= R_2(old)- 4 R_1(new) 0 0=4-4xx1R_2(new)= R_2(old)- 4 R_1(new) -10/3 -10/3=(-4)-4xx(-1/6)R_2(new)= R_2(old)- 4 R_1(new) -10/3 -10/3=0-4xx5/6R_2(new)= R_2(old)- 4 R_1(new) -2/3 -2/3=0-4xx1/6R_2(new)= R_2(old)- 4 R_1(new) 1 1=1-4xx0R_2(new)= R_2(old)- 4 R_1(new) 0 0=0-4xx0R_2(new)= R_2(old)- 4 R_1(new) --- S_3 Leaving variable 0 5/6 5/6=1-1/6R_3(new)= R_3(old)- R_1(new) 0 0=1-1R_3(new)= R_3(old)- R_1(new) (43/6) 43/6=7-(-1/6) (pivot element)R_3(new)= R_3(old)- R_1(new) 55/6 55/6=10-5/6R_3(new)= R_3(old)- R_1(new) -1/6 -1/6=0-1/6R_3(new)= R_3(old)- R_1(new) 0 0=0-0R_3(new)= R_3(old)- R_1(new) 1 1=1-0R_3(new)= R_3(old)- R_1(new) (5/6)/(43/6)=5/43-> Z_q=1/6 1/6=1xx1/6Z_j=sum C_B X_B Z_j Z_j=sum C_B x_j 1 1=1xx1+0xx0+0xx0Z_j=sum C_B y_1 -1/6 -1/6=1xx(-1/6)+0xx(-10/3)+0xx43/6Z_j=sum C_B y_2 5/6 5/6=1xx5/6+0xx(-10/3)+0xx55/6Z_j=sum C_B y_3 1/6 1/6=1xx1/6+0xx(-2/3)+0xx(-1/6)Z_j=sum C_B S_1 0 0=1xx0+0xx1+0xx0Z_j=sum C_B S_2 0 0=1xx0+0xx0+0xx1Z_j=sum C_B S_3 C_j-Z_j 0 0=1-1 7/6 7/6=1-(-1/6)uarr 1/6 1/6=1-5/6 -1/6 -1/6=0-1/6 0 0=0-0 0 0=0-0

Positive maximum C_j-Z_j is 7/6 and its column index is 2. So, the entering variable is y_2.

Minimum ratio is 5/43 and its row index is 3. So, the leaving basis variable is S_3.

:. The pivot element is 43/6.

Entering =y_2, Departing =S_3, Key Element =43/6

R_3(new)= R_3(old)xx6/43

R_1(new)= R_1(old)+ 1/6 R_3(new)

R_2(new)= R_2(old)+ 10/3 R_3(new)

 Iteration-3 C_j 1 1 1 0 0 0 B C_B X_B y_1 y_2 y_3 S_1 S_2 S_3 MinRatio y_1 1 8/43 8/43=1/6+1/6xx5/43R_1(new)= R_1(old)+ 1/6 R_3(new) 1 1=1+1/6xx0R_1(new)= R_1(old)+ 1/6 R_3(new) 0 0=(-1/6)+1/6xx1R_1(new)= R_1(old)+ 1/6 R_3(new) 45/43 45/43=5/6+1/6xx55/43R_1(new)= R_1(old)+ 1/6 R_3(new) 7/43 7/43=1/6+1/6xx(-1/43)R_1(new)= R_1(old)+ 1/6 R_3(new) 0 0=0+1/6xx0R_1(new)= R_1(old)+ 1/6 R_3(new) 1/43 1/43=0+1/6xx6/43R_1(new)= R_1(old)+ 1/6 R_3(new) S_2 0 31/43 31/43=1/3+10/3xx5/43R_2(new)= R_2(old)+ 10/3 R_3(new) 0 0=0+10/3xx0R_2(new)= R_2(old)+ 10/3 R_3(new) 0 0=(-10/3)+10/3xx1R_2(new)= R_2(old)+ 10/3 R_3(new) 40/43 40/43=(-10/3)+10/3xx55/43R_2(new)= R_2(old)+ 10/3 R_3(new) -32/43 -32/43=(-2/3)+10/3xx(-1/43)R_2(new)= R_2(old)+ 10/3 R_3(new) 1 1=1+10/3xx0R_2(new)= R_2(old)+ 10/3 R_3(new) 20/43 20/43=0+10/3xx6/43R_2(new)= R_2(old)+ 10/3 R_3(new) y_2 1 5/43 5/43=5/6xx6/43R_3(new)= R_3(old)xx6/43 0 0=0xx6/43R_3(new)= R_3(old)xx6/43 1 1=43/6xx6/43R_3(new)= R_3(old)xx6/43 55/43 55/43=55/6xx6/43R_3(new)= R_3(old)xx6/43 -1/43 -1/43=(-1/6)xx6/43R_3(new)= R_3(old)xx6/43 0 0=0xx6/43R_3(new)= R_3(old)xx6/43 6/43 6/43=1xx6/43R_3(new)= R_3(old)xx6/43 Z_q=13/43 13/43=1xx8/43+1xx5/43Z_j=sum C_B X_B Z_j Z_j=sum C_B x_j 1 1=1xx1+0xx0+1xx0Z_j=sum C_B y_1 1 1=1xx0+0xx0+1xx1Z_j=sum C_B y_2 100/43 100/43=1xx45/43+0xx40/43+1xx55/43Z_j=sum C_B y_3 6/43 6/43=1xx7/43+0xx(-32/43)+1xx(-1/43)Z_j=sum C_B S_1 0 0=1xx0+0xx1+1xx0Z_j=sum C_B S_2 7/43 7/43=1xx1/43+0xx20/43+1xx6/43Z_j=sum C_B S_3 C_j-Z_j 0 0=1-1 0 0=1-1 -57/43 -57/43=1-100/43 -6/43 -6/43=0-6/43 0 0=0-0 -7/43 -7/43=0-7/43

Since all C_j - Z_j <= 0

Hence, optimal solution is arrived with value of variables as :
y_1=8/43,y_2=5/43,y_3=0

Max Z_q = 13/43

:. Z_q=1/V=13/43

:. V=43/13

player B's optimal strategy
q_1=V xx y_1=43/13 xx 8/43=8/13

q_2=V xx y_2=43/13 xx 5/43=5/13

q_3=V xx y_3=43/13 xx 0=0

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

player A's optimal strategy
The values for x_1,x_2,x_3 can be obtained from the z_j-c_j row of final simplex table

x_1=6/43,x_2=0,x_3=7/43

p_1=V xx x_1=43/13 xx 6/43=6/13

p_2=V xx x_2=43/13 xx 0=0

p_3=V xx x_3=43/13 xx 7/43=7/13

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

This material is intended as a summary. Use your textbook for detail explanation.
Any bug, improvement, feedback then Submit Here

Dear user,