SOLUTION MANUAL
b
GameTheoryBasics1stEdition
b b b b b
ByBernhardvonStengel. Chapters1-12
b b b b b b b
1
, GT
1 -NimandCombinatorialGames
b b b b
2 -CongestionGames
b b
3 -GamesinStrategicForm
b b b b
4 -GameTreeswithPerfectInformation
b b b b b
5 - Expected Utility
b b
6 -MixedEquilibrium
b b
7 - Brouwer’s Fixed-Point Theorem
b b b
8 -Zero-SumGames
b b
9 -GeometryofEquilibriainBimatrixGames
b b b b b b
10 -GameTreeswithImperfectInformation
b b b b b
11 -Bargaining
b
12 -CorrelatedEquilibrium
b b
2
,Game Theory Basics b b
Solutions to Exercises b b
© Bernhard vonStengel2022
b b b b
Solution to Exercise 1.1 b b b
(a) Let≤ be defined by (1.7). To showthat ≤ is transitive, consider x, y, zwith x ≤ y and y ≤ z. If x =
b b b b b b b b b b b b b b b b b b b b b b b b b b
y thenx ≤z,andify =z then alsox ≤z.So theonlycaseleftis x < y and y < z,which implies x
b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b
< z because < is transitive, and hence x ≤ z.
b GT b GT b b b b b b
Clearly, ≤isreflexivebecause x = xandtherefore x ≤x. b b b b b b b b b b b b
Toshowthat ≤is antisymmetric,considerx and ywithx
b y andy≤ x. If we h≤ad x ≠ y then x
b b T bGT b b b b b b b b b G T b b b b b b b b
< y and y < x, and by transitivity x < x which contradicts (1.38). Hence x = y, as required. This shows
b b b b b b b b b b b b b b b b b b b b b b
that ≤is a partial order.
b b b b b b
Finally,weshow(1.6),so wehavetoshow thatx < y implies x yandx ≠ y≤ an d vice versa.Let x
b b b b b b b b b b b b b b G b b b b b b G T b b b b
<y, which implies x y by (1.7). If we had x = y≤t h e n x < x, contradicting(1.38),sowealsohavex
b b b b b b b b b b b b b b b b b b b b b b b
≠y. Conversely, x yandx ≠ yimplyby(1.7)x < y or x = y where≤the second case is excluded, h ence x <
b b b b b b b b b b b b b b b b b b GT b b b b b b b b
by, as required. b b
(b) Consider a partial order and≤ assume (1.6) as a definition of <. To show that < is transitive, su ppose
b b b b G T b b b b b b b b b b b b b b b
x < y, that is, x y and x ≠ y, and y <≤ z , that is, y z and y ≠ z. Because is tra≤
b b b b nsitive, x z. If we had xb b b b b b b b b b G T b b b b b b b b b b b b b b b b b
=≤ z then x
b GT y and y≤ x and hence x = y by antisym≤metry of ,≤which contradicts x ≠ y, so
G T b G b b G T G T G b b b b b b b b b b GT b b b b b
we have x z and x ≠ z, that is,x < z by (1.6), as required.
≤ ≤
b b b b b GTb b b b b b b b b b b
Also, < is irreflexive, because x < x would by definition mean x x and x ≠ ≤x , but the latter is n ot true.
b b b b b b b b b b b b G b b b b b b b b b b b b b
Finally,weshow(1.7), sowehavetoshowthatx ≤y implies x <yorx =y andvice versa, give n that< is
b b b b b b b b b b b b b b b b b b b b b b b b b b b b
definedby(1.6). Letx ≤y. Then if x =y, we aredone, otherwisex ≠y and thenbyd efinitionx <y.
b b b b b b b b b b b b b b b b b b b b b b b b b b b
bHence,x ≤y impliesx < yorx =y. Conversely,supposex < yorx =y. Ifx < y thenx ≤ y by (1.6),
b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b
and if x = y then x ≤ y because ≤isreflexive. Thiscompletes theproof. b b b b b b b b b b b b b b b b b
Solution to Exercise 1.2 b b b
(a) In analysing the games of three Nim heaps where one heap has size one, we first look at some e
b b b b b b b b b b b b b b b b GT b b
xamples, and then use mathematical induction to prove what we conjecture to be the losing positio ns. A
b b b b b b b b b b b b b b b b b b
losing position is one where every move is to a winning position, becausethen theoppon entwillwin.
b b b b b b b b b b b b b b b b b b b
Thepointofthisexerciseisto formulate aprecisestatement tobeproved,and the n to prove it.
b b b b b b b b b b b b b b b b b b b b
First, if there are only two heaps recall that they are losing if and only if the heaps are of equa l size. If
b b b b b b b b b b b b b b b b b b b b b b b
they are of unequal size, then the winning move is to reduce thelarger heap so that bo th heaps have
b b b b b b b b b b b b b b b b b b b b
equal size.
b b
3
, Consider three heaps of sizes 1, m, n, where 1 m ≤n . We≤observe the following: 1, 1, m is w
b b b b b b b b b T b GT b b b b b b b
inning, by moving to 1, 1, 0. Similarly, 1, m, m is winning, by moving to 0, m, m. Next, 1, 2, 3 i
b b b b b b b b b b b b b b GT b b b b b b b b
s losing(observed earlier inthe lecture), and hence1, 2, n for n 4 is winning. 1, 3, n is winnin gforany
b b b b b b b b b b b b b b b b b b b b b b b b
n 3 by moving to 1, 3, 2. For1, 4, 5,reducinganyheap produces awinningposition,
≥ ≥
b b b b b b b b b b b b b b b b b b b
so this is losing. b b b
Thegeneralpatternforthelosingpositions thus seems tobe: 1, m, m1, foreven+numbers m. This
b b b b b b b b b b b b b b b b GT b b
includes alsothe case m = 0, which we can take as the basecase foran induction. We now
b b b b b b b b b b GT b b b b b b b b
proceed toprovethis formally. b b b b
First we show that if the positions of the form 1, m, n with m b n are lo≤sing when m is even a b b b b b b b b b b b b b b b b b b b b
ndn =m1,thenthesea +r e theonlylosingpositionsbecauseanyotherposition1, m, n withm n is
b b b b b b b b b b b b b b b b b b b b b b b
winning. Namely, i f m = n then a winning move from1, m, m is to 0, m, m, so we can as
sume m < n. If m is even then n >≤
b b b G bTb b b b b b b b b b b b b b b b b b b
m 1 (otherwise we would be in the position 1, m, m 1)
+
b b b b b b b b b b b G b b b b b b b b b b
and so the winning move is to 1, m, m 1.If mis odd then the winning move is to 1, m, m 1, th
+ +
b b b b b b b b b b b b b b b b b b b b b b b b
esame as position 1, m 1, m (this would a l s o bea winning movefrom 1,m,m so there the winnin
b b b b b b b b b b b b b b b b b b b b b b
gmove is not unique).
b
– b b
− b
Second, we showthat any movefrom1, m, m + 1 with even m is to a winning position,using as ind uctive
b b b b b b b b b b b b b b b b b b b b b b
hypothesis that 1, mJ, mJ + 1 for even mJ and mJ < m is a losing position. The move to 0, m, m + 1
b b b b b
b
b b b b
b
b
b
b b b b b b b b b b b b b
produces a winning position with counter-
b b GT b b b
moveto0, m, m. A moveto 1, mJ, m +1 for mJ < m is to a winningposition withthe counter- moveto1, mJ,
b b b b b b b b b b b b b b
b
b b b b b b b b b b b b b
mJ +1 ifmJ is evenandto1, mJ,mJ − 1ifmJ is odd.Amove to1, m, mistoa win
b
b
b b b
b
b b b b b b
b
b b b
b
b b b b b b b b b b b GT
ning position withcounter- b b b
moveto0, m, m. A move to 1, m, mJ with mJ < mis alsoto awinningposition withthecounter- move
b b b b b b b b b b
b
b
b
b b b b b b b b b b b
to 1, mJ − 1, mJ if mJ is odd, and to 1, mJ
b b b 1, mJ if mJ is even (in which case mJ 1 < m beca
b
b b
b
b
b
b b b b b b
b
b
b
b b b b b b b b
use m is even). This concludes the induction proof.
+ +
b b b b b b b b b
This result is in agreement with the theorem on Nim heap sizes represented as sums of powers of2
b b b b b b b b b b b b b b b b b b
: 1 m ∗n+i s ∗l o s i+n ∗g ifandonlyif,exceptfor20, thepowersof2makingupm and n come in pa G
b
b T b GT b b b b b b b b b b b b b b b b b b
irs.So these mustbethe samepowers of 2, except for 1 = 20, which occurs in only mor n, where wehave
b b b b b b b b b b b b b b b b b b b b b b b b b
assumed thatn isthelargernumber,so 1appearsin the representation of n: We have m
b b b b b b b b b b b b b b b b b
= 2a 2b 2c G
+ + + ·· · ···1≥,so
b
b b b b
for a > b > c > b b
+
b b b b b b
2b + 2c + + · · · + 1 = m
G
T
m is even, and, with the same a,b,c,..., n = 2a
b b 1. Then
b b b b b b b b b b b b b
G b b b b b b
b b b
∗1 + ∗ m + ∗ n ≡ ∗ 0. Thefollowing is an exampleusingthe bit representation where
b T G T bGTG b T b bG T G T G b G T b bT G T G T b G bT b b b b b b b b b b b
m =12 (which determines the bitpattern 1100, which of coursedepends on m):
b b b b b b b b b b b b b b
1 = 0001
12 = 1100
13 = 1101 b
Nim-sum 0 = 0000
(b) We use(a). Clearly, 1, 2, 3 is losing as shown in (1.2), and because the Nim-
b b b b b b b b b b b b b b b b
sumof thebinaryrepresentations 01,10,11 is 00. Examples show thatanyother position is
b b b b b b b b b b b b b b b GT G
T
winning.The three numbers are n,n 1,n+ 2. I+f n is eventhenreducing theheap of size n 2 to
b b b b b b b b b b b b b b b b b b b b
1 creates thepositionn, n 1, 1 which is losing as shown in (a). If n is odd,thenn 1 is even b
+ +
b b b b b b b b b b b b GT b b b b b b b b b b
and n 2 = n 1 1 so by the same argument, a winning move is to reducetheNimheap of s
+ +
b b b b b b b b b b b b b b b b b b b b b b
ize n to1 (whi ch onlyworks if n > 1).
b b b b b b b b b
4
b
GameTheoryBasics1stEdition
b b b b b
ByBernhardvonStengel. Chapters1-12
b b b b b b b
1
, GT
1 -NimandCombinatorialGames
b b b b
2 -CongestionGames
b b
3 -GamesinStrategicForm
b b b b
4 -GameTreeswithPerfectInformation
b b b b b
5 - Expected Utility
b b
6 -MixedEquilibrium
b b
7 - Brouwer’s Fixed-Point Theorem
b b b
8 -Zero-SumGames
b b
9 -GeometryofEquilibriainBimatrixGames
b b b b b b
10 -GameTreeswithImperfectInformation
b b b b b
11 -Bargaining
b
12 -CorrelatedEquilibrium
b b
2
,Game Theory Basics b b
Solutions to Exercises b b
© Bernhard vonStengel2022
b b b b
Solution to Exercise 1.1 b b b
(a) Let≤ be defined by (1.7). To showthat ≤ is transitive, consider x, y, zwith x ≤ y and y ≤ z. If x =
b b b b b b b b b b b b b b b b b b b b b b b b b b
y thenx ≤z,andify =z then alsox ≤z.So theonlycaseleftis x < y and y < z,which implies x
b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b
< z because < is transitive, and hence x ≤ z.
b GT b GT b b b b b b
Clearly, ≤isreflexivebecause x = xandtherefore x ≤x. b b b b b b b b b b b b
Toshowthat ≤is antisymmetric,considerx and ywithx
b y andy≤ x. If we h≤ad x ≠ y then x
b b T bGT b b b b b b b b b G T b b b b b b b b
< y and y < x, and by transitivity x < x which contradicts (1.38). Hence x = y, as required. This shows
b b b b b b b b b b b b b b b b b b b b b b
that ≤is a partial order.
b b b b b b
Finally,weshow(1.6),so wehavetoshow thatx < y implies x yandx ≠ y≤ an d vice versa.Let x
b b b b b b b b b b b b b b G b b b b b b G T b b b b
<y, which implies x y by (1.7). If we had x = y≤t h e n x < x, contradicting(1.38),sowealsohavex
b b b b b b b b b b b b b b b b b b b b b b b
≠y. Conversely, x yandx ≠ yimplyby(1.7)x < y or x = y where≤the second case is excluded, h ence x <
b b b b b b b b b b b b b b b b b b GT b b b b b b b b
by, as required. b b
(b) Consider a partial order and≤ assume (1.6) as a definition of <. To show that < is transitive, su ppose
b b b b G T b b b b b b b b b b b b b b b
x < y, that is, x y and x ≠ y, and y <≤ z , that is, y z and y ≠ z. Because is tra≤
b b b b nsitive, x z. If we had xb b b b b b b b b b G T b b b b b b b b b b b b b b b b b
=≤ z then x
b GT y and y≤ x and hence x = y by antisym≤metry of ,≤which contradicts x ≠ y, so
G T b G b b G T G T G b b b b b b b b b b GT b b b b b
we have x z and x ≠ z, that is,x < z by (1.6), as required.
≤ ≤
b b b b b GTb b b b b b b b b b b
Also, < is irreflexive, because x < x would by definition mean x x and x ≠ ≤x , but the latter is n ot true.
b b b b b b b b b b b b G b b b b b b b b b b b b b
Finally,weshow(1.7), sowehavetoshowthatx ≤y implies x <yorx =y andvice versa, give n that< is
b b b b b b b b b b b b b b b b b b b b b b b b b b b b
definedby(1.6). Letx ≤y. Then if x =y, we aredone, otherwisex ≠y and thenbyd efinitionx <y.
b b b b b b b b b b b b b b b b b b b b b b b b b b b
bHence,x ≤y impliesx < yorx =y. Conversely,supposex < yorx =y. Ifx < y thenx ≤ y by (1.6),
b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b
and if x = y then x ≤ y because ≤isreflexive. Thiscompletes theproof. b b b b b b b b b b b b b b b b b
Solution to Exercise 1.2 b b b
(a) In analysing the games of three Nim heaps where one heap has size one, we first look at some e
b b b b b b b b b b b b b b b b GT b b
xamples, and then use mathematical induction to prove what we conjecture to be the losing positio ns. A
b b b b b b b b b b b b b b b b b b
losing position is one where every move is to a winning position, becausethen theoppon entwillwin.
b b b b b b b b b b b b b b b b b b b
Thepointofthisexerciseisto formulate aprecisestatement tobeproved,and the n to prove it.
b b b b b b b b b b b b b b b b b b b b
First, if there are only two heaps recall that they are losing if and only if the heaps are of equa l size. If
b b b b b b b b b b b b b b b b b b b b b b b
they are of unequal size, then the winning move is to reduce thelarger heap so that bo th heaps have
b b b b b b b b b b b b b b b b b b b b
equal size.
b b
3
, Consider three heaps of sizes 1, m, n, where 1 m ≤n . We≤observe the following: 1, 1, m is w
b b b b b b b b b T b GT b b b b b b b
inning, by moving to 1, 1, 0. Similarly, 1, m, m is winning, by moving to 0, m, m. Next, 1, 2, 3 i
b b b b b b b b b b b b b b GT b b b b b b b b
s losing(observed earlier inthe lecture), and hence1, 2, n for n 4 is winning. 1, 3, n is winnin gforany
b b b b b b b b b b b b b b b b b b b b b b b b
n 3 by moving to 1, 3, 2. For1, 4, 5,reducinganyheap produces awinningposition,
≥ ≥
b b b b b b b b b b b b b b b b b b b
so this is losing. b b b
Thegeneralpatternforthelosingpositions thus seems tobe: 1, m, m1, foreven+numbers m. This
b b b b b b b b b b b b b b b b GT b b
includes alsothe case m = 0, which we can take as the basecase foran induction. We now
b b b b b b b b b b GT b b b b b b b b
proceed toprovethis formally. b b b b
First we show that if the positions of the form 1, m, n with m b n are lo≤sing when m is even a b b b b b b b b b b b b b b b b b b b b
ndn =m1,thenthesea +r e theonlylosingpositionsbecauseanyotherposition1, m, n withm n is
b b b b b b b b b b b b b b b b b b b b b b b
winning. Namely, i f m = n then a winning move from1, m, m is to 0, m, m, so we can as
sume m < n. If m is even then n >≤
b b b G bTb b b b b b b b b b b b b b b b b b b
m 1 (otherwise we would be in the position 1, m, m 1)
+
b b b b b b b b b b b G b b b b b b b b b b
and so the winning move is to 1, m, m 1.If mis odd then the winning move is to 1, m, m 1, th
+ +
b b b b b b b b b b b b b b b b b b b b b b b b
esame as position 1, m 1, m (this would a l s o bea winning movefrom 1,m,m so there the winnin
b b b b b b b b b b b b b b b b b b b b b b
gmove is not unique).
b
– b b
− b
Second, we showthat any movefrom1, m, m + 1 with even m is to a winning position,using as ind uctive
b b b b b b b b b b b b b b b b b b b b b b
hypothesis that 1, mJ, mJ + 1 for even mJ and mJ < m is a losing position. The move to 0, m, m + 1
b b b b b
b
b b b b
b
b
b
b b b b b b b b b b b b b
produces a winning position with counter-
b b GT b b b
moveto0, m, m. A moveto 1, mJ, m +1 for mJ < m is to a winningposition withthe counter- moveto1, mJ,
b b b b b b b b b b b b b b
b
b b b b b b b b b b b b b
mJ +1 ifmJ is evenandto1, mJ,mJ − 1ifmJ is odd.Amove to1, m, mistoa win
b
b
b b b
b
b b b b b b
b
b b b
b
b b b b b b b b b b b GT
ning position withcounter- b b b
moveto0, m, m. A move to 1, m, mJ with mJ < mis alsoto awinningposition withthecounter- move
b b b b b b b b b b
b
b
b
b b b b b b b b b b b
to 1, mJ − 1, mJ if mJ is odd, and to 1, mJ
b b b 1, mJ if mJ is even (in which case mJ 1 < m beca
b
b b
b
b
b
b b b b b b
b
b
b
b b b b b b b b
use m is even). This concludes the induction proof.
+ +
b b b b b b b b b
This result is in agreement with the theorem on Nim heap sizes represented as sums of powers of2
b b b b b b b b b b b b b b b b b b
: 1 m ∗n+i s ∗l o s i+n ∗g ifandonlyif,exceptfor20, thepowersof2makingupm and n come in pa G
b
b T b GT b b b b b b b b b b b b b b b b b b
irs.So these mustbethe samepowers of 2, except for 1 = 20, which occurs in only mor n, where wehave
b b b b b b b b b b b b b b b b b b b b b b b b b
assumed thatn isthelargernumber,so 1appearsin the representation of n: We have m
b b b b b b b b b b b b b b b b b
= 2a 2b 2c G
+ + + ·· · ···1≥,so
b
b b b b
for a > b > c > b b
+
b b b b b b
2b + 2c + + · · · + 1 = m
G
T
m is even, and, with the same a,b,c,..., n = 2a
b b 1. Then
b b b b b b b b b b b b b
G b b b b b b
b b b
∗1 + ∗ m + ∗ n ≡ ∗ 0. Thefollowing is an exampleusingthe bit representation where
b T G T bGTG b T b bG T G T G b G T b bT G T G T b G bT b b b b b b b b b b b
m =12 (which determines the bitpattern 1100, which of coursedepends on m):
b b b b b b b b b b b b b b
1 = 0001
12 = 1100
13 = 1101 b
Nim-sum 0 = 0000
(b) We use(a). Clearly, 1, 2, 3 is losing as shown in (1.2), and because the Nim-
b b b b b b b b b b b b b b b b
sumof thebinaryrepresentations 01,10,11 is 00. Examples show thatanyother position is
b b b b b b b b b b b b b b b GT G
T
winning.The three numbers are n,n 1,n+ 2. I+f n is eventhenreducing theheap of size n 2 to
b b b b b b b b b b b b b b b b b b b b
1 creates thepositionn, n 1, 1 which is losing as shown in (a). If n is odd,thenn 1 is even b
+ +
b b b b b b b b b b b b GT b b b b b b b b b b
and n 2 = n 1 1 so by the same argument, a winning move is to reducetheNimheap of s
+ +
b b b b b b b b b b b b b b b b b b b b b b
ize n to1 (whi ch onlyworks if n > 1).
b b b b b b b b b
4
