Math 486  Game Theory Miderm 2  March 20, 2003.  5 problems, 13 pts each.
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
* maximal in its column
' 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
We name rows r1,r2,r3 and columns c1,c2,c3,c4,c5,c6,c7. By domination, we are reduced to the following 3 by 4 matrix game:
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]and   [0, 0, 0.1, 0.3, 0, 0, 0.6].
 

 

3.
0 1 -1 1
-1 0 1 1
1 -1 0 1
The last column goes by domination. What is left is a familiar  symmetric game.
An optimal strategy for the row player is   [1/3,1/3,1/3]T.
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  xi>=  0:
4.
x1 x2 x3 x4 x5 1
1 2 -3 5 6 -2 = -x6
0 -1 2 0 3 1 = x7
-1 0 2 4 -4 2 = x8
2 0 3 0 1 2 = f -> min
We obtain a standard row tableau by multiplying the last column and the last  3 rows by -1:
x1 x2 x3 x4 x5 -1
1 2 -3 5 6 2 = -x6
0 1 -2 0 -3 1 = - x7
1 0 -2 -4 4 2 =  -x8
-2 0 -3 0 -1 2 = - f -> max
This is an optimal tableau, so the basic solution
x1 = x2 = x3 = x4 = x5 = 0, x6 =  2,   x7=  1,  x8 = 2,   max(-f)  =  -2, min(f) =2.
All optimal solutions are described as follows:
x1 =   x3x5 = 0,  x6 = 2-  2x1   -5 x4 >=0,  x7 = 1 -x2 >=0, x8=  2+ 4x4, x2 , x4 >= 0.

5.
x1 x2 x3 x3 x5 -1
1 2 -3 5 6 -2 = -x6
0 -1 2 0 3 1 = x7
-1 0 2 4 -4 2 = 0
2 0 3 0 1 2   -> max

Combainning two  x3 -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.