Answer to Question #170601 in Operations Research for Gaurav Goyal

Question

Consider the pay-off table for two players as given below:

1 2 3

Player A 1|-4 -2 6|

2| 3 0 3 |

3| 6 -3 -5 |

(i) Find the saddle point the value of the game.

(ii) Give two equivalent linear programming problems for the above problem.

Answer 1

i) In a zero-sum matrix game, an outcome is a saddle point if the outcome is a minimum in its row and maximum in its column.

.In our case the saddle point is (minimum in the 2nd row and maximum in the 2nd column).

ii) Player's A LP:

min $w$

$4x_1+2x_2-6x_3+w\geq0$

$-3x_1-3x_3+w\geq0$

$-6x_1+3x_2+5x_3+w\geq0$

$x_1+x_2+x_3=1$

$x_1,x_2,x_3\geq0$

Player's A LP:

min $z$

$4v_1-3v_2-6v_3+z\leq0$

$2v_1+3v_3+z\leq0$

$-6v_1-3v_2+5v_3+z\leq0$

$v_1+v_2+v_3=1$

$v_1,v_2,v_3\geq0$

$x_i,v_i$ - probability of choosing action i, $i\isin \{1,2,3\}$