Solution Manual for Game Theory Basics 1st Edition – Lecture Summary

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