Game Theory and LPP:
If for any game, saddle point does not exist and the size of a game matrix can not be
brought to the size of 2x2, 2xn or mx2, then the given game needs to be solved using
LPP method.
We consider the following payoff matrix:
Player B
I II … n
I a11 a12 … a1n
Player A II a21 a22 … a2n
. . . . .
. . . . .
. . . . .
m am1 am2 … amn
Development of LPP model of Player A:
The expected gain to Player A w.r.t. the selection of each of alternatives of B is given
below:
A’s expected payoffs corresponding to B’s strategies are given as follows.
B’s pure strategies Expected payoff of Player A
m
1 a11p1+ a21p2 +…+ ai1pi+…+ am1pm=∑ a i=1
i1 pi
m
2 a12p1+ a22p2 +…+ ai2pi+…+ am2pm=∑ a i=1
i2 pi
⋮ ⋮ ⋮⋮ ⋮ ⋮
m
j a1jp1 + a2jp2+…+ aijpi+…+ amjpm=∑ a i=1
ij pi
⋮ ⋮ ⋮⋮ ⋮
n a1np1+ a2np2 +…+ ainpi+…+ amnpm=∑
i=1
a¿ pi
Descriptive Model for Player A: Since A is a maxmin
player, he tries to maximize the value of the game by
maximizing the minimum of functions:
m m m m
max[min(∑ a i=1
i1 pi ,∑ ai 2 pi ,…,∑ aij pi ,…,∑ a¿ pi)]
i=1 i=1 i=1
Sub to
p1+ p2 +…+ pi+…+ am1pm=1
and p1,p2 …pi…,pm≥0
Since the objective function of this model is not in linear
form, it is called a descriptive model.
LPP model of Player A: Since the descriptive model is not
a workable model, we use we convert this model into an
LPP model by using transformation:
m m m m
V=min (∑ ai 1 pi,∑ ai 2 pi,…,∑ aij pi,…,∑ a¿ pi)
i=1 i=1 i=1 i=1
The linear model with respect to the above substitution is:
Max Z=V
Sub to
m
∑ ai 1 pi ≥V
i=1
m
∑ ai 2 pi ≥V
i=1
⋮
m
∑ aij pi ≥V
i=1
⋮
m
∑ a¿ pi ≥V
i=1
p1+ p2 +…+ pi+…+ pm=1
and p1,p2 …pi…,pm≥0
The set of constraints of the above model can be simplified by
dividing it by V to get:
∑ ai 1 p i
i=1
≥1
V
m
∑ ai 2 p i
i=1
≥1
V
⋮
m
∑ aij p i
i=1
≥1
V
⋮
m
∑ a¿ pi
i=1
≥1
V
p1/V+ p2/V +…+ pi/V+…+ pm/V=1/V
and p1,p2 …pi…,pm≥0
Let pi/V =Xi i=1,2,…,m. Therefore
Max V=min 1/V
=( p1/V+ p2/V +…+ pi/V+…+ pm/V)
=min(X1+X2+…+Xi+…+Xm)
Then by substituting the above function in the above model, we
get the revised model as
Minimize Z1= X1+X2+…+Xi+…+Xm
Sub to
m
∑ ai 1 X 1 ≥ 1
i=1
m
∑ ai 2 X 2 ≥ 1
i=1
⋮
m
∑ aij X i ≥ 1
i=1
⋮
m
∑ a¿ X m ≥ 1
i=1
Xi≥0, i=1,2,…,m
The values of pi where i=1,2,…m and V are obtained using
the following formulae
V=1/Z2
and
pi=V.Xi, i=1,2,…,m
Development of LPP model of Player B:
The expected gain to Player B w.r.t. the selection of each of alternatives of A is given
below:
B’s expected payoffs corresponding to A’s strategies are given as follows.
A’s pure strategies Expected payoff of Player B
n
1 a11q1+ a12q2 +…+ a1jqj+…+ a1nqn=∑
j=1
a1 j q j
n
2 a21q1+ a22q2 +…+ a2jqj+…+ a2nqn=∑
j=1
a2 j q j
⋮ ⋮ ⋮⋮ ⋮ ⋮
n
i ai1q1 + ai2q2+…+ aijqj+…+ ainqn=∑ a q j=1
ij j
⋮ ⋮ ⋮⋮ ⋮
m am1q1+ am2q2 +…+ amjqj+…+ amnqn=∑ a j=1
mj qj
Descriptive Model for Player A: Since A is a maxmin
player, he tries to maximize the value of the game by
maximizing the minimum of functions:
n n n n
min[max(∑ a j=1
1j q j,∑ a2 j q j,∑ aij q j
j=1 j=1
,…,∑ a
j=1
mj q j]
Sub to
q1+ q2 +…+ qi+…+ qm=1
and q1,q2 …qi…,qm≥0
Since the objective function of this model is not in linear
form, it is called a descriptive model.
LPP model of Player A: Since the descriptive model is not
a workable model, we use we convert this model into an
LPP model by using transformation:
n n n n
V=min (∑ a1 j q j,∑ a2 j q j,∑ aij q j
j=1 j=1 j=1
,…,∑ a
j=1
mj q j)
The linear model with respect to the above substitution is:
Min Z=V
Sub to
n
∑ a1 j q j ≤ V
j=1
n
∑ a2 j q j ≤ V
j=1
⋮
n
∑ aij q j ≤ V
j=1
⋮
n
∑ amj q j ≤ V
j=1
q1+ q2 +…+ qi+…+ qm=1
and q1,q2 …qi…,pm≥0
The set of constraints of the above model can be simplified by
dividing it by V to get:
n
∑ a1 j q j /V ≤ 1
j=1
n
∑ a2 j q j /V ≤1
j=1
⋮
n
∑ aij q j /V ≤ 1
j=1
⋮
n
∑ amj q j /V ≤ 1
j=1
q1/V+ q2/V +…+ qi/V+…+ qn/V=1/V
and q1,q2 …qi…,qn≥0
Let qj/V =Yj j=1,2,…,n. Therefore
Min V=Max 1/V
=( q1/V+ q2/V +…+ qi/V+…+ qn/V)
=max(Y1+Y2+…+Yj+…+Yn)
Then by substituting the above function in the above model, we
get the revised model as
Max Z2= Y1+Y2+…+Yj+…+Yn
Sub to
n
∑ a1 j Y 1 ≤ 1
j=1
∑ a2 j Y 2 ≤ 1
j=1
⋮
n
∑ aij Y j ≤ 1
j=1
⋮
n
∑ amj Y j ≤1
j=1
Yj≥0
The values of qj where j=1,2,…n and V are obtained using
the following formulae
V=1/Z2
and
qj=V.Yj, j=1,2,…,n
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:
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 a constant ‘K’ is added to all the elements of matrix
which is at least equal to the negative of maximin.
Let K = 1+1=2 , add this value to all the elements of the matrix. The
resultant matrix is
And we write the problem of Player B as:
LPP
Max 1/V = Y1 + Y2 + Y3
Subject to
3y1 + y2+ y3 ≤ V
y1 + y2+ 5y3 ≤ V
y1 + 4y2+ y3 ≤ V
y1, y2, y3 ≥ 0
Standard LPP
We define Yj=yj/V and divide the constraints by V
Max 1/V = Y1 + Y2 + Y3
Subject to
3Y1 + Y2 + Y3 ≤ 1
Y1 + Y2 + 5Y3 ≤ 1
Y1 + 4Y2 + Y3 ≤ 1
Y1, Y2, Y3 ≥ 0
Max Z2 = Y1 + Y2 + Y3 + 0X1 + 0X2 + 0X3
3Y1 + Y2 + Y3 + X1 = 1
Y1 + Y2 + 5Y3 +X2 = 1
Y1 + 4Y2 + Y3 + X3 = 1
Y1, Y2, Y3, X1, X2, X3 ≥ 0
Cj
→ 1 1 1 0 0 0
Basic Min Ratio
CB Y1 Y2 Y3 X1 X2 X3 XB
Variables YB/YK
X1 0 3 1 1 1 0 0 1 1/2→
X2 0 1 1 5 0 1 0 1 -
X3 0 1 4 1 0 0 1 1 1
↑
Zj-Cj -1 -1 -1 0 0 0 Z2=0
Y1 1 1 1/3 1/3 1/3 0 0 1/3 1
X2 0 0 2/3 14/3 -1/3 1 0 2/3 1
X3 0 0 11/3 2/3 -1/3 0 1 2/3 2/11→
↑
Zj-Cj 0 -2/3 -2/3 1/3 0 0 Z2=1/3
Y1 1 1 0 3/11 4/11 0 -1//11 3/11 1
X2 0 0 0 50/11 -3/11 1 -2/11 6/11 3/25→
Y2 1 0 1 2/11 -1/11 0 3/11 2/11 1
↑
Zj-Cj 0 0 -6/11 3/11 0 2/11 Z2= 5/11
Y1 1 1 0 0 19/50 -3/50 -2/25 6/25
Y3 1 0 0 1 -3/50 11/50 -1/25 3/25
Y2 1 0 1 0 -2/25 -1/25 7/25 4/25
Zj-Cj 0 0 0 6/25 3/25 4/25 Z2=13/25
Thus,
We have
Y1=6/25
Y2=4/25
Y3=3/25 and
and
Z2=13/25
and
V =1/ Z2
= 25/13
y1 = V.Y1=(25/13).(6/25)=6/13 = 6/13
y2 = V.Y2=(25/13).(4/25)=6/13 = 4/13
y3 = V.Y3=(25/13).(3/25)=3/13 = 6/13
and V*=V-K=25/13-2=-1/13
Also, using the primal-dual relations, we obtain
X1=6/25, X2=3/25 , X3=4/25 and Z1=13/25 to get
V=1/ Z1=1/13/25=25/13
and
x1 = V.X1=(25/13).(6/25)=6/13
x2 = V.X2=(25/13).(3/13) = 3/13
x3 = V.X3=(25/13).(4/13)= 4/13
SA = (6/13, 3/13, 4/13)
SB = (6/13, 4/13, 3/13)
V*=V-K=25/13-2=-1/13
Example 2:
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 and no need of adding a constant. Thus. Player B’s
problem can be written as:
LPP
Max Z1 = Y1 + Y2 + Y3
Subject to
3Y1 – 2Y2+ 4Y3 ≤ 1
-1Y1 + 4Y2 + 2Y3 ≤ 1
2Y1 + 2Y2+ 6Y3 ≤ 1
Y 1, Y 2, Y 3 ≥ 0
SLPP
Max Z2 = Y1 + Y2 + Y3 + 0.X1 + 0.X2 + 0.X3
Subject to
3Y1 – 2Y2 + 4Y3 + X1 = 1
-1Y1 + 4Y2 + 2Y3 +X2 = 1
2Y1 + 2Y2 + 6Y3 + X3 = 1
Y1 , Y 2 , Y 3 , X 1 , X 2 , X 3 ≥ 0
Cj→ 1 1 1 0 0 0
Basic Min Ratio
CB Y1 Y2 Y3 X1 X2 X3 XB
Variables YB/YK
X1 0 3 -2 4 1 0 0 1 1/3→
X2 0 -1 4 2 0 1 0 1 -
X3 0 2 2 6 0 0 1 1 1/2
↑ 1
-1 -1 -1 0 0 0 Z2=1/V=0
Y1 1 1/3 1 -2/3 4/3 1/3 0 0 1/3 -
X2 0 4/3 0 10/3 10/3 1/3 1 0 4/3 2/5
X3 0 1/3 0 10/3 10/3 -2/3 0 1 1/3 1/10→
↑ 1/3
0 -5/3 1/3 1/3 0 0 Z2= 1/V =1/3
Y1 1 1 0 2 1/5 0 1/5 2/5
X2 0 0 0 0 1 1 -1 1
Y2 1 0 1 1 -1/5 0 3/10 1/10
0 0 2 0 0 1/2 Z2= 1/V = 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)
V=2
