lOMoARcPSD|47086496

Sol2 - Solutions section 2

Game theory (Technische Universiteit Delft)

Scannen om te openen op Studeersnel

Studeersnel wordt niet gesponsord of ondersteund door een hogeschool of universiteit

Gedownload door remco dassen (remcodassen2@gmail.com)
 lOMoARcPSD|47086496

Solutions to Exercises of Section II.1.

1. The new payoff matrix is

−1 +2
+2 −4
If player I uses the mixed strategy (p, 1 − p), the expected payoff is −1p + 2(1 − p)
if II uses column 1, and −2p − 4(1 − p) if II uses column 2. Equating these, we get
−p + 2(1 − p) = 2p − 4(1 − p) and solving for p gives p = 2/3 . Use of this strategy
guarantees that player I wins 0 on the average no matter what II does. Similarly, if II uses
the same mixed strategy (2/3, 1/3), II is guaranteed to win 0 on the average no matter
what I does. Thus, 0 is the value of the game. Since the value of a game is zero, the game
is fair by definition.

2. The payoff matrix is

red 2 black 7
! "
black Ace −2 1
red 8 8 −7
Solving −2p + 8(1 − p) = p − 7(1 − p) gives p = 5/6 as the probability that Player I should
use the black Ace. Similarly, q = 5/9 is the probability that Player II should use the red
2. The value is −1/3 .

3. If Professor Moriarty stops at Canterbury with probability p and continues to Dover

with probability 1−p, then his average payoff is 100p if Holmes stops at Canterbury, and is
−50p + 100(1 − p) if Holmes continues to Dover. Equating these payoffs gives 250p = 100 ,
or p = 2/5 . Use of this mixed strategy guarantees Moriarty an average payoff of 100p = 40 .
On the other hand, if Holmes stops at Canterbury with probability q and continues
to Dover with probability 1 − q , then his average payoff is 100q − 50(1 − q) if Moriarty
stops at Canterbury, and is 100(1 − q) if Holmes continues to Dover. Equating these gives
q = 3/5 . Use of this strategy holds Moriarty to an average payoff of 40 .
The value of the game is 40, and so the game favors Moriarty. But, as related by
Dr. Watson in The Final Problem, Holmes outwitted Moriarty once again and held the
diabolical professor to a draw.

4. Without the side payment, the game matrix in cents is

1 2
! "
1 55 10
2 10 110
Let p be the probability that Player I (Alex) uses row 1. Equating his payoffs if Player II
uses cols 1 or 2 gives 55p + 10(1 − p) = 10p + 110(1 − p), or 145p = 100 or p = 20/29 .
If Player I uses (20/29, 9/29), his average payoff is 55(20/29) + 10(1 − 9/29) = 1190/29 .
1
Since this is 41 29 , a side payment of 42 cents overcompensates slightly. With the side
payment, the game is in Olaf’s favor by 28/29 of one cent.

II – 1

Gedownload door remco dassen (remcodassen2@gmail.com)

 lOMoARcPSD|47086496

Solutions to Exercises of Section II.2.

1. The value is −4/3 . The mixed strategy, (2/3,1/3), is optimal for I, and the mixed
strategy (5/6,1/6) is optimal for II.
2. If t ≤ 0 , the strategy pair ⟨1, 1⟩ is a saddle-point, and the value is v(t) = 0 . If
0 ≤ t ≤ 1 , the strategy pair ⟨2, 1⟩ is a saddle-point, and the value is v(t) = t . If t > 1 ,
there is no saddle-point; I’s optimal strategy is ((t − 1)/(t + 1), 2/(t + 1)), II’s optimal
strategy is (1/(t + 1), t/(t + 1)), and the value is v(t) = 2t/(t + 1).

v(t)

0 1
3. Suppose that ⟨x, y⟩ and ⟨u, v⟩ are saddle-points. Look at the four numbers ax,y ,
ax,v , au,v , and au,y . We must have ax,y ≤ ax,v since ax,y is the minimum in its row.
Also, ax,v ≤ au,v since au,v is the maximum of its column. Keep going: au,v ≤ au,y since
au,v is the minimum of its row and au,y ≤ ax,y since ax,y is the maximum of its column.
We have
ax,y ≤ ax,v ≤ au,v ≤ au,y ≤ ax,y .
Since this begins and ends with the same number, we must have equality throughout:
ax,y = ax,v = au,v = au,y = ax,y . (This argument also works if x = u or y = v .)
4. (a) Column 2 dominates column 1; then row 3 dominates row 4; then column 4
dominates column 3; then row 1 dominates row 2. The resulting submatrix consists of
rows 1 and 3 vs. columns 2 and 4. Solving this 2 by 2 game and moving back to the
original game we find that the value is 3/2, I’s optimal strategy is p = (1/2, 0, 1/2, 0) and
II’s optimal strategy is q = (0, 3/8, 0, 5/8).
(b) Column 2 dominates column 4; then (1/2)row 1 + (1/2)row 2 dominates row 3;
then (1/2) col 1 + (1/2)col 2 dominates col 3. The resulting 2 by 2 game is easily solved.
Moving back to the original game we find that the value is 30/7, I’s optimal strategy is
(2/7,5/7,0) and II’s optimal strategy is (3/7,4/7,0,0).
5. (a) From the graph on the left, we guess that Player II uses columns 1 and 4.
Solving this 2 by 2 subgame gives
1/2 1/2
! "
7/10 3 0
Value = 1.5
3/10 −2 5

II – 2

Gedownload door remco dassen (remcodassen2@gmail.com)

 lOMoARcPSD|47086496

We conjecture I’s optimal strategy is (.7,.3), II’s optimal strategy is (.5,0,0,.5), and the
value is 1.5. Let us check how well I’s strategy works on columns 2 and 3. For column
2, 2(.7) + 1(.3) = 1.7 and for column 3, 4(.7) − 4(.3) = 1.6 , both greater than 1.5. This
strategy guarantees I at least 1.5 so our conjecture is verified.
5
4 col 3 12 row 3
3 col 1
2 col 2 8 8 row 2
1
0 4
p 10 col 4

-2 0 0 row 1
p

-4 -4
(b) (3/8)col 1 + (5/8)col 2 dominates col 3. Removing column 3 leaves a 3 by 2 game
whose payoffs for a given q are displayed in the graph on the right. The upper envelope
takes on its minimum value at the intersection of row 1 and row 2. Solving the 2 by 2
game in the upper left corner of the original matrix gives the solution. Player I’s optimal
strategy is (1/3,2/3,0), Player II’s optimal strategy is (1/3,2/3,0), and the value is 16/3.
6. (a) The first row is dominated by the third; the seventh is dominated by the fifth.
Then the third column is dominated by the first; the fourth is dominated by the second; the
fifth column is dominated by the seventh. Then the middle row is dominated. When these
three rows and columns are removed, the resulting matrix is the 4 by 4 identity matrix with
value v = 1/4 and optimal strategies giving equal weight 1/4 to each choice. This results in
the optimal strategies p = (0, .25, .25, 0, .25, .25, 0) for I, and q = (.25, .25, 0, 0, 0, .25, .25)
for II.
(b) For all n , domination reduces the game matrix to the identity matrix. We find the
value for arbitrary n ≥ 2 to be vn = 1/(2k) for n = 4k − 2, 4k − 1, 4k , and vn = 1/(2k + 1)
for n = 4k + 1 . For n equal to 2 or 3, the optimal strategies are simple special cases.
For n ≥ 4 , an optimal strategy for Player I is p = (p1 , p2 , . . . , pn ), symmetric about its
midpoint and such that for i ≤ (n#+ 1)/2 ,
vn if i = 2 or 3 mod 4
pi =
0 if i = 0 or 1 mod 4.
Similarly, an optimal strategy for Player II is q = (q1 , . . . , qn ), symmetric about its mid-
point and such that for j ≤ (n + 1)/2
$ ,
vn if j = 1 or 2 mod 4
qj =
0 if j = 0 or 3 mod 4.

7. If Player I uses p and Player II uses column 1, the average payoff is (6/37)5 +
(20/37)4 + (11/37) = 121/37 . Similarly for columns 2, 3, 4 and 5, the average payoffs are

II – 3

Gedownload door remco dassen (remcodassen2@gmail.com)

 lOMoARcPSD|47086496

121/37, 160/37, 121/37, and 161/37. So Player I can guarantee an average payoff of at
least 121/37 by using p . Similarly, if Player II uses q and Player I uses rows 1, 2, 3, or
4, the average payoffs are 121/37, 121/37, 120/37, and 121/27 respectively. By using q ,
Player II can keep the average payoff to at most 121/37. Thus, 121/37 is the value of the
game and p and q are optimal strategies.
8. If (52/143, 50/143.41/143) is optimal, then the value is the minimum of the inner
product of this vector with the three columns of the matrix. This inner product with each
of the three columns gives the same number, namely 96/143 , which is then the value.
9. The matrix is
1 2 3
⎛ ⎞
1 0 1 2
2⎝1 0 1⎠
3 2 1 0
(1/2)row 1 + (1/2)row 3 dominates row 2; then (1/2)col 1 + (1/2)col 3 dominates row
2. Solving the resulting 2 by 2 game and moving back to the original game, we find the
value is 1 and an optimal stratgey for I is (1/2,0,1/2), and an optimal strategy for II is
(1/2,0,1/2). However, the pure strategy of choosing col 2 is also optimal. In fact it is better
than the mixed strategy (1/2,0,1/2) whenever Player I makes the mistake of playing row
2.
) * +
an n×n magic square, A = aij , there is a number s such that i aij = s for
10. In+
all j , and j aij = s for all i. If Player I uses the mixed strategy p = (1/n, 1/n, . . . , 1/n)
his average payoff is V = s/n no matter what Player II does. The same goes for player II,
so the value is s/n and p is optimal for both players. In the example, n = 4 and s = 34 ,
so the value of the game is 17/2 and the optimal strategy is (1/4, 1/4, 1/4, 1/4).
11. (a) First, 6 dominates 4 and 5. With 4 and 5 removed, C dominates D and F ;
A dominates E . Also, the mixture (3/4)A + (1/4)C dominates B . Then with B , D , E
and F removed, 3 dominates 2 and 1. The resulting 2 by 2 game
A C
! "
3 18 31
6 23 19

