SOLUTION MANUAL
Game Theory Basics 1st Edition
By Bernhard von Stengel. Chapters 1 - 12
1
,TABLE OF CONTENTS
1 - Nim and Combinatorial Games
2 - Congestion Games
3 - Games in Strategic Form
4 - Game Trees with Perfect Information
5 - Expected Utility
6 - Mixed Equilibrium
7 - Brouwer’s Fixed-Point Theorem
8 - Zero-Sum Games
9 - Geometry of Equilibria in Bimatrix Games
10 - Game Trees with Imperfect Information
11 - Bargaining
12 - Correlated Equilibrium
2
,Game Theory Basics
Solutions to Exercises
© Bernhard von Stengel 2022
Solution to Exercise 1.1
(a) Let ≤ be defined by (1.7). To show that ≤ is transitive, consider x, y, z with x ≤ y and y ≤ z. If x = y then
x ≤ z, and if y = z then also x ≤ z. So the only case left is x < y and y < z, which implies x < z
because < is transitive, and hence x ≤ z.
Clearly, ≤ is reflexive because x = x and therefore x ≤ x.
To show that ≤ is antisymmetric, consider x and y with x y and y ≤x. If we had≤x ≠ y then x < y
and y < x, and by transitivity x < x which contradicts (1.38). Hence x = y, as required. This shows that
≤ is a partial order.
Finally, we show (1.6), so we have to show that x < y implies x y and x ≠ y and ≤ vice versa. Let x < y,
which implies x y by (1.7). If we had x = y then≤x < x, contradicting (1.38), so we also have x ≠ y.
Conversely, x y and x ≠ y imply by (1.7)x < y or x = y where the second case is excluded, hence x <
y, as required. ≤
(b) Consider a partial order and assume
≤ (1.6) as a definition of <. To show that < is transitive, suppose x
< y, that is, x y and x ≠ y, and y < z, that is,≤y z and y ≠ z. Because is transitive, x ≤z. If we had x =
z then x y and y x and hence x = y by antisymmetry of , which contradicts x ≠ y, so we have x
≤ ≤ ≤ ≤
z and x ≠ z, that is,x < z by (1.6), as required.
≤ ≤
Also, < is irreflexive, because x < x would by definition mean x x and x ≠ x, but≤the latter is not true.
Finally, we show (1.7), so we have to show that x ≤ y implies x < y or x = y and vice versa, given that
< is defined by (1.6). Let x ≤ y. Then if x = y, we are done, otherwise x ≠ y and then by definition x <
y. Hence, x ≤ y implies x < y or x = y. Conversely, suppose x < y or x = y. If x < y then x ≤ y by
(1.6), and if x = y then x ≤ y because ≤ is reflexive. This completes the proof.
Solution to Exercise 1.2
(a) In analysing the games of three Nim heaps where one heap has size one, we first look at some
examples, and then use mathematical induction to prove what we conjecture to be the losing positions. A
losing position is one where every move is to a winning position, because then the opponent will win.
The point of this exercise is to formulate a precise statement to be proved, and then to prove it.
First, if there are only two heaps recall that they are losing if and only if the heaps are of equal size. If
they are of unequal size, then the winning move is to reduce the larger heap so that both heaps have
equal size.
3
, Consider three heaps of sizes 1, m, n, where 1 m ≤ n. ≤We observe the following: 1, 1, m is
winning, by moving to 1, 1, 0. Similarly, 1, m, m is winning, by moving to 0, m, m. Next, 1, 2, 3 is
losing (observed earlier in the lecture), and hence 1, 2, n for n 4 is winning. 1, 3, n is winning for any n
3 by moving to 1, 3, 2. For 1, 4, 5, reducing any heap produces a winning position, so this is losing.
≥ ≥
The general pattern for the losing positions thus seems to be: 1, m, m 1, for even numbers + m. This
includes also the case m = 0, which we can take as the base case foran induction. We now proceed to
prove this formally.
First we show that if the positions of the form 1, m, n with m n are losing≤when m is even and n =
m 1, then these are the only+ losing positions because any other position 1, m, n with m n is winning.
Namely, if m = n then a winning move from 1, m, m is to 0, m, m, so we can assume m < n. If m is even
then n > m 1 (otherwise we≤would be in the position 1, m, m 1) and so the winning move is to 1, m, m
+ would also be a
1. If m is odd then the winning move is to 1, m, m 1, the same as position 1, m 1, m (this
winning move from 1, m, m so there the winning+ move is not unique). +
– −
Second, we show that any move from 1, m, m + 1 with even m is to a winning position, using as inductive
hypothesis that 1, mJ, mJ + 1 for even mJ and mJ < m is a losing position. The move to 0, m, m + 1
produces a winning position with counter-move to 0, m, m. A move to 1, mJ, m + 1 for mJ < m is to a
winning position with the counter-move to 1, mJ, mJ + 1 if mJ is even and to 1, mJ, mJ − 1 if mJ is odd. A
move to 1, m, m is to a winning position with counter-move to 0, m, m. A move to 1, m, mJ with mJ < m is
also to a winning position with the counter-move to 1, mJ − 1, mJ if mJ is odd, and to 1, mJ 1, mJ if mJ is
even (in which case mJ 1 < m because m is even). This concludes the induction proof.
This result is in agreement with the theorem on Nim heap sizes represented as sums of powers of 2: 1
m n is losing if∗and 0
+∗only+∗if, except for 2 , 0the powers of 2 making upm and n come in pairs. So these must
be the same powers of 2, except for 1 = 2 , which occurs in only m or n,+where we have assumed that n is
+
the larger number, so 1 appears in the representation of n: We have m = 2a 2b 2c for a > b
>c> 1,so m is even, and, with the same a, b, c, . . ., n = 2 a 2 b 2c 1 = m 1. Then
1 m n 0. The following is an example using+the bit
+ representation
+ ··· where ··· ≥
∗ +∗ +∗ ≡∗
m = 12 (which determines the bit pattern 1100, which of course+depends + on + ·m):
··+ +
1 = 0001
12 = 1100
13 = 1101
Nim-sum 0 = 0000
(b) We use (a). Clearly, 1, 2, 3 is losing as shown in (1.2), and because the Nim-sum of the binary
representations 01, 10, 11 is 00. Examples show that any other position is winning. The three numbers
are n, n 1, n 2. If n is even then reducing the heap of size n 2 to 1 creates the position n, n 1, 1
+ +
which is losing as shown in (a). If n is odd, then n 1 is even and n 2 = n 1 1 so by the same
+ +
argument, a winning move is to reduce the Nim heap of size n to 1 (which only works if n > 1).
+ + ( + )+
4
Game Theory Basics 1st Edition
By Bernhard von Stengel. Chapters 1 - 12
1
,TABLE OF CONTENTS
1 - Nim and Combinatorial Games
2 - Congestion Games
3 - Games in Strategic Form
4 - Game Trees with Perfect Information
5 - Expected Utility
6 - Mixed Equilibrium
7 - Brouwer’s Fixed-Point Theorem
8 - Zero-Sum Games
9 - Geometry of Equilibria in Bimatrix Games
10 - Game Trees with Imperfect Information
11 - Bargaining
12 - Correlated Equilibrium
2
,Game Theory Basics
Solutions to Exercises
© Bernhard von Stengel 2022
Solution to Exercise 1.1
(a) Let ≤ be defined by (1.7). To show that ≤ is transitive, consider x, y, z with x ≤ y and y ≤ z. If x = y then
x ≤ z, and if y = z then also x ≤ z. So the only case left is x < y and y < z, which implies x < z
because < is transitive, and hence x ≤ z.
Clearly, ≤ is reflexive because x = x and therefore x ≤ x.
To show that ≤ is antisymmetric, consider x and y with x y and y ≤x. If we had≤x ≠ y then x < y
and y < x, and by transitivity x < x which contradicts (1.38). Hence x = y, as required. This shows that
≤ is a partial order.
Finally, we show (1.6), so we have to show that x < y implies x y and x ≠ y and ≤ vice versa. Let x < y,
which implies x y by (1.7). If we had x = y then≤x < x, contradicting (1.38), so we also have x ≠ y.
Conversely, x y and x ≠ y imply by (1.7)x < y or x = y where the second case is excluded, hence x <
y, as required. ≤
(b) Consider a partial order and assume
≤ (1.6) as a definition of <. To show that < is transitive, suppose x
< y, that is, x y and x ≠ y, and y < z, that is,≤y z and y ≠ z. Because is transitive, x ≤z. If we had x =
z then x y and y x and hence x = y by antisymmetry of , which contradicts x ≠ y, so we have x
≤ ≤ ≤ ≤
z and x ≠ z, that is,x < z by (1.6), as required.
≤ ≤
Also, < is irreflexive, because x < x would by definition mean x x and x ≠ x, but≤the latter is not true.
Finally, we show (1.7), so we have to show that x ≤ y implies x < y or x = y and vice versa, given that
< is defined by (1.6). Let x ≤ y. Then if x = y, we are done, otherwise x ≠ y and then by definition x <
y. Hence, x ≤ y implies x < y or x = y. Conversely, suppose x < y or x = y. If x < y then x ≤ y by
(1.6), and if x = y then x ≤ y because ≤ is reflexive. This completes the proof.
Solution to Exercise 1.2
(a) In analysing the games of three Nim heaps where one heap has size one, we first look at some
examples, and then use mathematical induction to prove what we conjecture to be the losing positions. A
losing position is one where every move is to a winning position, because then the opponent will win.
The point of this exercise is to formulate a precise statement to be proved, and then to prove it.
First, if there are only two heaps recall that they are losing if and only if the heaps are of equal size. If
they are of unequal size, then the winning move is to reduce the larger heap so that both heaps have
equal size.
3
, Consider three heaps of sizes 1, m, n, where 1 m ≤ n. ≤We observe the following: 1, 1, m is
winning, by moving to 1, 1, 0. Similarly, 1, m, m is winning, by moving to 0, m, m. Next, 1, 2, 3 is
losing (observed earlier in the lecture), and hence 1, 2, n for n 4 is winning. 1, 3, n is winning for any n
3 by moving to 1, 3, 2. For 1, 4, 5, reducing any heap produces a winning position, so this is losing.
≥ ≥
The general pattern for the losing positions thus seems to be: 1, m, m 1, for even numbers + m. This
includes also the case m = 0, which we can take as the base case foran induction. We now proceed to
prove this formally.
First we show that if the positions of the form 1, m, n with m n are losing≤when m is even and n =
m 1, then these are the only+ losing positions because any other position 1, m, n with m n is winning.
Namely, if m = n then a winning move from 1, m, m is to 0, m, m, so we can assume m < n. If m is even
then n > m 1 (otherwise we≤would be in the position 1, m, m 1) and so the winning move is to 1, m, m
+ would also be a
1. If m is odd then the winning move is to 1, m, m 1, the same as position 1, m 1, m (this
winning move from 1, m, m so there the winning+ move is not unique). +
– −
Second, we show that any move from 1, m, m + 1 with even m is to a winning position, using as inductive
hypothesis that 1, mJ, mJ + 1 for even mJ and mJ < m is a losing position. The move to 0, m, m + 1
produces a winning position with counter-move to 0, m, m. A move to 1, mJ, m + 1 for mJ < m is to a
winning position with the counter-move to 1, mJ, mJ + 1 if mJ is even and to 1, mJ, mJ − 1 if mJ is odd. A
move to 1, m, m is to a winning position with counter-move to 0, m, m. A move to 1, m, mJ with mJ < m is
also to a winning position with the counter-move to 1, mJ − 1, mJ if mJ is odd, and to 1, mJ 1, mJ if mJ is
even (in which case mJ 1 < m because m is even). This concludes the induction proof.
This result is in agreement with the theorem on Nim heap sizes represented as sums of powers of 2: 1
m n is losing if∗and 0
+∗only+∗if, except for 2 , 0the powers of 2 making upm and n come in pairs. So these must
be the same powers of 2, except for 1 = 2 , which occurs in only m or n,+where we have assumed that n is
+
the larger number, so 1 appears in the representation of n: We have m = 2a 2b 2c for a > b
>c> 1,so m is even, and, with the same a, b, c, . . ., n = 2 a 2 b 2c 1 = m 1. Then
1 m n 0. The following is an example using+the bit
+ representation
+ ··· where ··· ≥
∗ +∗ +∗ ≡∗
m = 12 (which determines the bit pattern 1100, which of course+depends + on + ·m):
··+ +
1 = 0001
12 = 1100
13 = 1101
Nim-sum 0 = 0000
(b) We use (a). Clearly, 1, 2, 3 is losing as shown in (1.2), and because the Nim-sum of the binary
representations 01, 10, 11 is 00. Examples show that any other position is winning. The three numbers
are n, n 1, n 2. If n is even then reducing the heap of size n 2 to 1 creates the position n, n 1, 1
+ +
which is losing as shown in (a). If n is odd, then n 1 is even and n 2 = n 1 1 so by the same
+ +
argument, a winning move is to reduce the Nim heap of size n to 1 (which only works if n > 1).
+ + ( + )+
4
