We use cookies to improve your experience on our site and to show you relevant advertising. By browsing this website, you agree to our use of cookies. Learn more   

AtoZmath.com
Support us
(New) All problem can be solved using search box
I want to sell my website www.AtoZmath.com with complete code
Home What's new College Algebra Games Feedback About us
Algebra Matrix & Vector Numerical Methods Statistical Methods Operation Research Word Problems Calculus Geometry Pre-Algebra


Home > Operation Research calculators > Game Theory >> Saddle Point example
10. Linear programming method example ( Enter your problem )
( Enter your problem )
  1. Method & Example-1
  2. Example-2
 		Other related methods
  1. Saddle point
  2. Dominance method
  3. Oddment method
  4. Algebraic method
  5. Calculus method
  6. Arithmetic method
  7. Matrix method
  8. 2Xn Games
  9. Graphical method
  10. Linear programming method
  11. Bimatrix method
9. Graphical method
(Previous method)		2. Example-2
(Next example)

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 (2`xx`2) size.
Step-2: The example is used to explain the procedure.
Example-1
Find Solution of game theory problem using linear programming method
Player A\Player BB1B2B3
A13-42
A21-7-3
A3-247


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)`.

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


9. Graphical method
(Previous method)		2. Example-2
(Next example)


Share this solution or page with your friends.


Home What's new College Algebra Games Feedback About us
 
Copyright © 2023. All rights reserved. Terms, Privacy
 
 

.