is easily solved. The value is 21 + 14

17 . Optimal for Player I is (0, 0, 4/17, 0, 0, 13/17) and
optimal for Player II is (12/17, 0, 5/17, 0, 0, 0).
(b) Neither player was using an optimal strategy. The German choice was very poor,
and the Allies were lucky. (Or did they have inside information?)

II – 4

Gedownload door remco dassen (remcodassen2@gmail.com)

 lOMoARcPSD|47086496

Solutions to Exercises II.3.

1.(a) There is a saddle at row 2, column 3. The value is 1.

⎛ ⎞
1 −2 3
1
(b) The inverse is A−1 = ⎝ 2 1 1 ⎠.
5
−3 6 −4

(c) The mixed strategy (1/4, 1/2, 1/4), for example, is optimal for II.

(d) Equation (16) gives q = (2/5, 4/5, −1/5). Equations (16) are valid when A is
nonsingular and Player I has an optimal strategy giving positive weight to each strategy.
That is not the case here.

2.(a) If di = 0 for some i, then (row i, col i) is a saddlepoint of value zero. And row
i and col i are optimal pure strategies for the players.

(b) If di > 0 and dj < 0 , then (row i, col j ) is a saddlepoint of value zero. And row
i and col j are optimal pure strategies for the players.

+m (c) If all di < 0 , then the same analysis as in Section 3.3 holds. The value is V =
1 1/di , and the players have the same optimal strategy, (V /d1 , . . . , V /dm ).

3. The matrix is
2 0 0 0
⎛ ⎞
⎜0 4 0 0 ⎟
⎠.
0 0 8 0
⎝
0 0 0 16

This is a diagonal game of value V = (1/2 + 1/4 + 1/8 + 1/16)−1 = 16/15 . The optimal
strategy for both players is (8/15, 4/15, 2/15, 1/15).

4. The matrix is
1 0 0 0
⎛ ⎞
⎜ 1/2 1 0 0⎟
⎠.
1/2 1/2 1 0
⎝
1/2 1/2 1/2 1

This is a triangular game. If V is the value and if (p1 , p2 , p3 , p4 ) is Player I’s optimal
strategy, then equations (12) become V = p4 = p3 + (1/2)p4 = p2 + (1/2)(p3 + p4 ) =
p1 + (1/2)(p2 + p3 + p4 ). We may solve the equations one at a time to find p4 = V ,
p3 = (1/2)V , p2 = (1/4)V and p1 = (1/8)V . Since the sum of the p’s is one, we find
( 81 + 14 + 21 + 1)V = 1 , so that V = 8/15 . This is the value and p = (1/15, 2/15, 4/15, 8/15)
is optimal for Player I and q = (8/15, 4/15, 2/15, 1/15) is optimal for II.

II – 5

Gedownload door remco dassen (remcodassen2@gmail.com)

 lOMoARcPSD|47086496

5. This is similar to Exercise 4. Equations (12) become:

pn = V
pn−1 − pn = V
pn−2 − pn−1 − pn = V
..
.
p1 − p2 − · · · − pn−2 − pn−1 − pn = V

The solution is pn = V , pn−1 = 2V ,. . . , p1 = 2n−1 V . Since 1 = p1 + p2 + · · · + pn =

[2n−1 + 2n−2 + · · · + 1]V = [2n − 1]V , we find that the value is V = 1/(2n − 1). The
optimal strategy for I (and for II also) is (2n−1 , 2n−2 , . . . , 2, 1)/(2n − 1).
6. The matrix A has components aij = 0 for i < j and aij = bi−j for i ≥ j . It is
easy to show that
1 0 0 ··· 0 1 0 0 ··· 0
⎛ ⎞⎛ ⎞
⎜ b 1 0 0 ⎟ ⎜ −b 1 0 0⎟
⎜ 2
⎜ b b 1 0 ⎟ ⎜ 0 −b 1 0⎟ = I
⎟⎜ ⎟
⎜ . . ⎟⎜ .
⎝ .. .. ... ⎠ ⎝ .. .. .. ⎟
. . ⎠
bn−1 bn−2 ··· b 1 0 0 ··· −b 1
Therefore, we may use Theorem 3.2 to find the value V as the reciprocal of the sum of
all the elements of A−1 , V = 1/(n − (n − 1)b), and I’s optimal strategy is proportional
to the sums of the columns of A−1 , p = (1 − b, 1 − b, . . . , 1 − b, 1)/(n − (n − 1)b), and II’s
optimal strategy is q = (1, 1 − b, 1 − b, . . . , 1 − b)/(n − (n − 1)b), proportional to the sums
of the rows of A−1 .
7. We may use Theorem 3.2 with A−1 n replaced by Bn . Since the sum of the ith
i−1 n−1 T
row of Bn is 2 (the binomial theorem), we have+Bn 1) = (1, * 2,)4, *. . . , 2 ) , and so
T n n k−1 n
1 Bn 1 = 2 − 1 . Similarly, the sum of column j is k=j j−1 = k (easily proved by
T
)n* )n* )n*
induction). So that 1 B = ( 1 , 2 , . . . , n ). From this we may conclude that the value
is V = 1/(2n − 1), the optimal strategy )of *Player
)n* I is)np* = (1, 2, . . . , 2n−1 )/(2n − 1), and
n n
the optimal strategy of Player II is q = ( 1 , 2 , . . . , n )/(2 − 1).
8.(a) Assuming all strategies active, the optimal strategy for I satisfies, p1 = V ,
−p1 + 2p2 = V and −p1 + p2 + 3p3 = V , from which we find p1 = V , p2 = V and
p3 = V /3 . Since 1 = p1 + p2 + p3 = V + V + (1/3)V = (7/3)V , we have V = 3/7 and
p = (p1 , p2 , p3 ) = (3/7, 3/7, 1/7). A similar analysis for Player II gives q = (q1 , q2 , q3 ) =
(5/7, 1/7, 1/7). Since p and q are nonnegative, these are the optimal strategies, and V
is the value.
(b) If we subtract 1 from all entries of the matrix, we end up with a diagonal game
with 1, 1/2, 1/3 and 1/4 along the diagonal. The value of that game is 1/10 , and the
optimal strategies for both players is (1/10, 2/10, 3/10, 4/10). The original game has value
11/10 and the same optimal strategies.
(c) The last column is dominated by the first, and the bottom row is dominated by
the mixture of row 1 and row 2 with probability 1/2 each. The resulting three by three

II – 6

Gedownload door remco dassen (remcodassen2@gmail.com)

 lOMoARcPSD|47086496

matrix is a diagonal game with value 1/[(1/2) + (1/3) + (1/4)] = 12/13 . The optimal
strategy for both players is (6/13, 4/13, 3/13, 0).
9.(a) The matrix is
0 −2 1 1 1 ...
⎛ ⎞
⎜ 2 0 −2 1 1 ...⎟
⎜ −1 2 0 −2 1
⎜ ⎟
⎟
⎝ −1 −1 2 0 −1
⎜ ⎟
⎠
.. .. ..
. . .

(b) The game is symmetric and has value zero (if it exists). If the first five rows and
columns are the active ones, the equations become
2p2 − p3 − p4 − p5 = 0
−2p1 + 2p3 − p4 − p5 = 0
p1 − 2p2 + 2p4 − p5 = 0
p1 + p2 − 2p3 + 2p5 = 0
p1 + p2 + p3 − 2p4 =0

If we interchange (p1 , p2 ) with (p5 , p4 ) in these equations, we get the same set of equa-
tions. So in the solution, we must have p1 = p5 and p2 = p4 . Using this, the top
two equations become p2 = p1 + p3 and 2p3 = 3p2 + p1 , which together with 2p1 +
2p2 + p3 = 1 gives p1 = p5 = 1/16 , p2 = p4 = 5/16 and p3 = 4/16 . If Player I uses
p = (1/16, 5/16, 4/16, 5/16, 1/16, 0, 0, . . .) on the game with general n , then Player II will
never use columns 6 or greater because the average payoff to Player I would be positive.
Thus, the value is zero and p is optimal for both players.
10. (a) The matrix is
1 2 3 4 5 6 ...
1 0 −1 2 2 2 2 ...
⎛ ⎞
2⎜ 1 0 −1 −1 −1 2 ...⎟
3 ⎜ −2 1 0 −1 −1 −1 ...⎟
⎜ ⎟
4 ⎜ −2 1 1 0 −1 −1 ...⎟
⎜ ⎟
5 ⎜ −2 1 1 1 0 −1 ...⎟
⎜ ⎟
6 ⎝ −2 −2 1 1 1 0 ...⎠
⎜ ⎟
.. .. .. .. .. .. ..
. . . . . . .

