SOLUTION MANUAL Game Theory
Basics 1st Edition by Bernhardvon
Stengel. Chapters 1-12
1
,TABLE OF CONTENTS R R R
1 - Nim and Combinatorial Games
R R R R R
2 - Congestion Games
R R R
3 - Games in Strategic Form
R R R R R
4 - Game Trees with Perfect Information
R R R R R R
5 - Expected Utility
R R R
6 - Mixed Equilibrium
R R R
7 - Brouwer’s Fixed-Point Theorem
R R R R
8 - Zero-Sum Games
R R R
9 - Geometry of Equilibria in Bimatrix Games
R R R R R R R
10 - Game Trees with Imperfect Information
R R R R R R
11 - Bargaining
R R
12 - Correlated Equilibrium
R R R
2
,Game Theory Basics
R R
Solutions to Exercises
R R
©R BernhardRvonRStengelR2022
SolutionRtoRExerciseR1.1
(a) LetR≤RbeRdefinedRbyR(1.7).R ToRshowRthatR≤RisRtransitive,RconsiderRx,Ry,RzRwithRxR ≤RyRandRyR≤Rz.RIfRxR
=RyRthenRxR≤Rz,RandRifRyR=RzRthenRalsoRxR≤Rz.RSoRtheRonlyRcaseRleftRisRxR<RyRandRyR <Rz,RwhichRimpl
iesRxR <RzRbecauseR<RisRtransitive,RandRhenceRxR ≤Rz.
Clearly,R≤RisRreflexiveRbecauseRxR=RxRandRthereforeRxR≤Rx.
ToRshowRthatRRRRR
≤ isRantisymmetric,RconsiderRxRandRyRwithRxRRRRRyRand
≤RyRRRRRx.RIfRwe
≤ RhadRxR≠RyRthe
nRxR<RyRandRyR<Rx,RandRbyRtransitivityRxR<RxRwhichRcontradictsR(1.38).RHenceRxR=R y,RasRrequired.
R ThisRshowsRthatR ≤RisRaRpartialRorder.
Finally,RweRshowR(1.6),RsoRweRhaveRtoRshowRthatRxR<RyRimpliesRxRRRyRandRxR≤ ≠RyRandRviceRversa.RL
etRxR<Ry,RwhichRimpliesRxRyRbyR(1.7).RIfRweRhadR≤xR=RyRthenRxR<Rx,RcontradictingR(1.38),RsoRweRalsoR
haveRxR≠Ry.R Conversely,RxRRR yRandRxR≠RyRimplyRbyR(1.7)RxR <R yRorR xR =≤R yRwhereRtheRsecondRcaseRisRex
cluded,RhenceR xR <R y,RasRrequired.
(b) ConsiderRaRpartialRorderRand≤RassumeR(1.6)RasRaRdefinitionRofR<.RToRshowRthatR<RisRtransitive,Rs
upposeRxR<Ry,RthatRis,RxRyRandRxR≠Ry,Rand≤ RyR<Rz,RthatRis,RyRzRandRyR≠Rz.RBecauseRRRRisRtransitive,RxRRR
≤
Rz.RIfRweRhadRxR=RzRthenRxRRRRRyRandRyRRRRRxRandRhenceRxR=RyRbyRantisymmetryR ofRRRR ,RwhichR contra
≤ ≤ ≤ ≤
dictsR xR ≠R y,RsoRweRhaveR xRRRRzRandR xR ≠R z,RthatRis,RxR <R zRbyR(1.6),RasRrequired.
≤ ≤
Also,R<RisRirreflexive,RbecauseRxR<RxRwouldRbyRdefinitionRmeanRxRRRxRandRxR≤ ≠Rx,RbutRtheRlatterRis
RnotRtrue.
Finally,RweRshowR(1.7),RsoRweRhaveRtoRshowRthatRxR ≤RyRimpliesRxR<RyRorRxR=RyRandRviceRversa,Rgi
venRthatR<RisRdefinedRbyR(1.6).RLetRxR≤Ry.RThenRifRxR=Ry,RweRareRdone,RotherwiseRxR≠RyRandRthenR
byRdefinitionRxR<Ry.RHence,RxR≤RyRimpliesRxR<RyRorRxR=Ry.RConversely,RsupposeRxR <R yRorRxR=Ry.R If
RxR <R yRthenRxR ≤RyRbyR(1.6),RandRifRxR=RyRthenRxR ≤R yRbecauseR ≤RisRreflexive.R ThisRcompletesRtheR
proof.
SolutionRtoRExerciseR1.2
(a) InR analysingR theR gamesR ofR threeR NimR heapsR whereR oneR heapR hasR sizeR one,R weR firstR lookRatRsomeR
examples,RandRthenRuseRmathematicalRinductionRtoRproveRwhatRweRconjectureRtoRbeRtheRlosingRposi
tions.RARlosingRpositionRisRoneRwhereReveryRmoveRisRtoRaRwinningRposition,RbecauseRthenRtheRo
pponentRwillRwin.R TheRpointRofRthisRexerciseRisRtoRformulateRaRpreciseRstatementRtoRbeRproved,R
andRthenRtoRproveRit.
First,RifRthereRareRonlyRtwoRheapsRrecallRthatRtheyRareRlosingRifRandRonlyRifRtheRheapsRareRofReq
ualRsize.R IfRtheyRareRofRunequalRsize,RthenRtheRwinningRmoveRisRtoRreduceRtheRlargerRheapRsoRth
atRbothRheapsRhaveRequalRsize.
3
, ConsiderRthreeRheapsRofRsizesR1,Rm,Rn,RwhereR1RRRRRmRRRRR
≤ n.RWe
≤ RobserveRtheRfollowing:R1,R1,RmRi
sRwinning,RbyRmovingRtoR1,R1,R0.RSimilarly,R1,Rm,RmRisRwinning,RbyRmovingRtoR0,Rm,Rm.RNext,R1,R
2,R3RisRlosingR(observedRearlierRinRtheRlecture),RandRhenceR1,R2,RnRforRnR4RisRwinning.R1,R3,RnRisR
winningRforRanyRnR3RbyRmovingRtoR1,R3,R2.RForR1,R4,R5,RreducingRanyRheapRproducesRaRwinning
≥ ≥
Rposition,RsoRthisRisRlosing.
TheRgeneralRpatternRforRtheRlosingRpositionsRthusRseemsRtoRbe:R1,Rm,RmR1,RforReven+ RnumbersR
m.R ThisRincludesRalsoRtheRcaseRmR=R0,RwhichRweRcanRtakeRasRtheRbaseRcaseRforRanRinduction.R W
eRnowRproceedRtoRproveRthisRformally.
FirstRweRshowRthatRifRtheRpositionsRofRtheRformR1,Rm,RnRwithRmRRRRRRnRare≤RlosingRwhenRmRisReven
RandRnR=RmR1,RthenRtheseRareRtheRonlyRlosingRpositionsRbecauseRanyRotherRpositionR1, Rm,RnR with
+
RmR R nR isRwinning.R Namely,RifRmR =RnR thenRaRwinningRmoveRfromR1, Rm,RmRisRtoR0, Rm, Rm,RsoRweRcanR
≤
assumeRmR<Rn.R IfRmRisRevenRthenRnR>RmR R 1R(otherwiseRweRwouldRbeRinRtheRpositionR1,Rm,RmR R 1)R
+
andRsoRtheRwinningRmoveRisRtoR1,Rm,RmR R 1.RIfRmRisRoddRthenRtheRwinningRmoveRisRtoR1,Rm,RmR1,Rth
+ +
eRsameRasRpositionR1,RmR1,RmR(thisRwouldR alsoR beR aR winningR moveR fromR 1,Rm,RmR soR thereR theR winni
ngR moveR isR notR unique). – −
Second,RweRshowRthatRanyRmoveRfromR1,Rm,RmR+R1RwithRevenRmRisRtoRaRwinningRposition,RusingRasRi
nductiveRhypothesisRthatR1,RmJ,RmJR+R1RforRevenRmJRandRmJR<RmRisRaRlosingRposition.RTheRmoveRt
oR0,Rm,RmR+R1RproducesRaRwinningRpositionRwithRcounter-
moveRtoR0,Rm,Rm.RARmoveRtoR1,RmJ,RmR+R1RforRmJR<RmRisRtoRaRwinningRpositionRwithRtheRcounter-
moveRtoR1,RmJ,RmJR+R1RifRmJRisRevenRandRtoR1,RmJ,RmJR−R1RifRmJRisRodd.RARmoveRtoR1,Rm,RmRisRtoRaR
winningRpositionRwithRcounter-
moveRtoR0,Rm,Rm.RARmoveRtoR1,Rm,RmJRwithR mJR<R mRisRalsoRtoRaRwinningRpositionRwithRtheRcounter-
moveRtoR1,RmJR−R1,RmJRifR mJRisRodd,RandRtoR1,RmJR 1,RmJRifRmJRisRevenR(inRwhichRcaseRmJR 1R<RmRbeca
useRmRisReven).RThisRconcludesRtheRinductionRproof.
+ +
ThisRresultRisRinRagreementRwithRtheRtheoremRonRNimRheapRsizesRrepresentedRasRsumsRofRpowersRo
fR2:R 1R R mR R ∗ nRRis+∗ 0
RlosingRifRandRonlyRif,RexceptRforR2 ,RtheRpowersRofR2RmakingRupRmRandRnRcomeRinR
+∗
pairs.RSoRtheseRmustRbeRtheRsameRpowersRofR2,RexceptRforR1R=R20,RwhichRoccursRinRonlyRmRorRn,Rwh
ereRweRhaveRassumedRthatRnRisRtheRlargerRnumber,RsoR1RappearsRinR theR representationRofR n:R WeR
haveR mR =R 2aRRRRRR2bRRRRRR2c
+ + +R ·R ·R · ·R ·R ·R ≥
forR aR >R bR >R cR >RRRRRRRR 1,RsoR
+ + +R ·R ·R ·R + +
mR isR even,R and,R withR theR sameR a,Rb,Rc,R.R.R.,R nR =R 2aR R R 2bR R R 2c 1R =R mRRRR 1.R Then
1 m
∗R +R ∗ +R ∗ ≡R∗
RRRRRR RRRRR n RRRRRR 0.R The R followingR isR an R example R using R theR bitR representation R where
mR=R12R(whichRdeterminesRtheRbitRpatternR1100,RwhichRofRcourseRdependsRonRm):
1 = 0001
12 = 1100
13 = 1101
Nim-sum 0 = 0000
(b) WeRuseR(a).RClearly,R1,R2,R3RisRlosingRasRshownRinR(1.2),RandRbecauseRtheRNim-
sumRofRtheRbinaryRrepresentationsR01,R10,R11RisR00.RExamplesRshowRthatRanyRotherRpositionRi
sRwinning.RTheRthreeRnumbersRareRn,RnR 1,Rn+R R 2.RIf+RnRisRevenRthenRreducingRtheRheapRofRsizeRnR2Rt
oR1RcreatesRtheRpositionRn,RnR 1,R1RwhichRisRlosingRasRshownRinR(a).RIfRnRisRodd,RthenRnR 1RisRev
+ +
enRandRnRRR2R=R nRRR1RRR1RsoRbyRtheRsameRargument,RaRwinningRmoveRisRtoRreduceRtheRNimRhea
+ + (R +R )R+
pRofRsizeRnRtoR1R(whichRonlyRworksRifRnR >R1).
4
Basics 1st Edition by Bernhardvon
Stengel. Chapters 1-12
1
,TABLE OF CONTENTS R R R
1 - Nim and Combinatorial Games
R R R R R
2 - Congestion Games
R R R
3 - Games in Strategic Form
R R R R R
4 - Game Trees with Perfect Information
R R R R R R
5 - Expected Utility
R R R
6 - Mixed Equilibrium
R R R
7 - Brouwer’s Fixed-Point Theorem
R R R R
8 - Zero-Sum Games
R R R
9 - Geometry of Equilibria in Bimatrix Games
R R R R R R R
10 - Game Trees with Imperfect Information
R R R R R R
11 - Bargaining
R R
12 - Correlated Equilibrium
R R R
2
,Game Theory Basics
R R
Solutions to Exercises
R R
©R BernhardRvonRStengelR2022
SolutionRtoRExerciseR1.1
(a) LetR≤RbeRdefinedRbyR(1.7).R ToRshowRthatR≤RisRtransitive,RconsiderRx,Ry,RzRwithRxR ≤RyRandRyR≤Rz.RIfRxR
=RyRthenRxR≤Rz,RandRifRyR=RzRthenRalsoRxR≤Rz.RSoRtheRonlyRcaseRleftRisRxR<RyRandRyR <Rz,RwhichRimpl
iesRxR <RzRbecauseR<RisRtransitive,RandRhenceRxR ≤Rz.
Clearly,R≤RisRreflexiveRbecauseRxR=RxRandRthereforeRxR≤Rx.
ToRshowRthatRRRRR
≤ isRantisymmetric,RconsiderRxRandRyRwithRxRRRRRyRand
≤RyRRRRRx.RIfRwe
≤ RhadRxR≠RyRthe
nRxR<RyRandRyR<Rx,RandRbyRtransitivityRxR<RxRwhichRcontradictsR(1.38).RHenceRxR=R y,RasRrequired.
R ThisRshowsRthatR ≤RisRaRpartialRorder.
Finally,RweRshowR(1.6),RsoRweRhaveRtoRshowRthatRxR<RyRimpliesRxRRRyRandRxR≤ ≠RyRandRviceRversa.RL
etRxR<Ry,RwhichRimpliesRxRyRbyR(1.7).RIfRweRhadR≤xR=RyRthenRxR<Rx,RcontradictingR(1.38),RsoRweRalsoR
haveRxR≠Ry.R Conversely,RxRRR yRandRxR≠RyRimplyRbyR(1.7)RxR <R yRorR xR =≤R yRwhereRtheRsecondRcaseRisRex
cluded,RhenceR xR <R y,RasRrequired.
(b) ConsiderRaRpartialRorderRand≤RassumeR(1.6)RasRaRdefinitionRofR<.RToRshowRthatR<RisRtransitive,Rs
upposeRxR<Ry,RthatRis,RxRyRandRxR≠Ry,Rand≤ RyR<Rz,RthatRis,RyRzRandRyR≠Rz.RBecauseRRRRisRtransitive,RxRRR
≤
Rz.RIfRweRhadRxR=RzRthenRxRRRRRyRandRyRRRRRxRandRhenceRxR=RyRbyRantisymmetryR ofRRRR ,RwhichR contra
≤ ≤ ≤ ≤
dictsR xR ≠R y,RsoRweRhaveR xRRRRzRandR xR ≠R z,RthatRis,RxR <R zRbyR(1.6),RasRrequired.
≤ ≤
Also,R<RisRirreflexive,RbecauseRxR<RxRwouldRbyRdefinitionRmeanRxRRRxRandRxR≤ ≠Rx,RbutRtheRlatterRis
RnotRtrue.
Finally,RweRshowR(1.7),RsoRweRhaveRtoRshowRthatRxR ≤RyRimpliesRxR<RyRorRxR=RyRandRviceRversa,Rgi
venRthatR<RisRdefinedRbyR(1.6).RLetRxR≤Ry.RThenRifRxR=Ry,RweRareRdone,RotherwiseRxR≠RyRandRthenR
byRdefinitionRxR<Ry.RHence,RxR≤RyRimpliesRxR<RyRorRxR=Ry.RConversely,RsupposeRxR <R yRorRxR=Ry.R If
RxR <R yRthenRxR ≤RyRbyR(1.6),RandRifRxR=RyRthenRxR ≤R yRbecauseR ≤RisRreflexive.R ThisRcompletesRtheR
proof.
SolutionRtoRExerciseR1.2
(a) InR analysingR theR gamesR ofR threeR NimR heapsR whereR oneR heapR hasR sizeR one,R weR firstR lookRatRsomeR
examples,RandRthenRuseRmathematicalRinductionRtoRproveRwhatRweRconjectureRtoRbeRtheRlosingRposi
tions.RARlosingRpositionRisRoneRwhereReveryRmoveRisRtoRaRwinningRposition,RbecauseRthenRtheRo
pponentRwillRwin.R TheRpointRofRthisRexerciseRisRtoRformulateRaRpreciseRstatementRtoRbeRproved,R
andRthenRtoRproveRit.
First,RifRthereRareRonlyRtwoRheapsRrecallRthatRtheyRareRlosingRifRandRonlyRifRtheRheapsRareRofReq
ualRsize.R IfRtheyRareRofRunequalRsize,RthenRtheRwinningRmoveRisRtoRreduceRtheRlargerRheapRsoRth
atRbothRheapsRhaveRequalRsize.
3
, ConsiderRthreeRheapsRofRsizesR1,Rm,Rn,RwhereR1RRRRRmRRRRR
≤ n.RWe
≤ RobserveRtheRfollowing:R1,R1,RmRi
sRwinning,RbyRmovingRtoR1,R1,R0.RSimilarly,R1,Rm,RmRisRwinning,RbyRmovingRtoR0,Rm,Rm.RNext,R1,R
2,R3RisRlosingR(observedRearlierRinRtheRlecture),RandRhenceR1,R2,RnRforRnR4RisRwinning.R1,R3,RnRisR
winningRforRanyRnR3RbyRmovingRtoR1,R3,R2.RForR1,R4,R5,RreducingRanyRheapRproducesRaRwinning
≥ ≥
Rposition,RsoRthisRisRlosing.
TheRgeneralRpatternRforRtheRlosingRpositionsRthusRseemsRtoRbe:R1,Rm,RmR1,RforReven+ RnumbersR
m.R ThisRincludesRalsoRtheRcaseRmR=R0,RwhichRweRcanRtakeRasRtheRbaseRcaseRforRanRinduction.R W
eRnowRproceedRtoRproveRthisRformally.
FirstRweRshowRthatRifRtheRpositionsRofRtheRformR1,Rm,RnRwithRmRRRRRRnRare≤RlosingRwhenRmRisReven
RandRnR=RmR1,RthenRtheseRareRtheRonlyRlosingRpositionsRbecauseRanyRotherRpositionR1, Rm,RnR with
+
RmR R nR isRwinning.R Namely,RifRmR =RnR thenRaRwinningRmoveRfromR1, Rm,RmRisRtoR0, Rm, Rm,RsoRweRcanR
≤
assumeRmR<Rn.R IfRmRisRevenRthenRnR>RmR R 1R(otherwiseRweRwouldRbeRinRtheRpositionR1,Rm,RmR R 1)R
+
andRsoRtheRwinningRmoveRisRtoR1,Rm,RmR R 1.RIfRmRisRoddRthenRtheRwinningRmoveRisRtoR1,Rm,RmR1,Rth
+ +
eRsameRasRpositionR1,RmR1,RmR(thisRwouldR alsoR beR aR winningR moveR fromR 1,Rm,RmR soR thereR theR winni
ngR moveR isR notR unique). – −
Second,RweRshowRthatRanyRmoveRfromR1,Rm,RmR+R1RwithRevenRmRisRtoRaRwinningRposition,RusingRasRi
nductiveRhypothesisRthatR1,RmJ,RmJR+R1RforRevenRmJRandRmJR<RmRisRaRlosingRposition.RTheRmoveRt
oR0,Rm,RmR+R1RproducesRaRwinningRpositionRwithRcounter-
moveRtoR0,Rm,Rm.RARmoveRtoR1,RmJ,RmR+R1RforRmJR<RmRisRtoRaRwinningRpositionRwithRtheRcounter-
moveRtoR1,RmJ,RmJR+R1RifRmJRisRevenRandRtoR1,RmJ,RmJR−R1RifRmJRisRodd.RARmoveRtoR1,Rm,RmRisRtoRaR
winningRpositionRwithRcounter-
moveRtoR0,Rm,Rm.RARmoveRtoR1,Rm,RmJRwithR mJR<R mRisRalsoRtoRaRwinningRpositionRwithRtheRcounter-
moveRtoR1,RmJR−R1,RmJRifR mJRisRodd,RandRtoR1,RmJR 1,RmJRifRmJRisRevenR(inRwhichRcaseRmJR 1R<RmRbeca
useRmRisReven).RThisRconcludesRtheRinductionRproof.
+ +
ThisRresultRisRinRagreementRwithRtheRtheoremRonRNimRheapRsizesRrepresentedRasRsumsRofRpowersRo
fR2:R 1R R mR R ∗ nRRis+∗ 0
RlosingRifRandRonlyRif,RexceptRforR2 ,RtheRpowersRofR2RmakingRupRmRandRnRcomeRinR
+∗
pairs.RSoRtheseRmustRbeRtheRsameRpowersRofR2,RexceptRforR1R=R20,RwhichRoccursRinRonlyRmRorRn,Rwh
ereRweRhaveRassumedRthatRnRisRtheRlargerRnumber,RsoR1RappearsRinR theR representationRofR n:R WeR
haveR mR =R 2aRRRRRR2bRRRRRR2c
+ + +R ·R ·R · ·R ·R ·R ≥
forR aR >R bR >R cR >RRRRRRRR 1,RsoR
+ + +R ·R ·R ·R + +
mR isR even,R and,R withR theR sameR a,Rb,Rc,R.R.R.,R nR =R 2aR R R 2bR R R 2c 1R =R mRRRR 1.R Then
1 m
∗R +R ∗ +R ∗ ≡R∗
RRRRRR RRRRR n RRRRRR 0.R The R followingR isR an R example R using R theR bitR representation R where
mR=R12R(whichRdeterminesRtheRbitRpatternR1100,RwhichRofRcourseRdependsRonRm):
1 = 0001
12 = 1100
13 = 1101
Nim-sum 0 = 0000
(b) WeRuseR(a).RClearly,R1,R2,R3RisRlosingRasRshownRinR(1.2),RandRbecauseRtheRNim-
sumRofRtheRbinaryRrepresentationsR01,R10,R11RisR00.RExamplesRshowRthatRanyRotherRpositionRi
sRwinning.RTheRthreeRnumbersRareRn,RnR 1,Rn+R R 2.RIf+RnRisRevenRthenRreducingRtheRheapRofRsizeRnR2Rt
oR1RcreatesRtheRpositionRn,RnR 1,R1RwhichRisRlosingRasRshownRinR(a).RIfRnRisRodd,RthenRnR 1RisRev
+ +
enRandRnRRR2R=R nRRR1RRR1RsoRbyRtheRsameRargument,RaRwinningRmoveRisRtoRreduceRtheRNimRhea
+ + (R +R )R+
pRofRsizeRnRtoR1R(whichRonlyRworksRifRnR >R1).
4
