Name Leon Vaserstein

1-3. Solve matrix games:

1.

1' | 3 | 5 | 7 | 1' | 3 | 2 |

7* | 8* | 6*' | 8* | 7* | 6*' | 6*' |

1 | -5' | 4 | 3 | 4 | 0 | 1 |

3 | 5 | 6* | -3' | 0 | 1 | 3 |

2 | 3 | -2' | 0 | 1 | 2 | 0 |

' minimal in its row

There are 3 saddle ponts: the second row, columns 3, 6, and 7.

The value of game is 6.

The optimal strategy for the row player: choose the second row.

The optimal strategy for the column player: use any mixture of columns 3,6,7.

2.

0 | 0 | 0 | -2 | -2 | -1 | -2 |

0 | 4 | 3 | -1 | -2 | -1 | -1 |

0 | 4 | 3 | 0 | -2 | 0 | -1 |

3 | 0 | -3 | 0 | 2 | 2 | 0 |

0 | 3 | 3 | -2 | -3 | 0 | 0 |

c3 | c4 | c5 | c7 | |

r3 | 3 | 0 | -2 | -1 |

r4 | -3 | 0 | 2 | 0 |

r5 | 3 | -2 | -3 | 0 |

It is easy to find good strategies for both players. To find optimal
strategies, I used Mathematica 4.1 for Sun Solaris. Here is how I enter
data:

a = {{3, 0, -2, -1}, {-3, 0, 2, 0}, {3, -2, -3, 0}};

x = {x3, x4, x5}; y = {y3, y4, y5, y7};

where

a is the payoff matrix,

x =p/(u+10) is strategy for the row player p divided by
(the value of game+10);

y =q/(v*10) is strategy q for the row player divided by
(the value of game+10).

To find optimal x:

ConstrainedMin[Apply[Plus, x], Table[(x.(a + 10))[[i]] > 1, {i,
4}], x]

Answer:

{10/97, {x3 -> 3/97, x4 -> 11/194, x5 -> 3/194}

So the value of game is 97/10-10= -0.3

and an optimal strategy for the row player is 10x/97= [p3,p4,p5]^{T}=[0.3,0.55,0.15]^{T}.

Similarly, input

ConstrainedMax[Apply[Plus, y], Table[((a + 1).y)[[i]] < 1,
{i, 3}], y]

gives output

{10/7, {y3 -> 1/7, y4 -> 3/7, y5 -> 0, y7 -> 6/7}}

so an optimal strategy for the column player is

[q3,q4,q5,q7]=[0.1, 0.3, 0,0.6].

In the terms of the origional problem, optimal strategies are

[0, 0, 0.3,0.55,0.15]^{T }and [0, 0, 0.1,
0.3, 0, 0, 0.6].

3.

0 | 1 | -1 | 1 |

-1 | 0 | 1 | 1 |

1 | -1 | 0 | 1 |

An optimal strategy for the row player is [1/3,1/3,1/3]

An optimal strategy for the column player is [1/3,1/3,1/3,0].

The value of game is 0.

4-5. Solve the linear programs, where all *x _{i}*>=
0:

4.

x_{1} |
x_{2} |
x_{3} |
x_{4} |
x_{5} |
1 | |

1 | 2 | -3 | 5 | 6 | -2 | = -x_{6} |

0 | -1 | 2 | 0 | 3 | 1 | = x_{7} |

-1 | 0 | 2 | 4 | -4 | 2 | = x_{8} |

2 | 0 | 3 | 0 | 1 | 2 | = f -> min |

x_{1} |
x_{2} |
x_{3} |
x_{4} |
x_{5} |
-1 | |

1 | 2 | -3 | 5 | 6 | 2 | = -x_{6} |

0 | 1 | -2 | 0 | -3 | 1 | = - x_{7} |

1 | 0 | -2 | -4 | 4 | 2 | = -x_{8} |

-2 | 0 | -3 | 0 | -1 | 2 | = - f -> max |

All optimal solutions are described as follows:

5.

x_{1} |
x_{2} |
x_{3} |
x_{3} |
x_{5} |
-1 | |

1 | 2 | -3 | 5 | 6 | -2 | = -x_{6} |

0 | -1 | 2 | 0 | 3 | 1 | = x_{7} |

-1 | 0 | 2 | 4 | -4 | 2 | = 0 |

2 | 0 | 3 | 0 | 1 | 2 | -> max |

Combainning two *x*_{3 }-columns into one and pivoting
on 6 in this column gives a standard row tableau

with the first row bad. Also the first row in the origional tableau
gives an infeasible constraint.

The program is infeasible.