One can see that columns 6, 7, . . . are all dominated by column 1. Similarly for rows. This
reduces the game to a 5 by 5 matrix. Columns 3 and 4 are dominated by column 5. This
reduces the game to 3 by 3.
⎛ ⎞
0 −1 2
(b) The game restricted to rows and columns 1, 2 and 5 has matrix ⎝ 1 0 −1 ⎠ ,
−2 1 0
whose solution (see (25)) is (1/4, 1/2, 1/4). It is easy to check that the mixed strategy

II – 7

Gedownload door remco dassen (remcodassen2@gmail.com)

 lOMoARcPSD|47086496

(1/4, 1/2, 0, 0, 1/4, 0, . . .) gives Player I an average payoff of at least 0 for every pure strat-
egy of Player II. So this strategy is optimal for Player I, and by symmetry Player II as
well.
11.(a) The matrix is skew-symmetric so this is a symmetric game. So the value is 0.
To find an optimal strategy for I, we try (p1 , p2 , p3 ) against the columns. The first column
gives −p2 + 2p3 = 0 (since 0 is the value), and the second gives p1 − 3p3 − 0 . We have
p1 = 3p3 and p2 = 2p3 . Then since the probabilities sum to 1, we have 3p3 + 2p3 + p3 = 1
or p3 = 1/6 . Then, p1 = 1/2 and p2 = 1/3 . The optimal strategy for both players is
(1/2, 1/3, 1/6).
(b) This is a Latin square game, so (1/3, 1/3, 1/3) is optimal for both players and the
value is v = (0 + 1 − 2)/3 = −1/3 .
(c) (1/4)row 1 + (1/4)row 2 + (1/4)row 3 + (1/4)row 4 dominates row 5. After
removing row 5, the matrix is a Latin square. So (1/4, 1/4, 1/4, 1/4) is optimal for II, and
(1/4, 1/4, 1/4, 1/4, 0) is optimal for I. The value is v = (1 + 4 − 1 + 5)/4 = 9/4 .
12. The answer given by the Matrix Game Solver gives the same value and opti-
mal strategy for Player I as in the text, but gives the optimal strategy for Player II as
(7/90,32/90,48/90,3/90). This shows that although there may be a unique invariant op-
timal strategy, there may be other noninvariant optimal strategies as well. The simplex
method only finds basic feasible solutions, and so will not find the invariant optimal solu-
tion (1/18,4/9,4/9,1/18), because it is not basic.
In (15), the middle row is strictly dominated by (3/4) the top row plus (1/4) the
bottom row. Our solution and the one found by the Matrix Game Solver both give zero
weight to (3,1) and (1,3).
13. (a) The reduced matrix has a saddle point.
(1, 0)∗
(2, 0)∗
! "
1
(1, 1) 1

So the value is 1, (1, 1) (or (2, 0)∗ ) is optimal for Player I and (1, 0)∗ is optimal for Player
II.
(b) The reduced matrix is
(2, 0)∗ (1, 1)
∗
! "
(3, 0) 3/2 1/2
(2, 1)∗ 0 2

The value is 1. An optimal strategy for Player I is to use (3, 0)∗ with probability 2/3, and
(2, 1)∗ with probability 1/3. This corresponds to playing (3, 0) and (0, 3) with probability
1/3 each, and (2, 1) and (1, 2) with probability 1/6 each. An optimal strategy for Player
II is to use (1.1) with probability 1/2, and (2, 0) and (0, 2) with probability 1/4 each.
14. (a) In the matrix below, row 4 is dominated by (1/2)row 2 + (1/2)row 3. Then
col 2 is dominated by (1/2)col 1 + (1/2)col 3. Then row 2 is dominated by (2/3)row 1 +

II – 8

Gedownload door remco dassen (remcodassen2@gmail.com)

 lOMoARcPSD|47086496

(1/3)row 3.
(3, 0, 0)∗ (2, 1, 0)∗ (1, 1, 1)
(4, 0, 0)∗
⎛ ⎞
4/3 2/3 0
∗⎜
(3, 1, 0) ⎜ 1/3 1 1 ⎟
⎟
(2, 2, 0)∗ ⎝ −1 4/3 3 ⎠
(2, 1, 1)∗ −1/3 1/3 2
We find that (3/4,0,1/4,0) is optimal for Player I, (9/16,0,7/16) is optimal for Player II,
and the value is 3/4.
(b) In the matrix below, row 4 is dominated by (1/2)row 3 + (1/2)row 5. But we
might as well use the Matrix Game Solver directly.
(3, 0, 0, 0)∗ (2, 1, 0, 0)∗ (1, 1, 1, 0)
⎛ ⎞
(4, 0, 0, 0)∗ 1 1/4 −1/2
(3, 1, 0, 0)∗ ⎜
⎜ 1/2 3/4 1/2 ⎟ ⎟
(2, 2, 0, 0)∗ ⎜
⎜ −1/2 1 2 ⎟
⎟
∗⎝
(2, 2, 1, 1) 1/4 1/2 3/2 ⎠
(1, 1, 1, 1) 1 0 1
The value is 3/5, (0,4/5,0,0,1/5) is optimal for Player I, and (8/15,2/5,1/15) is optimal for
Player II.
15. Consider the following strategies for Player II.
A: Start at the center square; if this is a hit continue with a 2, 4, 6, or 8 in random
order each order equally likely; if this is a miss, shoot at the corners 1,3,7,9 in a random,
equally likely order, and when a hit occurs, choose one of the two possible middle edge
squares at random, then the other.
B: Start at the four middle edge squares, 2,4,6,8 in some random order; when a hit
occurs, try the center next, the the possible corner squares.
C: Start at the four middle edge squares, 2,4,6,8 in some random order; when a hit
occurs, try the possible corners next, then the center.
There are many other strategies for Player II, but they should be dominated by some
mixture of these. In particular, starting at a corner square should be dominated by starting
at a middle edge.
Using invariance, Player I has the two strategies, [1, 2]∗ and [2, 5]∗ . Suppose Player
I uses [1, 2]∗ and Player II uses C. Then the first hit will occur on shot 1, 2, 3, or 4 with
probability 1/4 each. After the first hit it takes on the average 1.5 more shots to get the
other hit. The average number of shots then is
(1/4)(2.5) + (1/4)(3.5) + (1/4)(4.5) + (1/4)(5.5) = 4.
But if Player II starts off by shooting in the center before trying the corners, it will take
one more shot on the average, namely 5. This gives the top row of the matrix below. The
whole matrix turns out to be
A B C
∗
! "
[1, 2] 5 5 4
[2, 5]∗ 3.5 3.5 5.5

II – 9

Gedownload door remco dassen (remcodassen2@gmail.com)

 lOMoARcPSD|47086496

The first two columns are equivalent. Player I’s optimal strategy is (2/3, 1/3). This
translates into choosing one of the 12 positions at random with probability 1/12 each.
One optimal strategy for Player II is to randomize with equal probability between B and
C. The value is 4.5.
16. Invariance reduces Player I to two strategies; choose 1 and 3 with probability 1/2
each, denoted by 1∗ , and choose 3. Similarly, invariance and dominance reduces Player II
to two strategies, we call A and B. For A, start with 2. For B, with probability 1/2, start
with 1 and if it’s not successful follow it with 3, and with probability 1/2 start with 3 if
it’s not successful and follow it with 1. This leads to a 2 by 2 game with matrix
A B
∗
! "
1 2 3/2
2 1 3

The value is 9/5 . An optimal strategy for I is to choose 2 with probability 1/5, and
1 or 3 equally likely with probability 2/5 each. An optimal strategy for II is guess 2 first
with probability 3/5, and otherwise to guess 1 then 3, or 3 then 1 with probability 1/5
each; that is, II never guesses 1 then 2 then 3 and never guesses 3 then 2 then 1.
17. To make Player I indifferent in choosing + among rows 1 through k , Player II will
choose q = (q1 , . . . , qk , 0, . . . , 0) so that ui i̸=j qj = Vk for i = 1, . . . , k for some constant
+k +k
Vk . Using 1 qj = 1 , this reduces to (1 − qi$ ) = Vk /ui . Since 1 (1 − qi ) = k − 1 , we have
k−1 1 − Vk /ui for i = 1, . . . , k
Vk = +k and qi = (1)
1/ui 0 for i = k + 1, . . . , m
1

The qi are nondecreasing but we must have qi ≥ 0 , which reduces to Vk ≤ uk . If k < m ,

