Lecture_23_Game Theory_Simplex Method

23.1 Simplex Method


Let us consider the 3 x 3 matrix



As per the assumptions, A always attempts to choose the set of strategies with the non-zero probabilities say p1, p2, p3 where p1 + p2 + p3 = 1 that maximizes his minimum expected gain.

Similarly B would choose the set of strategies with the non-zero probabilities say q1, q2, q3 where q1 + q2 + q3 = 1 that minimizes his maximum expected loss.

Step 1
Find the minimax and maximin value from the given matrix

Step 2
The objective of A is to maximize the value, which is equivalent to minimizing the value 1/V. The LPP is written as
Min 1/V = p1/V + p2/V + p3/V and constraints ? 1

It is written as


Min 1/V = x1 + x2 + x3 and constraints ? 1


Similarly for B, we get the LPP as the dual of the above LPP Max 1/V = Y1 + Y2 + Y3
and constraints ? 1
Where Y1 = q1/V, Y2 = q2/V, Y3 = q3/V


Step 3
Solve the LPP by using simplex table and obtain the best strategy for the players




Example 1
Solve by Simplex method



Solution



We can infer that 2 ? V ? 3. Hence it can be concluded that the value of the game lies between 2
and 3 and the V > 0.

LPP
Max 1/V = Y1 + Y2 + Y3
Subject to
3Y1 – 2Y2 + 4Y3 ? 1
-1Y1 + 4Y2 + 2Y3 ? 1 2Y1 + 2Y2 + 6Y3 ? 1 Y1, Y2, Y3 ? 0

SLPP
Max 1/V = Y1 + Y2 + Y3 + 0s1 + 0s2 + 0s3
Subject to
3Y1 – 2Y2 + 4Y3 + s1 = 1
-1Y1 + 4Y2 + 2Y3 + s2 =1 2Y1 + 2Y2 + 6Y3 + s3 = 1 Y1, Y2, Y3, s1, s2, s3 ? 0











2

Cj? 1 1 1 0 0 0
Basic Variables CB YB Y1 Y2 Y3 S1 S2 S3 Min Ratio YB / YK
S1 S2 S3 0 1
0 1
0 1 3 -2 4 1 0 0 1/3?
-
1/2
-1 4 2 0 1 0
2 2 6 0 0 1

1/V = 0 ?
-1 -1 -1 0 0 0
Y1 S2 S3 1 1/3
0 4/3
0 1/3 1 -2/3 4/3 1/3 0 0
0 10/3 10/3 1/3 1 0 -
2/5
1/10?
0 10/3 10/3 -2/3 0 1

1/V =1/3 ?
0 -5/3 1/3 1/3 0 0
Y1 S2 Y2 1 2/5
0 1
1 1/10 1 0 2 1/5 0 1/5
0 0 0 1 1 -1
0 1 1 -1/5 0 3/10

1/V = 1/2
0 0 2 0 0 1/2

1/V =1/2 V = 2

y1 = 2/5 * 2 = 4/5 y2 = 1/10 * 2 = 1/5 y3 = 0 * 2 = 0

x1 = 0*2 = 0 x2 = 0*2 = 0 x3 = 1/2*2 = 1

SA = (0, 0, 1)
SB = (4/5, 1/5, 0)
Value = 2

Example 2


Solution



Maximin = -1
Minimax = 1

We can infer that -1 ? V ? 1

Since maximin value is -1, it is possible that value of the game may be negative or zero, thus the constant ‘C’ is added to all the elements of matrix which is at least equal to the negative of maximin.

Let C = 1, add this value to all the elements of the matrix. The resultant matrix is


LPP
Max 1/V = Y1 + Y2 + Y3
Subject to
2Y1 + 0Y2 + 0Y3 ? 1
0Y1 + 0Y2 + 4Y3 ? 1
0Y1 + 3Y2 + 0Y3 ? 1
Y1, Y2, Y3 ? 0

SLPP
Max 1/V = Y1 + Y2 + Y3 + 0s1 + 0s2 + 0s3
Subject to
2Y1 + 0Y2 + 0Y3 + s1 = 1
0Y1 + 0Y2 + 4Y3 + s2 = 1
0Y1 + 3Y2 + 0Y3 + s3 = 1 Y1, Y2, Y3, s1, s2, s3 ? 0

Cj? 1 1 1 0 0 0
Basic Variables CB YB Y1 Y2 Y3 S1 S2 S3 Min Ratio YB / YK
S1 S2 S3 0 1
0 1
0 1 2 0 0 1 0 0 1/2?
-
-
0 0 4 0 1 0
0 3 0 0 0 1

1/V =0 ?
-1 -1 -1 0 0 0
Y1 S2 S3 1 1/2
0 1
0 1 1 0 0 1/2 0 0
0 0 4 0 1 0 -
-
1/3?
0 3 0 0 0 1

1/V =1/2 ?
0 -1 -1 1/2 0 0
Y1
S2 Y2 1 1/2
0 1
1 1/3 1 0 0 1/2 0 0
0 0 4 0 1 0
0 1 0 0 0 1/3 -
1/4?
-

1/V = 5/6 ?
0 0 -1 1/2 0 1/3
Y1 Y3 Y2 1 1/2
1 1/4
1 1/3 1 0 0 1/2 0 0
0 0 1 0 1/4 0
0 1 0 0 0 1/3

1/V =13/12
0 0 0 1/2 1/4 1/3

1/V =13/12 V = 12/13

y1 = 1/2 * 12/13 = 6/13 y2 = 1/3 * 12/13 = 4/13 y3 = 1/4 * 12/13 = 3/13

x1 = 1/2*12/13 = 6/13 x2 = 1/4 * 12/13 = 3/13 x3 = 1/3 * 12/13 = 4/13

SA = (6/13, 3/13, 4/13) SB = (6/13, 4/13, 3/13)

Value = 12/13 – C =12/13 -1 = -1/13