Method

linear programming method Steps (Rule)
Step-1:	The linear programming technique is used for solving mixed strategy games of dimensions greater than (2`xx`2) 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:
1. Saddle point testing
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`		Row Minimum
Player `A`	`A_1`		(3)	-4	2		`-4`
	`A_2`		1	-7	-3		`-7`
	`A_3`		[-2]	4	7		`[-2]`
	Column Maximum		`(3)`	`4`	`7`

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

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

Here, Column MiniMax `!=` Row MaxiMin

`:.` 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+0xx1` `Z_j=sum C_B y_1`	`0` `0=0xx(-1)+0xx(-4)+0xx7` `Z_j=sum C_B y_2`	`0` `0=0xx5+0xx0+0xx10` `Z_j=sum C_B y_3`	`0` `0=0xx1+0xx0+0xx0` `Z_j=sum C_B S_1`	`0` `0=0xx0+0xx1+0xx0` `Z_j=sum C_B S_2`	`0` `0=0xx0+0xx0+0xx1` `Z_j=sum C_B S_3`
		`C_j-Z_j`	`1` `1=1-0``uarr`	`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-:6` `R_1`(new)`= R_1`(old)`-: 6`	`1` `1=6-:6` `R_1`(new)`= R_1`(old)`-: 6`	`-1/6` `-1/6=(-1)-:6` `R_1`(new)`= R_1`(old)`-: 6`	`5/6` `5/6=5-:6` `R_1`(new)`= R_1`(old)`-: 6`	`1/6` `1/6=1-:6` `R_1`(new)`= R_1`(old)`-: 6`	`0` `0=0-:6` `R_1`(new)`= R_1`(old)`-: 6`	`0` `0=0-:6` `R_1`(new)`= R_1`(old)`-: 6`	---
`S_2`	`0`	`1/3` `1/3=1-4xx1/6` `R_2`(new)`= R_2`(old)`- 4 R_1`(new)	`0` `0=4-4xx1` `R_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/6` `R_2`(new)`= R_2`(old)`- 4 R_1`(new)	`-2/3` `-2/3=0-4xx1/6` `R_2`(new)`= R_2`(old)`- 4 R_1`(new)	`1` `1=1-4xx0` `R_2`(new)`= R_2`(old)`- 4 R_1`(new)	`0` `0=0-4xx0` `R_2`(new)`= R_2`(old)`- 4 R_1`(new)	---
`S_3` Leaving variable	`0`	`5/6` `5/6=1-1/6` `R_3`(new)`= R_3`(old)`- R_1`(new)	`0` `0=1-1` `R_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/6` `R_3`(new)`= R_3`(old)`- R_1`(new)	`-1/6` `-1/6=0-1/6` `R_3`(new)`= R_3`(old)`- R_1`(new)	`0` `0=0-0` `R_3`(new)`= R_3`(old)`- R_1`(new)	`1` `1=1-0` `R_3`(new)`= R_3`(old)`- R_1`(new)	`(5/6)/(43/6)=5/43``->`
`Z_q=1/6` `1/6=1xx1/6` `Z_j=sum C_B X_B`		`Z_j` `Z_j=sum C_B x_j`	`1` `1=1xx1+0xx0+0xx0` `Z_j=sum C_B y_1`	`-1/6` `-1/6=1xx(-1/6)+0xx(-10/3)+0xx43/6` `Z_j=sum C_B y_2`	`5/6` `5/6=1xx5/6+0xx(-10/3)+0xx55/6` `Z_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+0xx0` `Z_j=sum C_B S_2`	`0` `0=1xx0+0xx0+0xx1` `Z_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/43` `R_1`(new)`= R_1`(old)`+ 1/6 R_3`(new)	`1` `1=1+1/6xx0` `R_1`(new)`= R_1`(old)`+ 1/6 R_3`(new)	`0` `0=(-1/6)+1/6xx1` `R_1`(new)`= R_1`(old)`+ 1/6 R_3`(new)	`45/43` `45/43=5/6+1/6xx55/43` `R_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/6xx0` `R_1`(new)`= R_1`(old)`+ 1/6 R_3`(new)	`1/43` `1/43=0+1/6xx6/43` `R_1`(new)`= R_1`(old)`+ 1/6 R_3`(new)
`S_2`	`0`	`31/43` `31/43=1/3+10/3xx5/43` `R_2`(new)`= R_2`(old)`+ 10/3 R_3`(new)	`0` `0=0+10/3xx0` `R_2`(new)`= R_2`(old)`+ 10/3 R_3`(new)	`0` `0=(-10/3)+10/3xx1` `R_2`(new)`= R_2`(old)`+ 10/3 R_3`(new)	`40/43` `40/43=(-10/3)+10/3xx55/43` `R_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/3xx0` `R_2`(new)`= R_2`(old)`+ 10/3 R_3`(new)	`20/43` `20/43=0+10/3xx6/43` `R_2`(new)`= R_2`(old)`+ 10/3 R_3`(new)
`y_2`	`1`	`5/43` `5/43=5/6xx6/43` `R_3`(new)`= R_3`(old)`xx6/43`	`0` `0=0xx6/43` `R_3`(new)`= R_3`(old)`xx6/43`	`1` `1=43/6xx6/43` `R_3`(new)`= R_3`(old)`xx6/43`	`55/43` `55/43=55/6xx6/43` `R_3`(new)`= R_3`(old)`xx6/43`	`-1/43` `-1/43=(-1/6)xx6/43` `R_3`(new)`= R_3`(old)`xx6/43`	`0` `0=0xx6/43` `R_3`(new)`= R_3`(old)`xx6/43`	`6/43` `6/43=1xx6/43` `R_3`(new)`= R_3`(old)`xx6/43`
`Z_q=13/43` `13/43=1xx8/43+1xx5/43` `Z_j=sum C_B X_B`		`Z_j` `Z_j=sum C_B x_j`	`1` `1=1xx1+0xx0+1xx0` `Z_j=sum C_B y_1`	`1` `1=1xx0+0xx0+1xx1` `Z_j=sum C_B y_2`	`100/43` `100/43=1xx45/43+0xx40/43+1xx55/43` `Z_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+1xx0` `Z_j=sum C_B S_2`	`7/43` `7/43=1xx1/43+0xx20/43+1xx6/43` `Z_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)`.

---

---