we also require that Player I will not choose rows k + 1 to m . This reduces to uk+1 ≤ Vk .
Therefore, if uk+1 ≤ Vk ≤ uk , Player II can achieve Vk by using q . (It is easy to show
that V2 < u2 and that Vk ≤ uk implies that Vk−1 ≤ uk−1 . This shows that such a k
exists and is unique.)
To make Player II indifferent in choosing +k among columns 1 through k , Player I will
choose p = (p1 , . . . , pk , 0, . . . , 0) so that 1 pi ui − pj uj = Vk for some constant Vk and
j = 1, . . . , k . This shows that pj is equal to some constant over uj for j = 1, . . . , k . Using
+k
1 pj = 1 , we find ⎧
⎨ 1/uj
for j = 1, . . . , k
pj = +k 1/ui (2)
⎩ 1
0 for j = k + 1, . . . , m
Solving for Vk shows it indeed has the same value as above. All the pj are nonnegative,
so we only have to show that Player II will not want to choose columns
+k k + 1, . . . , m . The
expected payoff is the same for each of these columns, namely, 1 pi ui which is clearly
greater than Vk , so Player I can achieve at least Vk .
+k
In summary, find the largest k in {2, . . . , m} such that (k − 1)/uk ≤ 1 1/ui . Then
the value and the optimal strategies are given by (1) and (2).

II – 10

Gedownload door remco dassen (remcodassen2@gmail.com)

 lOMoARcPSD|47086496

18. The payoff matrix is An = (aij ), where

2 if i = j
1
aij = −1 if |i − j| = 1
0 otherwise.
It is straightforward to check that An Bn = In , so that A−1 n = Bn . The sum of the ith row
of A−1n is i(n + 1 − i)/2 . By symmetry these are also the column sums. Since they are all
positive the game is completely mixed, and the optimal strategy, the same for both players,
is proportional to (n, 2(n−1), 3(n−2), . . . , n), namely, p(i) = 6i(n+1−i)/(n(n+1)(n+2)).
The sum of all numbers in A−1 n is n(n + 1)(n + 2)/12 , so the value is its reciprocal,
vn = 12/(n(n + 1)(n + 2)).
19. (a) n odd: Let x = (1, 0, 1, 0, . . . , 1)T . Then xT A = (2, 2, . . . , 2). There are
(n + 1)/2 1’s in x , so p = 2x/(n + 1) is a mixed strategy for I that guarantees I will
win 4/(n + 1) no matter what column II chooses. The matrix is symmetric, so the same
strategy guarantees II will lose 4/(n + 1) no matter what I does. Thus, p is an optimal
strategy for both I and II, and 4/(n + 2) is the value.
(b) n even: Let k = n/2 and x = (k, 1, k − 1, 2, . . . , 1, k)T . Then xt A = (2k +
1, 2k + 1, . . . , 2k + 1). The sum of the elements of x is k(k + 1) so p = x/(k(k + 1))
is a mixed strategy for I that guarantees I will win (2k + 1)/(k(k + 1)) no matter what
column II chooses. The same strategy guarantees II will lose (2k + 1)/(k(k + 1)) no
matter what I does. Thus, p is an optimal strategy for both I and II, and the value is
v = (2k + 1)/(k(k + 1)) = 4(n + 1)/(n(n + 2)).

II – 11

Gedownload door remco dassen (remcodassen2@gmail.com)

 lOMoARcPSD|47086496

Solutions to Exercises of Section II.4.

1.(a) If Player II uses the mixed strategy, (1/5, 1/5, 1/5, 2/5), I’s expected payoff from
rows 1, 2, and 3 are 17/5, 17/5, and 23/5 respectively. So I’s Bayes strategy is row 3, giving
expected payoff 23/5.
(b) If II guesses correctly that I will use the Bayes strategy against (1/5, 1/5, 1/5, 2/5),
she should choose column 3, giving Player I a payoff of −1 .

2.(a) We have bij = 5 + 2aij for all i and j . Hence, A and B have the same optimal
strategies for the players, and the value of B is Val(B) = 5 + 2Val(A) = 5 . The optimal
strategy for I is (6/11, 3/11, 2/11).
(b) Since we are given that Val(A) = 0 , we may solve for the optimal q for II using
the equations, −q2 + q3 = 0 , and 2q1 − 2q3 = 0 . So q1 = q3 and q2 = q3 . Since the
probabilities sum to 1, all three must be equal to 1/3. So (1/3, 1/3, 1/3) is optimal for
Player II for both matrices A and B .
+n
3.(a) Let ϵ > 0 and let q be any element of Y ∗ . Then since j=1 qj → 1 as n → ∞ ,
+∞ +∞
we have j=n qj → 0 , so that there is an integer N such that j=N qj < ϵ. If Player
+∞ +N −1 +∞
I uses i = N , the expected payoff is L(N, j)qj = j=1 qj − j=N +1 qj < 1 − 2ϵ.
j=1 +
∞
Thus for every q ∈ Y ∗ , we have sup1≤i<∞ j=1 L(i, j)qj ≥ 1 − 2ϵ. Since this is true for
all ϵ > 0 , it is also true for ϵ = 0 .
+∞
(b) Since (a) is true for all q ∈ Y ∗ , we have V = inf q∈Y ∗ sup1≤i<∞ j=1 L(i, j)qj ≥ 1 .
Since no payoff is greater than 1, we have V = 1 .
(c) The game is symmetric, so V = −V . Hence, V = −1 .
(d) Any strategy is minimax for Player I since any strategy guarantees an expected
payoff of at least V = −1 .

4. The value of A is positive since the simple strategy (2/3)row 1 + (1/3)row 2

guarantees a positive return for Player⎛
I. But let’s add
⎞ 1 to A anyway to get B :
1 2 3
B = ⎝ 3 0 −1 ⎠ .
4 −2 1

The simplex tableau is displayed below on the left. We are asked to pivot in the second
column. But there is only one positive number there, so we must pivot on the first row
second column. We arrive at:
y1 y2 y3 y1 x1 y3
x1 1 ⃝ 2 3 1 y2 1/2 1/2 3/2 1/2
x2 3 0 −1 1 −→ x2 3 0 −1 1
x3 4 −2 1 1 x3 5 1 4 2
−1 −1 −1 0 −1/2 1/2 1/2 1/2

II – 12

Gedownload door remco dassen (remcodassen2@gmail.com)

 lOMoARcPSD|47086496

There is still a negative element on the bottom edge so we continue. It is unique and in
the first column, so we pivot in the first column. the smallest of the ratios is 1/3 occuring
in the second row. So we pivot on the second row first column to find:
y1 x1 y3 x2 x1 y3
y2 1/2 1/2 3/2 1/2 y2 −1/6 1/2 5/3 1/3
x2 ⃝3 0 −1 1 −→ y1 1/3 0 −1/3 1/3
x3 5 1 4 2 x3 −5/3 1 17/3 1/3
−1/2 1/2 1/2 1/2 1/6 1/2 1/3 2/3

From this we see that Val(B) = 3/2 , so that Val(A) = 1/2 . For either game (p1 , p2 , p3 ) =
(3/4, 1/4, 0) is optimal for Player I and (q1 , q2 , q3 ) = (1/2, 1/2, 0) is optimal for Player II.
You may use the sure-fire test to see that this is correct.

5. (a) For all j = 0, 1, 2, . . . ,

∞ j−1 ∞
2 2 1 i
2 1
pi A(i, j) = (i+1)
(−4 ) + (i+1)
(4j )
i=0 i=0
2 i=j+1
2
1 1 1 1
= − (1 + 2 + · · · + 2j−1 ) + 4j (j+2) (1 + + + · · ·)
2 2 2 4
1 j 1 j 1
= − (2 − 1) + 2 = .
2 2 2
++
(b) If both players use the mixed strategy, p , the payoff is pi A(i, j)pj . The trouble
is that the answer depends on the order of summation. If we sum over i first, we get
+1/2 , and if we sum over j first we get −1/2 .+In+other words, Fubini’s Theorem does
not hold here. For Fubini’s Theorem, we need pi |A(i, j)|pj < ∞ , which is not the
case here. The whole theory of using mixed strategies in games depends heavily on Utility
Theory. In Utility Theory, at least as presented in Appendix 1, the utility functions are
bounded. So it would seem most logical to restrict attention to games in which the payoff
function, A, is bounded. That is certainly one way to avoid such examples. However, in
many important problems the payoff function is unbounded, at least on one side, so one
usually assumes that the payoff function is bounded below, say.
There is another way of dealing with the problem that is more germane to the exam-
ple above, and that is by restricting the notion of a mixed strategy to be a probability
distribution that gives weight to only a finite number of pure strategies. (Then Fubini’s
theorem holds because the summations are finite.) If this is done in the example, then one
can easily see that the value of the game does not exist. This seems to be the “proper”
solution of the game because it is just a blown-up version of the game, “the-player-that-
chooses-the-larger-integer-wins”.

II – 13

Gedownload door remco dassen (remcodassen2@gmail.com)

 lOMoARcPSD|47086496

6. We take the initial i1 = 1 , and find

k ik sk (1) sk (2) Vk jk tk (1) tk (2) Vk

