Solution Manual for Game Theory Basics 1st Edition By Bernhar vodn Stengel, ISBN: 9781108843300, All 12 Chapters Covered

SOLUTIONMANUAL b




GameTheoryBasics1stEdition
b b b b b




ByBernhardvonStengel. Chapters1-12
b b b bb b b b




1

,TABLE OF CONTENTS b b b




1 - Nim and Combinatorial Games
b b b b b




2 - Congestion Games
b b b




3 - Games in Strategic Form
b b b b b




4 - Game Trees with Perfect Information
b b b b b b




5 - Expected Utility
b b b




6 - Mixed Equilibrium
b b b




7 - Brouwer’s Fixed-Point Theorem
b b b b




8 - Zero-Sum Games
b b b




9 - Geometry of Equilibria in Bimatrix Games
b b b b b b b




10 - Game Trees with Imperfect Information
b b b b b b




11 - Bargaining
b b




12 - Correlated Equilibrium
b b b




2

,Game Theory Basics b b




Solutions to Exercises b b




© Bernhard von Stengel 2022
b b b b




SolutiontoExercise1.1 b b b




(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,
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 b




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,
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 b b




and hence x ≤ z.
b b b b b




Clearly, ≤isreflexivebecause x = xandtherefore x ≤x. b b b b b b b b b b b b




To show that is antisymmetric,
≤ b consider x and y with x y and y x. If we had
≤ x ≠ y then≤
x < y and y < x, and
b bb bb b b b b b b b b b b b b b b b bb b b b b b b b b b b b b b b b b b b




by transitivity x < x which contradicts (1.38). Hence x = y, as required. This shows that ≤ is a partial
b b b b b b b b b b b b b b b b b b b b b




order.
b




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
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 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
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 yandx ≠ yimplyby(1.7)x < y or x = y where the second case is excluded,≤hence x < y, as required.
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) Consider a partial order and assume ≤ (1.6) as a definition of <. To show that < is transitive, suppose x < b b b b b b b b b b b b b b b b b b b b




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
b b b b b b b b b b b b b b b b b b b b b b bbb b b b bb b b b b b b b b b b bb b b b b b bb b b b




and hence≤x = y by antisymmetry
b



≤ of , which contradicts x ≠ y, so≤we have x z≤and x ≠ z, that is,x < z by
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 b b b b




(1.6), as required.
≤ ≤
b b b




Also, < is irreflexive, because x < x would by definition mean x x and x ≠ x, but the≤
b b latter is not true.
b b b b b b b b b b bb b b b b b b b b b b b




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
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 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
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 ≤ 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
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 b b b




b then x ≤ y because ≤is reflexive. This completes the proof.
b b b b b b b b b b b




SolutiontoExercise1.2 b b b




(a) In analysing the games of three Nim heaps where one heap has size one, we first look at some
b b b b b b b b b b b b b b b b b b




examples, and then use mathematical induction to prove what we conjecture to be the losing positions. A
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, because then the opponent will win.
b b b b b b b b b b b b b b b b b b




The point of this exercise is to formulate a precise statement to be proved, and then to prove it.
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 equal size. If
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 the larger heap so that both 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 winning, by 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 moving to 1, 1, 0. Similarly, 1, m, m is winning, by moving to 0, m, m. Next, 1, 2, 3 is losing (observed
b b b b b b b b b b b b b b b b b b b b b b b




b 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,
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




2. For 1, 4, 5, reducing any heap produces a winning position, so this is losing.
≥ ≥
b b b b b b b b b b b b b b b b




The general pattern for the losing positions thus seems to be: 1, m, m 1, for even numbers
b

+ m. This b b b b b b b b b b b b b b b b b b




includes also the case m = 0, which we can take as the base case for an induction. We now proceed to
b b b b b b b b b b b b b b b b b b b b b b




prove this formally.
b b b




First we show that if the positions of the form 1, m, n with m n are losing when
b

≤ m is even and n = 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 b b b b




b then these are the only losing
+ positions because any
b other position 1, m, n with m n is winning. b b b b b b b b b b b b b b b b b b




b Namely, if m = n then a winning
≤ move from1, m, m is to 0, m, m, so we can assume m < n. If m is even then 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




n>m 1 (otherwise we would be in the position 1, m, m 1) and so the winning move is to 1, m, m
+
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




1. If m is odd then the winning move is to 1, m, m 1, the same as position 1, m 1, m (this would also be a
+ +
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




winning move from 1,m,m so there the winning move is not unique).
– −
b b b b b b b b b b b b b b




Second, we show that any move from 1, m, m + 1 with even m is to a winning position, using as inductive
b 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 produces 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 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
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 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
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 b b




b winning position with counter-move to 0, m, m. A move to 1, m, mJ with mJ < m is also to a winning b b b b b b b b b b b b b b b b b b b b b b




b 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
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 1 < m because m is even). This concludes theinduction proof.
b b 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 of 2: 1
b b b b b b b b b b b b b b b b b b b b




m n islosing∗ifa+∗ ndonly 0
b

+if, exceptfor2 , thepowersof2makingupm and
+∗ b b

+n come in pairs. So these must be
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




0
b




b the same powers of 2, except for 1 = 2 , which occurs in only m or n, where we have assumed that n is the
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 larger number, so 1 appearsin the representation of n: We have m = 2a 2b 2c for a > b > c >
b b b b b b b b b b b b b b
bbb bb b b bb b b b



b b b b b b b b b b b b b




1,so m is even, and, with the same a,b,c,..., n = 2a 2b 2c 1 = m 1. Then
+ + + ··· ··· ≥
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 bbb b b




1 m n
∗ + ∗ + ∗ ≡∗0. The following is an example using the bit representation where
b b b b b b




+ + + ··· + +
bbbbb b b bb b b b b bb b b b b b b b b b b b b

b b b b




m =12(whichdeterminesthe bitpattern1100,whichof course dependson m):
b b b b




b b b b b b b b b b b b b b




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
b b b b b b b b b b b b b b b b b b b




representations 01, 10, 11 is 00. Examples show that any other position is winning. The three
b b b b b b b b b b b b b b b b




numbers are n, n 1, n 2. If n is even then reducing
b




+ the
+ heap of size n 2 to 1 creates the position n, n 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 b




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,
+ +
b b b b b b b b b b b b b b b b b b b bb b b b bb b bbb b b b b b




a winning move is to reduce the Nim heap of size n to 1 (which only works if n > 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




4