Math 486. September 25, 2002. Midterm 1.
Solutions
 

1. Nim. Last move wins. 2,5, or 9 stones in a move. Initial position: 1 pile, 1000 stones.
We mark positions by W or L  if it is winning  or loosing positions for the player who starts.
Fow winning positions we write  winning moves (the number of stones to take).
 
0 1 2 3 4 5 6 7 8 9
L L W W L W W L L W
2 2 5 5 2,5,9
10 11 12 13 14 15 16 17 18 19
W L W W L L W W L W
2,9 5 2,5,9 2,5,9 2,9 5

So the winning positions repeat with period 7.
The first player wins at initial positions of the form  7n+2,  7n+3, 7n+5, 7n+6. The second player wins
if the first player starts  at the other positions.  In particular,  1000 is 6 modulo 7, so the first player wins
by  taking 2,5, or 9 stones and following the following
 winning strategy:
7n 7n+1 7n+2 7n+3 7n+4 7n+5 7n+6
L L W W L W W
2 2 5 5
There are other optimal strategies for the first player.
Any strategy of the second player is optimal.  The value of the game is $1 for the first player.
It is a zero-sum game.
 

2. Blackjack. Players has 10 and 6. Dealer shows 10.  Cards left: 5, 5, 6, 7.
Here is an extensive form:

                                                   P 16
            P    stands    with 16                                                           P         draws
    D draws (chance move)                                                                     chance move
1/2                        1/4                1/4                                                 1/2                                         1/2
D 15                    D 16              D 17. -$1                                P 21, D 10                                P over.  -$1
chance move          chance move                                       D draws   (chance move}
1/3   1/3  1/3             2/3      1/3                                            1/3              1/3                          1/3
 D20   D21  D22     D21      D23                                        D 15              D 16                     D 17. $1
-$1    -$1   $1        -$1      $1                         chance move                 chance move
                                                                          1/2        1/2                   1/2            1/2
                                                                   D 21.$ 0.   D 22. $1.        D 21. $0.     D 23. $1.
Now we lift the payoff for the player from the terminal positions to all positions:

                                                   P 16    -$1/6
            P    stands    with 16     -$1/2                                                      P         draws  -$1/6
    D draws (chance move)                                                                     chance move
1/2                            1/4                1/4                                                 1/2                                         1/2
D 15.   -$1/3      D 16.  -$1/3      D 17. -$1                                P 21, D 10    $2/3                       P over.  -$1
chance move          chance move                                                          chance move
1/3   1/3  1/3             2/3      1/3                                            1/3              1/3                          1/3
 D20   D21  D22     D21      D23                                   D 15.  $1/2        D 16   $1/2                   D 17. $1
-$1    -$1   $1        -$1      $1                         chance move                 chance move
                                                                          1/2        1/2                   1/2            1/2
                                                                   D 21.$ 0.   D 22. $1.        D 21. $0.     D 23. $1.
So the optimal strategy for the player is to draw once. The payoff is -$1/6.
The dealar 's stratefy is fixed (D has only one strategy).

In Problems 3--5, we mark by * maximal numbers in their columns and by ' the minimal numbers in their rows.
The column player is called She, the row player is called He. His  pure strategies are called  r1,r2,..., and
her strategies are called c1,c2,....

3.
3 4 3 0' 3
5 7* 5* 5 0'
5 4 4 6* 3'
7* 5' 5*' 6* 5*'
So there are two saddle points,     (r4, c3) and (r4,c5). The value of game is 5.
He has only one optimal strategy, r4. She has two optimal pure strategies, c3 and c5, and her optimal mixed strategies are the mixtures of  c3 and c5.
 

4. Matrix game.
3* -1' 2* 0 2
3* 0' 2* 1* 4*
0 3* 2* 1* -1'
There are no sadle points.
His best pure strategy is  r2 with the worst-case payoff 0. Her best pure strategy is c4  where she pays him
at most 1. The value of the game is between 0 and 1.
The strategy c1 is dominated by c2, so he drop c1;  c3 is dominated by c4, so she drops c3. They are left with the matrix game
 
smaller game c1 c2 c4 c5
r2 3 0 1 4
r3 0 3 1 -1
He can get  1 by using   (r2+r3)/2 =(0,1/2.1/2}T   (there are other optimal stratefies). Her optimal strategy  c4 is unique.
The value of the game is 1.
 
 

5.
2 1 2* 0' 3*
2 2 0' 2* 2
3 2 1' 1' 1'
4* 5* 1' 1' 1'
There are no saddle points. The value of game is between  1 and 2.
By domination, she drops  c1,c2, and c5, and he can drop r3 or  r4. they get a smaller game:
 
 smaller game c3 c4
r1 2 0
r2 0 2
r4 1 1
His optimal strategies are the mixtures of  r3 and r4. Her optimal strategy  (c3+c4)/2= (0,0,1/2,1/2,0)
is unique. The value of the game is 1.