1 1 1 −1 −1 2 −1 2 2
2 2 1 1 .5 1 0 2 1
3 2 1 3 .3333 1 1 2 0.6667
4 2 1 5 0.25 1 2 2 .5
The largest of the Vk , namely .5 , is equal to the smallest of the Vk . So the value of the
game is 1/2. An optimal strategy for Player I is found at k = 2 to be p = (.5, .5). An
optimal strategy for Player II is q = (.75, .25) found at k = 4 . Don’t expect to find the
value of a game by this method again!
√
7. (a) The upper left payoff of 2 was chosen so that there would be no ties in
the fictitious play. So Player II knows exactly what Player I will do and will be able to
guarantee a zero payoff at each
√ future stage. If Player II’s relative frequency, qk , of column
1 by stage k goes above 1/( 2 + 1), Player I will play row 1, causing √ Player II to play
column 2, thus causing qk to decrease. Thus qk converges to 1/( 2 + 1), which in fact
is Player II’s optimal strategy
√ for the game. Similarly, Player I’s relative frequency, pk , of
row 1 converges to 1/( 2 + 1), which is his optimal strategy.
(b)√Player I should play the same pure strategy as his opponent at each stage, gaining
either 2 or 1 at each stage. The same argument√as in (a) shows that Player II’s average
relative frequency of column 2 converges to 1/( 2 + 1), so Player I’s limiting average
payoff is √
1 √ 2 √
√ · 2+ √ = 2(2 − 2),
2+1 2+1
twice the value of the game.

II – 14

Gedownload door remco dassen (remcodassen2@gmail.com)

 lOMoARcPSD|47086496

Solutions to Exercises of Section II.5.

1. The Silver Dollar. I hides the dollar, II searches for it with random success.
II

1 2
I

1 2 1 2
N N
0 0
find find
1/2 1/2 2/3 1/3

1 0 0 1

2. Two Guesses for the Silver Dollar. I hides the dollar, II searches for it twice
with random success.
II
1 2

1 2 1 2
N N
find 1/2 2/3 find
1/2 1/3
I I
1 1
1 2 1 2 1 2 1 2
N N N N
0 0 0 0
1/2 1/2 1/2 1/2 2/3 1/3 2/3 1/3

1 0 1 0 0 1 0 1

3. Guessing the Probability of a Coin. I chooses the fair (F) or biased (B) coin.
II observes H or T on one toss of the coin and must guess which coin.
I

F B
N N

1/2 1/2 1/3 2/3

II II

F B F B F B F B

0 1 0 1 1 0 1 0

II – 15

Gedownload door remco dassen (remcodassen2@gmail.com)

 lOMoARcPSD|47086496

4. A Forgetful Player. A fair coin is tossed. I hears the outcome and bets 1 or 2.
II guesses H or T. I forgets the toss and doubles or passes.
N

H 1/2 1/2 T
I I

1 2 1 2
II II

H T H T H T H T
I I
I I

d p d p d p d p d p d p d p d p

-4 -2 4 2 -6 -3 6 3 2 1 -2 -1 4 2 -4 -2

5. A One-Shot Game of Incomplete Information.

I

H T
N N
H T H T
1/2 1/2 1/3 2/3
II II

A B A B A B A B

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

There is an alternate Kuhn tree where the simultaneous move is replaced by Player
II moving first and then Player I moving, not knowing what move Player II made.
6. In Figure 2, replace 1/4 by p, 3/4 by 1 − p, and ±3 by ±(1 + b). Again one
can argue that Player I should bet with a winning card; he wins 1 if he checks, and wins
at least 1 if he bets. In other words, as in the analysis in the text of the resulting 4 × 2
matrix, the first row dominates the third row and the second row dominates the fourth
row. The top two rows of the matrix are
c f
! "
(b, b) (1 + b)(2p − 1) 1
(b, c) p(2 + b) − 1 2p − 1

If (2p − 1)(1 + b) ≥ 1 , (that is, if p ≥ (2 + b)/(2 + 2b)), there is a saddle-point in the

upper right corner. The value of the game is 1, Player I should always bet, and Player II
should always fold.

II – 16

Gedownload door remco dassen (remcodassen2@gmail.com)

 lOMoARcPSD|47086496

Otherwise, (if p < (2 + b)/(2 + 2b)), the game does not have a saddle-point and we
can use the straightforward method for solving two by two games. It is optimal for Player
I to choose row 1 with probability pb/((2 + b)(1 − p)), and row 2 otherwise. It is optimal
for Player II to choose column 1 with probability 2/(2 + b), and column 2 otherwise. The
value is (4p(1 + b) − (2 + b))/(2 + b).

7.(a) The strategic (normal) form is

(d, f) (d, g) (e, f) (e, g)
⎛ ⎞
a −1 −1 1 3
b ⎝ 1 0 1 2 ⎠
c 1 1 −1 1

(b) Column 2 dominates

! columns
" 1 and 4. Then row 2 dominates row 1. The resulting
0 1
two by two matrix is , with value 1/3. The optimal mixed strategy for Player
1 −1
I is (0, 2/3, 1/3). The optimal mixed strategy for Player 2 is (0, 2/3, 1/3, 0).

8.(a) The strategic (normal) form is

(a, c) (a, d) (b, c) (b, d)
⎛ ⎞
(A, C) 1 1 0 0
(A, D) ⎜ 0
⎜ 2 1 3 ⎟ ⎟
(B, C) ⎝ 3/2 1/2 −1/2 −3/2 ⎠
(B, D) 1/2 3/2 1/2 3/2

(b) Column 3 dominates column 2. The mixture, (2/3)row 2 + (1/3)row 3, dominates

row 4. The!mixture, (1/3)row 2 "+ (2/3)row 3, dominates row 1. The resulting two by three
0 1 3
matrix is . The first two columns of this matrix are active. The
3/2 −1/2 −3/2
value is 1/2 . An optimal mixed strategy for Player I in the original game is (0, 2/3, 1/3, 0).
An optimal mixed strategy for Player II is (1/2, 0, 1/2, 0). It is interesting to note that
Player I also has an optimal pure strategy, namely row 4.

II – 17

Gedownload door remco dassen (remcodassen2@gmail.com)

 lOMoARcPSD|47086496

9. (a) I

H T
N N
H T H T
1/2 1/2 1/3 2/3
II II

A B A B A B A B

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

AA AB BA BB
! "
H −1 −1/2 1/2 1
(b) The matrix is .
T 4/3 1 −2/3 −1
(c) Optimal for I = (4/7, 3/7). Optimal for II = (1/3, 0, 2/3, 0). Value = 0 .

1 2
! "
1 1/2 0
10. (a) The matrix is . The mixed strategy (2/5, 3/5) is optimal for
2 0 1/3
both I and II. The value is 1/5.
1 2
⎛⎞
11 3/4 0
12 ⎜
⎜ 1/2 1/3 ⎟ . An optimal strategy for I is (0, 0, 10/13, 3/13).
⎟
(b) The matrix is
21 ⎝ 1/2 1/3 ⎠
22 0 5/9
The optimal strategy for II is (4/13, 9/13). The value is 5/13.
F F F B BF BB
! "
F 0 1/2 1/2 1
(c) The matrix is . Optimal for I is (4/7, 3/7). Optimal
B 1 1/3 2/3 0
for II is (1/7, 6/7, 0, 0). The value is 3/7.
(d) The matrix is 64 by 4, much too large write out by hand. However, simple
arguments show that most of Player I’s pure strategies are dominated. First some notation.
We denote Player I’s pure strategies by a six-tuple, ab; wxyz , where a and b are 1 or 2
(the amount bet) for information sets I1 and I2 respectively, and and each of w , x, y
and z are p or d (pass or double) for information sets I3 , I4 , I5 and I6 respectively.
Thus, for example, 12; pdpp represents the strategy: Bet 1 with heads and 2 with tails;
his partner passes unless 1 is bet and Player II guesses heads, in which case he doubles.
If Player I uses a strategy starting 12 , then his partner upon hearing a bet of 1 and a
guess of heads should pass rather than double since that means a loss of 2 rather than 4.

II – 18

Gedownload door remco dassen (remcodassen2@gmail.com)

 lOMoARcPSD|47086496

Similarly, on hearing a bet of 1 and a guess of tails, his partner should double. Continuing
in this way, we see that the strategy 12; pddp dominates all strategies beginning 12.
Similarly, we may see that the strategy 21; dppd dominates all strategies beginning 21,
the strategy 11; pdxx (where x stands for “any”) dominates all strategies beginning 11,
and 22; xxpd dominates all strategies beginning 22. Thus, dominance reduces the game
to the following 4 by 4 matrix.
HH HT TH TT
⎛ ⎞
11; pdxx −1/2 −1/2 1 1
12; pddp ⎜
⎜ 1 −2 4 1 ⎟⎟
21; dppd ⎝ −1/2 4 −2 5/2 ⎠
22; xxpd −1/2 1 −1/2 1

Now, we can see that col 1 dominates col 4. Moreover an equiprobable mixture of rows 2
and 3 dominate rows 1 and 4. This reduces the game to a 2 by 3 matrix which is easily
solvable. For the above matrix, (0,3/5,2/5,0) is optimal for I, (4/5,1/5,0,0) is optimal for
II and the value is 2/5.
We can describe Player I’s strategy as follows. 60% of the time, Player I bets low on
heads and high on tails, and his partner doubles when Player II is wrong. The other 40%
of the time, Player I bets high on heads and low on tails, and his partner doubles when
Player II is wrong.
1 2
⎛ ⎞
11 4 0
12 ⎜
⎜ 2 4 ⎟ . An optimal strategy for I is (1/3, 2/3, 0, 0). An
⎟
(e) The matrix is
12 2 0 ⎠
⎝
22 0 4
optimal strategy for II is (2/3, 1/3). The value is 8/3.

