1. Nim. Last move loses. Player may take 1, 5, or 8 stones in
a move. Initial position: 1 pile, 1000 stones.
Who wins and how?
Solution.
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 |
| W | L | W | L | W | L | W | L | W | W |
| terminal | 1 | 1 | 1,5 | 1,5 | 8 |
| 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 |
| W | W | W | W | L | W | L | W | L | W |
| 5 | 8 | 5 | 8 | 1,8 | 1 | 1,5 |
So the winning positions repeat with period 13.
The first player wins at initial positions of the forms
13n, 13n+2, 13n+4, 13n+6, 13n+8, 13n+9,13n+10, 13n+11, and
13n+12.
The second player wins
if the first player starts at the other positions, namely, 13n+1,
13n+3, 13n+5, 13n+7.. In particular, 1000=13*76+12 is
12 modulo 13, so the first player wins
by taking 5 stones.
Any strategy of the second player is optimal.
2. Blackjack. P has 10 and 7. Dealer shows 10. Cards left: 6,
6, 6,8, 8. Bet is $10.
(a) P is the only player.
(b) P is the second player, and the first player draws a card.
Find an optimal strategy and the corresponding payoff.
Solution.
P goes over if draws, so P stands.
In the case (a), P wins with probability 3/5 and loses with probability
2/5. The expected payoff is $2.
An extensive form is
chance move ($2)
/
\
3/5
2/5
/
\
$10
-$10
In the case (b), an extensive form is
chance move ($2)
/
\
3/5
2/5 (first player draws)
/
\
6,6,8,8 left
($0)
6,6,6,8 left ($5)
(cards left; lifted payoff)
/
\
/ \
1/2
1/2
3/4 1/4
(dealer's face-down card 6 or 8)
/
\
/
\
$10
-$10
$10
-$10
(P's payoff)
The expected payoff is $2.
3. Matrix game.
| 3 | 4 | 3 | 0 | 3 |
| 5 | 5 | 5 | 5 | 6 |
| 5 | 4 | 4 | 6 | 3 |
| 7 | 5 | 3 | 6 | 4 |
Solution.
| 3 | 4 | 3 | 0' | 3 |
| 5' | 5*' | 5*' | 5' | 6* |
| 5 | 4 | 4 | 6* | 3' |
| 7* | 5* | 3' | 6* | 4 |
4. Extensive form, 3 players, A B, C.
initial position
chance move
/
\
0.1
0.9
/
\
A
B
/
\
/ \
B
C
B C
/ \
/ \
/ \ /
\
1,2,3 0,0,0 -1,-2,-3
1,0,1 0,1,0
-2,0,2
Find an equilibrium and the corresponding payoff.
Solution.
initial position 0.1, 1.1, 0.3
chance move
/
\
0.1
0.9
/
\
A 1,2,3
B 0,1,0
//
\
// \
B 1,2,3
C 0,0,0
0,1,0 B
C -2,0,2
/ / \
// \
/ \ \ /
\ \
1,2,3 0,0,0 -1,-2,-3
1,0,1 0,1,0
-2,0,2
5. Roulete. P bets $x on black in roulette (with 0 and 00) using a coupon which gives him additional $y in case of winning. Compute P's expected payoff.
Solution.
The payoff is (x+y)(9/19)-x(10/19)= (9y - x)/19.
6. Blackjack insurance. Dealer's face-up card is Ace. The house
bets 2 to 1 up to $100 that
the dealer will not get a blackjack. Should the player take the
bet?
(a) There are many decks in the shoe.
(b) One deck is used, and the player has 10+10.
Solution. (a) The player wins (insurance pays) with probability
4/13. So if his bet is $x, then his expected payoff
is $(4/13)2x-(9/13)x= -$x/8. He should not buy insurance (x=0).
(b) The player wins (insurance pays) with probability 14/49.So if his
bet is $x, then his expected payoff
is $(14/49)2x-(35/49)x= -$x/7. He should not buy insurance.