USA: +1-585-535-1023

UK: +44-208-133-5697

AUS: +61-280-07-5697

Linear Programming Method for Games

The linear programming method is used in solving mixed strategies games of dimensions greater than (2 x 2) size. Consider an m x n payoff matrix in which player A (i.e., the row player) has m strategies and player B (i. e., the column player) has n strategies. The elements of pay off  Matrix be {(aij) ; i = 1, 2, . . . , m and j = l, 2, . . . , n}.

 

Let P i be the probability of selection of strategy i by player A and q1 be the probability

of selection of strategy j by player B .

 

LPP FOR PLAYER A

V = min    { Ʃ a il pi       Ʃ a i2 pi   , ….., Ʃ a in pi  }

i                   i                             i

Since the player A is maximin type, the LPP can be written as follows :

Subject  to,

 

P1 +p2+…+pm =1

All pi  ≥0

Maximize v

 

Subject   to ,

P1/v + p2 /v +…+pm /v  =1

 

All p≥ 0

 

Pi /v =x i, i,2,…m. therefore

 

Maximize v =Minimize (1/v)

 

=  Maximize(p1/v +p2/v +…+pm/v)

 

=Maximize (x1+x2+…xm)

Subject to ,

 

 

xi  ≥0,i= 1,2, …, m.

and

 

 

LIPP FOR PLAYER B

Let                                           U =max . {Ʃ a1 j q j, Ʃa2j aj,…..,Ʃ amj  q j}

 

Since the player B is minimax type, the LPP can be written as follows :

Minimize u

 

Subject to,

Ʃ a lj qj  ≤ u

J

 

Ʃ a­2j qj ≤ u

J

--------------

Ʃ a mj  qj≤ u

j

q1 +q2+…b+q n =1

q j ≥ 0

minimize u

subject to,

 

Ʃ a lj( qj / u)≤ 1

j

 

Ʃ a­2j( qj/u) ≤ 1

j

--------------

Ʃ a mj(  qj/u)≤ 1

q1/u+ q2/u+….+qn/u =1

q j ≥0

all

set                                q j /u =y j, j =1,2,.., n, therefore

Minimize u =maximize (1/u)

= Maximize (q1/u+q2/u+..qn/u)

 

Subject to 

Y j ≥ 0, j =1,2,…,n.

Note : 1 In then above approach we may face two problems .value of the  game may be zero or less than zero .first case constraints will become infinite and in the second case the type of each constraint will get change ,therefore to obtain a non-negative value of the game a constant c=max {abs .[negative values ]} +1 is to be added to each elements in the payoff matrix the optimal strategy will not  change .however the value of the original game will be value of the ne game minus constant.

 

2. The above LIPP formulations for player A and B primal –due pair so solving one problems we can read the solution of the other problem from the optimal table

 

Example 8. Solve the following game by linear programming technique :

Player B

Player A     -1    - 1     -1

-1       1       2

1      1      -1

 

Solution. The game has no saddle point. Since the payoff matrix has negative values, let us add a constant c = 2 to each element. The revised payoff matrix is given below

Player B

1          1          3

Player A          1          3          4

3          3          1

Let the strategies of the two players be

SA =     I           II        III                   SB =     I           II        III

P1         P2         P3                                  q1        q2         q3

 

P1+p2+p3+=1     and q1+q2+q3=1

The LIPP for player A:

Maximize  v =minimize l/v =x1+x2+x3

 

Subject to ,                  x1+x2+3x3 ≥1

x1+3x2+3x3 ≥ 1

3x1 + 4x2 + x3 ≥1

x1,x2,x3 ≥ 0

x j =pj/v ,j =1,2,3

where

 

The LIPP for player B:

 

Minimize u =minimize l/u =y1 +y2 +y3

 

Subject to ,                  y1+y2+y3 ≤ l

Y1 +3y2 +4y3 ≤ l

3y1 +3y2 +y3 ≤ l

Y1  ,y2 ,  y3,  ≤ 0

Y j =q j/ u ,j=1,2,3

 

"Let us now solve the problem for player B.

The standard form can be written as follows

 

Maximize l/u =y1+y2+y3+0.s1 +0,s2+0.s3

Subject to ,

y1+y2+3y3+s1 = l

Y1 +3y2 +4y3+s2= l

3y1 +3y2 +y3 +s3= l

Y1  ,y2 ,  y3,   0s1,s2,s3 slacks ≥ 0

 

Iteration  1

Iteration  2

Iteration  3

Y1= 3/11 ,y2 * =0,y3 =2/11 ,    max l/u =5/11 u* 11/5 v*

Original u* =11/5 -2= 1/5 =original v*

Using  duality             X1*  =0 ,x2 =2/11 ,x3* =3/11

Now  q1 = y1.u  =3/11 .11/5 =3/5 , p1 =x1 .v =0

q2 =y2.u =0,                 p2 =x2.v 2/11 .11/5 =2/5

q3 =y3.u = 2/11 /11/5=2/5 ,p3 =x3.v =3/11, 11/5 =3/

 

SA =     I           II         III

0           2/5        3/5

 

SB =     I           II         III       and  V* 1/5

3/5         0         2/5