11. Suppose Player I uses f with probability p1 and c with probability p2 (and so
g with probability 1 − p1 and d with probability 1 − p2 ). Suppose Player II uses a with
probability q (and b with probability 1 − q ). The average payoff is then
v = q(p1 − (1 − p1 )(1 − p2 )) + (1 − q)(−p1 p2 + 2(1 − p1 ))
= q(4p1 + p2 − 3) + 2 − 2p1 − p1 p2 .

Therefore, Player II will choose q = 0 if 4p1 + p2 ≥ 3 , and q = 1 if 4p1 + p2 < 3 . Against

this, the best Player I can do is to use p1 = 1/2 and p2 = 1 (or p1 = 3/4 and p2 = 0 )
giving an average payoff of 1/2. If q is announced, then Player I will use p1 = 1 and
p2 = 0 if q ≥ 2/3 , and p1 = 0 and p2 = 1 if q < 2/3 . Against this, the best Player II can
do is q = 2/3 , which gives Player I an average payoff of 2/3 . Therefore, the value of the
game does not exist if behavioral strategies must be used.

II – 19

Gedownload door remco dassen (remcodassen2@gmail.com)

 lOMoARcPSD|47086496

12. (a) N
face card
3/13 10/13

I I
5 1
5

II II

d c d c d

10 5 –10 5 –2

c d
! "
5 5 −70/13
(b) The matrix is .
1 −5/13 10/13
(c) The strategy (1/10, 9/10) is optimal for I, (8/15, 7/15) is optimal for II and the
value is 2/13.

II – 20

Gedownload door remco dassen (remcodassen2@gmail.com)

 lOMoARcPSD|47086496

Solutions to Exercises of Section II.6.

1. (a) G1 has a saddle point. The value is 3 , the pure strategy (1, 0) is optimal for
I, and (0, 1) is optimal for II.
The value of G2 is 3 , the strategy (.4, .6) is optimal for I, and (.5, .5) is optimal for II.
The value of G3 is −1 , the strategy (.5, .5) is optimal for
! I and"for II.
0 3
The game G is thus equivalent to a game with matrix .
3 −1
Hence, the value of G is 9/7 , and the strategy (4/7, 3/7) is optimal for both players.
(b1)
! Interchanging
" the second
! and" third columns, ! we " have a matrix of the form
0 G1 6 2 5 2
G = , where G1 = and G2 = . Since Val(G1 ) = 4 and
G2 0 3 5 1 4
Val(G2 ) = 3 , we find Val(G) = 12/7 .
! " ! "
G1 2 6 3
(b2) The matrix has the form, G = , where G2 = and G1 =
⎛ ⎞ 1 G2 4 7
3 1 5 ! " ! "
⎝1 3 5⎠ = G 3 5 3 1
, where G3 = . Since Val(G3 ) = 2 , we have Val(G1 ) =
4 1 1 3
4 4 1
3 , and then since Val(G2 ) = 5 , we have Val(G) = 13/6 .

2. The games Gm,n are defined by the induction

act wait
! "
inspect 1 Gm−1,n−1
Gm,n = for n = m + 1, m + 2, . . . and m = 1, 2, . . .
wait 0 Gm,n−1

with boundary conditions G0,n = (0). Let Vm,n = Value(Gm,n ). We have Vm,n = 1
for m ≥ n and V0,n = 0 for n ≥ 1 . Also from the Example given in the text, we have
V1,n = 1/n . We compute the! next few
" values, ! "
1 1/2 2 1 1/3 2
V2,3 = Value = V2,4 = Value =
0 1 3 0 2/3 4

and perhaps a few more, and then we conjecture Vm,n = m/n for 0 ≤ m ≤ n . Let us
check this conjecture by induction. It is true for m = 0 and for m = n . Suppose that
0 < m < n and suppose the conjecture is ! true for all smaller
" values. Then,
1 Vm−1,n−1
Vm,n = Value
0 Vm,n−1
! "
1 (m − 1)/(n − 1)
= Value
0 m/(n − 1)
m
= .
n
and the conjecture is verified. The optimal strategy for I in Gm,n is the mixed strategy
(m/n, (n − m)/n), and the optimal strategy for II is (1/n, (n − 1/n). It is interesting to

II – 21

Gedownload door remco dassen (remcodassen2@gmail.com)

 lOMoARcPSD|47086496

note that to play optimally player II does not need to keep track of how many times I has
searched for him.

3. The induction is
1 2
! "
1 Gn−1 0
Gn = for n = 2, 3, . . .
2 0 Gn−2
and boundary conditions G0 = (1) and G1 = (1). Let Vn = Value(Gn ). The recursion
for the Vn becomes ! "
Vn−1 0 Vn−1 Vn−2
Vn = Value = for n = 2, 3, . . .
0 Vn−2 Vn−1 + Vn−2
with boundary conditions V0 = 1 and V1 = 1 . Taking reciprocals of this equation, we find
1 1 1
= + for n = 2, 3, . . .
Vn Vn−1 Vn−2
This is the recursion for the Fibonacci sequence. Since 1/V0 = F0 and 1/V1 = F1 , we
must have 1/Vn = Fn . Hence we have Vn = 1/Fn for all n and we may compute the
optimal strategy for I and II to be (Fn−1 /Fn , Fn−2 /Fn ) for n = 2, 3, . . . .

4. Use of the first row implies vn ≥ n + 2 . Use of the first column implies vn ≤ n + 3 .
Since n + 2 ≤ vn ≤ n + 3 , none! of the games "have saddle points. So for n = 0, 1, . . . ,
n+3 n+2 2
vn = Val =n+3− .
n + 1 vn+1 vn+1 − n
Let wn = vn − n + 1 for n = 0, 1, . . . . Then the wn satisfy
2
wn = 4 − .
wn+1
′
In fact, the wn are the values of the
! games G"n where
3 2
G′n = 1 + ′ for n = 0, 1, . . .
1 Gn+1
In game G′n , I receives 1 from II and then the players choose row and column; if the players
choose the second row second column, then I receives 1 from II and they next play G′n+1 .
It may be seen that each of the games G′n has the same structure. It is as if the players
were playing the recursive game G′ where ! "
′ 3 2
G =1+ .
1 G′
So all the games G′n should have the same values. If so, denoting the common value by
w , we would have w = 4 − (2/w), or w2√− 4w + 2 = 0 . This has a unique solution √ in
the interval 3 ≤ w ≤ 4 , namely w = 2 + 2 . From this we have vn = n + 1 + 2 . The
optimal3strategies are the4same for all games, namely,
√
1+ 2 1
√ , √ = (.707 · · · , .293 · · ·) is optimal for I for all games Gn
2+ 2 2+ 2
3 √ 4
2 2
√ , √ = (.414 · · · , .586 · · ·) is optimal for II for all games Gn .
2+ 2 2+ 2

II – 22

Gedownload door remco dassen (remcodassen2@gmail.com)

 lOMoARcPSD|47086496

5. The game matrix !

of G1,n reduces to
n n n
"
1 − n+1 Vn−1,1 n+1 − n+1 Vn−1,1
.
0 1

(a) So Player I’s optimal strategy uses odds 1 : 1/(n + 1) = n + 1 : 1 ; i.e, he should bluff
with probability 1/(n + 2).
1 n n
(b) Player II’s optimal odds are n+1 + n+1 Vn−1,1 : 1 − n+1 Vn−1,1 = 1 + nVn−1,1 : n + 1 −
nVn−1,1 ; i.e., she should call with probability (n + 1 − nVn−1,1 )/(n + 2) = V1,n .

6. (a) If Q ≥ 2 , the top row forever is optimal for I, the second column is optimal
for II, and the value is v = 2 . If 0 ≤ Q ≤ 2 , the top row forever is optimal for I, the first
column forever is optimal for II, and the value is v = Q. If Q ≤ 0 , the bottom row is
optimal for I, the first column forever is optimal for II, and the value is v = 0 .
(b) If Q ≥ 1 , the value is v = 1 , (1, 0, 0)∞ (i.e. the top row forever) is optimal for I, and
(0, 1/2, 1/2)∞ is optimal for II. If Q ≤ 1 , the value is still v = 1 , (1, 0, 0)∞ is optimal for
II, and (1 − ϵ, ϵ/2, ϵ/2)∞ is ϵ-optimal for I (actually ϵ/(2 − ϵ)-optimal)

7. Since in game G3 , I can choose the second row and II can choose the second
column,! we have
" 0 ≤ v3 ≤ 1 . But since v3 ≤ 1 , the most that I can hope to achieve in G2
1 0
is Val = 2/3 , so we have 0 ≤ v2 ≤ 2/3 . Similarly, 1/2 ≤ v1 ≤ 1 . So none of the
0 2
game matrices have saddle points and we can write
1 2v3 1
v1 = v2 = v3 = .
2 − v2 2 + v3 2 − v1

Substitution of the first equation into the third and then the result into the second yields
2
the quadratic
√ equation, v2 = (4 − 2v2 )/(8 − 5v2 ), or 5v2 − 10v2 + 4 = 0 . Solving
√this gives
v2 = (5 −√ 5)/5 as the root less than 1 . From this we can find v1 = (5 − 5)/4 and
v3 = 3 − 5 . The complete solution √ is
G1 : Val(G1 ) = v1 = (5 − 5)/5 = .691 · · ·
Optimal for I = Optimal for II = (v1 , 1 − v1 ) = (.691 · · · , .309 · · ·)

√
G2 : Val(G2 ) = v2 = (5 − 5)/5 = .553 · · ·
√ √
5+ 5 5− 5
Optimal for I = Optimal for II = ( , ) = (.724 · · · , .276 · · ·)
10 10

√
G3 : Val(G3 ) = v3 = 3 − 5 = .764 · · ·
Optimal for I = Optimal for II = (v3 , 1 − v3 ) = (.764 · · · , .236 · · ·)

independent of Q.

8. Whatever the values of G1 , G2 and G3 , the game G1 is a latin square game

and so has optimal strategies (1/3, 1/3, 1/3) for both players. So we must have v1 =

II – 23

Gedownload door remco dassen (remcodassen2@gmail.com)

 lOMoARcPSD|47086496

(v1 + v2 + v3 )/3 , or equivalently 2v1 = v2 + v3 . From the form of G2 and G3 , we see that
0 ≤ v2 ≤ 2 and 0 ≤ v3 ≤ 1 . Hence, 0 ≤ v1 ≤ 3/2 . We now see that G2 does not have
a saddle point, and that 0 ≤ v2 < 1 so that G3 does not have a saddle point either. We
arrive at the three equations,
2v1 1
2v1 = v2 + v3 v2 = v3 = .
2 + v1 2 − v2
2
Eliminating v1 and v3 leads to a quadratic
√ equation for v2 , namely v2 + 2v2√− 1 = 0 .
This has one positive
√ root, namely v2 = 2 − 1 . From this we can find v1 = (4 2 − 2)/7
and v3 = (3 + 2)/7 . The complete √ solution is
G1 : Val(G1 ) = v1 = (4 2 − 2)/7 = .522 · · ·
Optimal for I = Optimal for II = (1/3, 1/3, 1/3)

√
G2 : Val(G2 ) = v2 = 2 − 1 = .414 · · ·
Optimal for I = Optimal for II = (.793 · · · , .207 · · ·)

√
G3 : Val(G3 ) = v3 = (3 + 2)/7 = .631 · · ·
Optimal for I = Optimal for II = (v3 , 1 − v3 ) = (.631 · · · , .369 · · ·)

independent of Q.

9. This is a recursive game!of the form

.8 + .2(−GT ) .5 + .5(−GT )
"
G=
.6 + .4(−GT ) .7 + .3(−GT )

and the value, v , of the game satisfies! "

.8 − .2v .5 − .5v
v = Val
.6 − .4v .7 − .3v

The game is in favor of the server, so the value is between zero and one and the game does
not have a saddle point. The optimal strategy for the server is to serve (high,low) with
probabilities proportional to (.1+.1v, .3+.3v), namely (1/4, 3/4). The optimal strategy for
the receiver is to receive (near,far) with probabilitites proportional to (.2 + .2v, .2 + .2v),
namely, (1/2, 1/2). Using the second of these equalizing strategies, the value may be
found to be v = (1/2)(.8 − .2v) + (1/2)(.5 − .5v) = .65 − .35v . Solving for v gives
v = 13/27 = .481 · · · .

10. (a) We may think of the basic game, G, as the one in which player I chooses
a number k to be the number of times he tosses the coin before challenging II. In this,
player II has no choice and the matrix G is an ∞ × 1 matrix, which is to say an infinite
dimensional column vector. The probability of tossing k heads in a row is pk . Counting
1 for a win and −1 for a loss, the expected payoff given that I tosses k heads in a row is
pk (−1)+ (1 − pk ) = 1 − 2pk . Thus the k th component of G is pk (1 − 2pk )+ (1 − pk )(−GT ).

II – 24

Gedownload door remco dassen (remcodassen2@gmail.com)

 lOMoARcPSD|47086496

Whatever the value v = Val(G), Player I will choose k to maximize this. We have the
equation
v = max(pk (1 − 2pk ) + (1 − pk )(−v)).
k

Clearly v > 0 , so there is a finite integer k at which the maximum is taken on, call it k0 .
Then v = pk0 (1 − 2pk0 )/(2 − pk0 ) and since! kv takes on "its maximum value at k0 , we have
p (1 − 2pk )
v = max .
k 2 − pk

When p = .5 , evaluating pk (1−2pk )/(2−pk ) at k = 1, 2, 3, 4, . . . gives 0 , 1/14 = .0714 · · · ,

1/20 = .05 , 7/248 = .0282 · · · , and so on, with a clear maximum at k = 2 .
(b) For arbitrary p, there is a maximum value attainable by v . Replace pk by y
in the formula for v and write it as f(y) = y(1 − 2y)/(2 − y). Calculus gives f ′ (y) =
(2y 2 − 8y + 2)/(2 − y)2 , so the function f(y) has a unique maximum on the interval (0,1) √
attained when y 2 −4y +1 = 0 . The root of this√ equation√in the interval (0,1) is y = 2− 3,
and the value attained there is V ∗ = f(2 − 3)√ = 7 − 4 3 = .0718 · · · . This is quite close
to .0714 · · · attainable when p = .5 . If p = 2 − 3, then V ∗ is attainable √ with k = 1 . As
p → ∞ , it becomes easier and easier to choose k so that pk is close to 2 − 3 so the value
converges to V ∗ .

11. The first row shows the value is at least 1, and the first column shows the value
is at most 4. So 1 ≤ v ≤ 4 . Then we see by “down-up-down-up” that the game does not
have a saddle-point, so ! "
4 1 + (v/3) 4 + (8v/3)
v = Val = .
0 1 + (2v/3) 4 + (v/3)

This leads to the quadratic equation, v 2 + 4v − 12 = 0 , which has solutions

! v = −2 ±"4.
4 1 + (2/3)
Since v is positive, we have v = 2 as the value. The matrix becomes .
0 1 + (4/3)
Player I’s stationary optimal strategy is (1/2, 1/2), and Player II’s stationary optimal
strategy is (1/7, 6/7).

12. We have
! " ! "
2 2 + (v(2)/2) −4 0
v(1) = Val v(2) = Val .
0 4 + (v(2)/2) −2 + (v(1)/2) −4 + (v(1)/2)

It may be difficult to guess that the matrices do not have saddle-points, so let us assume
they do not and check later to see if this assumption is correct. If neither matrix has a
saddle-point, then the equations become,
8 + v(2) 16 − 2v(1)
v(1) = v(2) = .
4 −6

Solving these equations simultaneously, we find v(1) = 16/11 and v(2) = −24/11 . With
these values the matrices above become

II – 25

Gedownload door remco dassen (remcodassen2@gmail.com)

 lOMoARcPSD|47086496

! " ! "
2 2 − (12/11) −4 0
.
0 4 − (12/11) −2 + (8/11) −4 + (8/11)
Since these do not have saddle-points, our assumption is valid and v(1) = 16/11 and
v(2) = −24/11 are the values. In G(1) , the optimal stationary strategies are (8/11, 3/11)
for I and (1/2, 1/2) for II. In G(2) , the optimal stationary strategies are (1/3, 2/3) for I
and (6/11, 5/11) for II.

II – 26

Gedownload door remco dassen (remcodassen2@gmail.com)

 lOMoARcPSD|47086496

Solutions to Exercises of Section II.7.

1. (a) The value is 0. Player II has a pure optimal strategy, namely y = 0 , since
A(x, 0) = 0 for all x ∈ X . Player I’s optimal strategy is 1 and −1 with equal probability
1/2, since if q ∈ YF∗ , 2 2
A(1/2, q) = (1/2) jqj − (1/2) jqj = 0
j j

because the sums are finite.

$
−k
(b) If qj = (1/4)(1/|j|) for |j| = 2 for some k ≥ 2 , then j qj = 1 and
+
0 otherwise
1 1 1 1 1 1
A(x, q) = (· · · − − − ) + ( + + + · · ·) = −∞ + ∞.
4 4 4 4 4 4

2. It is easier to use Method 2. The value occurs at the intersection of the curve
y2 = e−y1 and the line y1 = y2 , namely, it is the solution of the equation v = e−v . This
is about v = .5671 . The optimal strategy for II is y = v . The slope of the tangent line
to the curve y2 = e−y1 at the point y1 = v is −e−v = −v . The normal to this is the
negative of the reciprocal, namely 1/v . The optimal strategy of Player I takes x1 and x2
in proportions v : 1 . This is the mixed strategy (v/(1 + v), 1/(1 + v)) = (.3619, .6381).

3. The value occurs where the curve (y1 − 3)2 + 4(y2 − 2)2 = 4 is first hit by the line
y1 = y2 . Thus it satisfies the equation (v − 3)2 + 4(v − 2)2 = 4 with v < 2 . This leads to
the equation, v 5 − 22v + 21 = 0 , or (5v − 7)(v − 3) = 0 , so v = 7/5 is the value. Player II’s
optimal pure strategy is (v, v). The slope of the curve (y1 − 3)2 + 4(y2 − 2)2 = 4 at the
point (v, v) is y2′ = −(y 1 −3)
4(y2−2)
= −(v−3)
4(v−2)
. The normal is 4(2−v)
(3−v)
= 23 . So Player I’s optimal
strategy is (2/5, 3/5).

4. (a) For the upper semi-continuous payoff, the value is 1/2. An optimal strategy for
Player I is to choose 0 and 1 with probability 1/2 each. For any 0 < ϵ < 1/6 , an optimal
strategy for Player II is choose 1/3 − ϵ and 2/3 + ϵ with probability 1/2 each.
(b) For the lower semi-continuous payoff, the value is 1/2. An optimal strategy for
Player II is to choose 1/3 and 2/3 with probability 1/2 each. Player I also has an optimal
strategy. It is the same as above, namely, to choose 0 and 1 with probability 1/2 each.

5. This is essentially the game, He-who-chooses-the-smaller-positive-number-wins.

6. The game is symmetric, so if the value, if it exists, is zero and the players have
identical optimal strategies. The pure strategy x = 1 for Player I dominates the pure
strategies x such that 0 ≤ x ≤ 1 − 2b. Similarly for Player II. The game, played on the
remaining square, [1 − 2b, 1]2 , is a latin square game of the form of Example 1 of Section

II – 27

Gedownload door remco dassen (remcodassen2@gmail.com)

 lOMoARcPSD|47086496

7.2. So the optimal strategy for both players is the uniform distribution on the interval
[1 − 2b, 1] , and the value is zero. If b = 0 , the optimal strategies are the pure strategies,
x = 1 and y = 1 .

7. (a) The upper envelope is max{A(0, y), A(1, y)} = max{y 2 , 2(1 − y)2 } . This has a
minimum√when y 2 = 2(1 − y)2 . This reduces to y 2 − 4y + 2 = 0 whose solution in [0, 1] is
y0 = 2 − 2 = .586 · · · . The slope of A(0,√
y) and
√ that of A(1, y) at y = y0 is proportional
to 2y0 : −4 + 2y0 which reduces to 2 − √ 2 : 2 . So √ Player I’s optimal strategy is mix
x = 0 and x = 1 with probabilities (2 − 2)/2 and 2/2 , respectively. Numerically this
is (.293 · · · , .707 · · ·).
(b) This is a convex-concave game so both player have optimal pure strategies. If y0
is an optimal pure strategy for Player II, then x0 must maximize A(x, y0 ). As a function
of x this is a line of slope e−y0 − y0 . ⎧
So
⎨0 if e−y0 < y0
x0 = any if e−y0 = y0
1 if e−y0 > y0
⎩

We are bound to have a solution to this equation if e−y0 = y0 . So y0 = .5671 · · · . But

y must minimize A(x0 , y), whose derivative, −x0 e−y + 1 − x0 must be zero at y0 . This
gives x0 (e−y0 + 1) = 1 . Since e−y0 = y0 , we have x0 = 1/(1 + y0 ) = .6381 · · · .

8. (a) The payoff is convex in y for every y , so Player II has an optimal pure strategy.
Player I will hide in one of the three corners to make it as hard as possible for Player II
to come close. Therefore Player II will choose the point equidistant from (−1, 0), (1, 0),
and (0, 2). This will be the point (0, a) such that the distance from (0, a) to (1, 0) is
equal to the distance from (0, a) to (0, 2). This gives 1 + a2 = (2 − a)2 , or a = 3/4 .
So II’s optimal strategy is y = (0, 3/4), and the value of the game is (2 − a)2 = 25/26 .
By symmetry, I’s optimal strategy gives equal probability, say p, to (−1, 0) and (1, 0)
and probability 1 − 2p to (0, 2), such that p(−1, 0) + p(1, 0) + (1 − 2p)(0, 2) = (0, 3/4).
This gives p = 5/16 . Player I gives probability 5/16 to each of (−1, 0) and (1, 0) and
probability 6/16 to (0, 2).
(b) Find the smallest sphere, {y : ∥y − y0 ∥2 ≤ r2 } containing S . Then, r2 is the
value, and Player II has the optimal pure strategy y0 . Let X0 = {x ∈ S : ∥x−y0 ∥2 = r2 } .
Then, there exist x1 , . . . , xk in X0 (for some k ≤ n+1 ) and probabilities p1 , . . . , pk adding
+k
to one, such that 1 pi xi = y0 . An optimal mixed strategy for Player I is to choose xi
with probability pi .

9. Let us assume that the “good” strategies are those that give all mass to some
interval, [a, b] , with 0 < a < 1 < b, and let us search for a strategy F5 with a density f(x)
y
for which A(F, G) is constant over good strategies, G. Let Φ(y) = a xf(x) dx. Then
6 b6 y 6 b
A(F, G) = (y + x)f(x) dx dG(y) − 1 = [yF (y) + Φ(y)] dG(y) − 1 (2)
a a a
5b 5b
Since a dG(y) = 1 and a y dG(y) = 1 , the payoff (2) will be constant for all good G,
provided yF (y)+Φ(y) is linear in y ∈ (a, b), for some α . This means the second derivative

II – 28

Gedownload door remco dassen (remcodassen2@gmail.com)

 lOMoARcPSD|47086496

of yF (y) + Φ(y) must be zero:

3yf(y) + 2f ′ (y) = 0 (3)

whose solution is
f(y) = cy −3/2 for y ∈ (a, b), (4)
for some constant c > 0 . We have
F (y) = 2c[a−1/2 − y −1/2 ] and Φ(y) = 2c[y 1/2 − a1/2 ] for a < y < b (5)

For f to be a density, the constant c must satisfy

1 1
2c( √ − √ ) = 1. (6)
a b

For E(X) = 1 , we must have √ √

2c( b − a) = 1. (7)
√
We see from (6) and (7) that b = 1/a, and c = b/(2(b − 1)). Therefore from (5),
2c b 1
yF (y) + Φ(y) = √ (y − a) = (y − ) (8)
a b−1 b

The value of this game is√zero. The distribution with density

f(y) = b/(2(b − 1))y −3/2 for 1/b < y < b (9)

is an optimal pure strategy for both players.

Proof. Suppose Player I uses f(x) of (9). Since there can be no ties, we must show that if
Player II uses any distribution function G(y) on [0, b] having mean 1, then E((Y +X)I(X <
Y )) ≥ 1 . But,
6 b 6 y 6 b
E((Y + X)I(X < Y )) = (y + x)f(x) dx dG(y) = [yF (y) + Φ(y)] dG(y)
1/b 1/b 1/b
b
b 1
6
= (y − ) dG(y)
1/b b−1 b
b
b 1 b 1
6
≥ (y − ) dG(y) = (1 − ) = 1
0 b−1 b b−1 b

This also shows that if Player II puts any mass below 1/b, then Player I’s expected payoff
is positive.

10. The payoff function, B(u, v), is displayed in Figure 7.7.

51
This is a Latin Square type game with 0 B(u, v)du equal to the constant c for all
51
v , and similarly 0 B(u, v) dv = c for all u . Thus, the optimal mixed strategy for both
players is the uniform distribution on (0,1), and the value of the game is c = .60206 . . . .
This implies that in the original game the optimal strategy for I is to choose U from
a uniform distribution on (0,1) and let X = 10U , and similarly for II. The value is c .

II – 29

Gedownload door remco dassen (remcodassen2@gmail.com)

 lOMoARcPSD|47086496

c
1
0

1
c c
B(u, v)
0

0
0 c 1
Figure 7.7

It is interesting to note that if the payoff is changed so that Player I wins 1 if and
only if the first significant digit is in some set, such as {2, 4, 7, 8} , the optimal strategies
of the players remain the same. Only the value changes.

11. (a) I
bet check
II II

call fold call check

±(β+1) +1 ±1 0

(b) Indifference at a: c − (β + 1)(1 − c) = 0 · d − (1 − d).

Indifference at b: c + (β + 1)(b − c − (1 − b)) = 0 · d + (b − c − (1 − b)).
Indifference at c : (β + 1)(−a + 1 − b) = a + 1 − b.
Indifference at d : d − a − (b − d) = 0 .
Simplifying gives
d = (β + 2)c − β
d = β(1 + c − 2b)
β(1 − b) = (β + 2)a
d = (a + b)/2

(c) At β = 2 , I get a = 5/33 , b = 23/33 , c = 20/33 , and d = 14/33 .

The value is: v = (β +1)[(1−b)(b−c)−a(1−c)]+ac+(1−b)c−(1−b)(b−a)−(d−a)2 .
This turns out to be negative for all β > 0 . In particular for β = 2 , v = −2/33 ; the game
favors Player II.

II – 30

Gedownload door remco dassen (remcodassen2@gmail.com)

 lOMoARcPSD|47086496

12. It is optimal for Player I to play the points x0 = 0 and x1 = 0.7 , and for Player
II to play the points y0 = 0 and y1 = 0.5 (but any 0.4 < y1 < 0.6 works as well). This
leads to the following 2 by 2 game with matrix
y y1
! 0 "
x0 .00 .40
x1 .60 .24

Methods of Chapter 2.2 may be used to solve this game. The value is v = 6/19 . Player
I bets nothing with probability 9/19, and bets $70 with probability 10/19. Player II
bets nothing with probability 4/19, and $50 with probability 15/19. Player I wins with
probability v = .316 . . . .

II – 31

Gedownload door remco dassen (remcodassen2@gmail.com)