2018

UNDERGRADUATEGAMETHEORY

LECTURENOTES

BY

OMERTAMUZ

CaliforniaInstituteofTechnology

2

Acknowledgments

TheselecturenotesarepartiallyadaptedfromOsborneandRubinstein[

29

],Maschler,SolanandZamir[

23

],lecturenotesbyFedericoEchenique,andslidesbyDaronAcemogluandAsuOzdaglar.IamindebtedtoSeoYoung(Silvia)KimandZhuofangLifortheirhelpin?ndingandcorrectingmanyerrors.Anycommentsorsuggestionsarewelcome.

3

Contents

1WhatisaGame?

7

2Finiteextensiveformgameswithperfectinformation

8

2.1Tic-Tac-Toe

8

2.2TheSweetFifteenGame

8

2.3Chess

8

2.4De?nitionof?niteextensiveformgameswithperfectinformation

10

2.5Theultimatumgame

10

2.6Equilibria

11

2.7Thecentipedegame

11

2.8Subgamesandsubgameperfectequilibria

13

2.9Thedollarauction

14

2.10Backwardinduction,Kuhn’sTheoremandaproofofZermelo’sTheorem

15

3Strategicformgames

17

3.1De?nition

17

3.2Nashequilibria

17

3.3Classicalexamples

17

3.4Dominatedstrategies

21

3.5Repeatedeliminationofdominatedstrategies

21

3.6Dominantstrategies

22

3.7MixedequilibriaandNash’sTheorem

23

3.8ProofofNash’sTheorem

24

3.9Bestresponses

25

3.10Tremblinghandperfectequilibria

27

3.10.1Motivatingexample

27

3.10.2De?nitionandresults

27

3.11Correlatedequilibria

29

3.11.1Motivatingexample

29

3.11.2De?nition

29

3.12Zero-sumgames

31

3.12.1Motivatingexample

31

3.12.2De?nitionandresults

31

4Knowledgeandbelief

33

4.1Knowledge

33

4.1.1Thehatsriddle

33

4.1.2Knowledgespaces

33

4.1.3Knowledge

34

4.1.4Knowledgeintermsofself-evidenteventalgebras

35

4.1.5Commonknowledge

37

4

4.1.6Backtothehatsriddle

39

4.2Beliefs

40

4.2.1Amotivatingexample

40

4.2.2Beliefspaces

41

4.3Rationalizability

41

4.4Agreeingtodisagree

42

4.5Notrade

43

4.6Reachingcommonknowledge

44

4.7Bayesiangames

46

5Auctions

47

5.1Classicalauctions

47

5.1.1Firstprice,sealedbidauction

47

5.1.2Secondprice,sealedbidauction

48

5.1.3Englishauction

49

5.1.4Socialwelfare

49

5.2Bayesianauctions

50

5.2.1Secondprice,sealedbidauction

50

5.2.2Firstprice,sealedbidauction

50

5.3Truthfulmechanismsandtherevelationprinciple

53

6Extensiveformgameswithchancemovesandimperfectinformation

55

6.1Motivatingexample:traininspections

55

6.2De?nition

56

6.3Purestrategies,mixedstrategiesandbehavioralstrategies

58

6.4Beliefsystemsandassessments

60

6.5Sequentialrationalityandsequentialequilibria

60

6.6Tremblinghandperfectequilibrium

61

6.7PerfectBayesianequilibrium

61

6.8Cheaptalk

63

6.8.1Example1

63

6.8.2Example2

63

6.8.3Example3

64

6.9TheWalmartgame

65

6.9.1Perfectinformation,oneround

65

6.9.2Perfectinformation,manyrounds

65

6.9.3Imperfectinformation,oneround

65

6.9.4Imperfectinformation,manyrounds

66

7Repeatedgames

69

7.1De?nition

69

7.2Payoffs

69

7.2.1Finitelyrepeatedgames

69

5

7.2.2In?nitelyrepeatedgames:discounting

70

7.2.3In?nitelyrepeatedgames:limitofmeans

70

7.3Folktheorems

72

7.3.1Examples

72

7.3.2Enforceableandfeasiblepayoffs

72

7.4Nashfolktheorems

73

7.5Perfectfolktheorems

75

7.5.1Perfectfolktheoremforlimitingmeans

75

7.5.2Perfectfolktheoremsfordiscounting

76

7.6Finitelyrepeatedgames

82

7.6.1Nashequilibriaandfolktheorems

82

7.6.2PerfectNashequilibriaandfolktheorems

84

8Sociallearning

85

8.1Bayesianhypothesistesting

85

8.2Herdbehavior

87

9Betterresponsedynamicsandpotentialgames

90

9.1Betterresponsedynamics

90

9.2Acongestiongame

90

9.3Potentialgames

91

9.4Theconformismgame

92

10Socialchoice

93

10.1Preferencesandconstitutions

93

10.2TheCondorcetParadox

94

10.3Arrow’sTheorem

94

10.4TheGibbard-SatterthwaiteTheorem

94

6

Disclaimer

Thisanotatextbook.Thesearelecturenotes.

7

1WhatisaGame?

Agameisamathematicalmodelofastrategicinteraction.Wewillbestudyingawidevarietyofgames,butallofthemwillhavethefollowingcommonelements.

?Players.Weoftenthinkofplayersaspeople,butsometimestheymodelbusinesses,teams,politicalparties,countries,etc.

?Choices.Playershavetomakeachoiceormultiplechoicesbetweendifferentactions.Aplayer’sstrategyisherruleforchoosingactions.

?Outcomes.Whentheplayersaredonechoosing,anoutcomeisrealizedandthegameends.Thisoutcomedependsonthechoices.Examplesofoutcomesinclude“player1wins,”“FloragetsadollarandMilesgetstwodollars,”or“anuclearwarstartsandeveryonedies.”

?Preferences.Playershavepreferencesoveroutcomes.Forexample,Floramayprefertheoutcome“FloragetstwodollarsandMilesgetsnothing”overtheoutcome“MilesgetsadollarandFloragetsnothing.”Milesmayhavetheoppositepreference.

Twoimportantfeaturesmakeagamestrategic:?rst,thefactthatoutcomesaredeter-minedbyeveryone’sactions,ratherthanbytheactionsofjustoneplayer.Second,thatplayershavedifferentpreferences.Thiscreatestensions,whichmakegamesinteresting.

Gamesdifferinmanyaspects.

?Timing.Doplayerschooseonce(e.g.,rock-paper-scissors),oragainandagainovertime(e.g.,chess)?Inthelattercase,doesthegameeventuallyend,ordoesitcontinueforever?Dotheychoosesimultaneously,orinturn?

?Observations.Canplayersobserveeachother’schoices?

?Uncertainty.Istheoutcomerandom,orisitadeterministicfunctionoftheplayers’actions?Dosomeplayershaveinformationthattheothersdonot?

Itisimportanttonotethatagamedoesnotspecifywhattheplayersactuallydo,butonlywhattheiroptionsareandwhattheconsequencesare.Unlikeanequationwhich(maybe)hasauniquesolution,theansweringamesismuchlessclearcut.Asolutionconceptisawaytothinkaboutwhattheyplayersmightdecidetodo.Itisnotpartofthedescriptionofthegame,anddifferentsolutionconceptscanyielddifferentpredictionsforthesamegame.

8

2Finiteextensiveformgameswithperfectinformation

Wewillstartbystudyingasimplefamilyofgames,whichincludesmanythatareindeedgamesinthelaypersonmeaningoftheword.Inthesegamesplayerstaketurnsmakingmoves,allplayersobserveallpastmoves,nothingisrandom,andthegameendsaftersome?xednumberofmovesorless.Wewillpresentsomeexamplesandthende?nethisclassofgamesformally.

2.1Tic-Tac-Toe

Twopeopleplaythefollowinggame.Athree-by-threesquaregridisdrawnonapieceofpaper.The?rstplayermarksasquarewithan“x”,thenthesecondplayermarksasquarefromthoseleftwithan“o”,etc.Thewinneristhe?rstplayertohavemarksthatformeitherarow,acolumnoradiagonal.

Doesthe?rstplayerhaveastrategythatassuresthatshewins?Whataboutthesecondplayer?

2.2TheSweetFifteenGame

Twopeopleplaythefollowinggame.Therearecardsonthetablenumberedonethroughnine,facingup,andarrangedinasquare.The?rstplayermarksacardwithan“x”,thenthesecondplayermarksacardfromthoseleftwithan“o”,etc.Thewinneristhe?rstplayertohavethreecards(outofthethreeormorethattheyhavepicked)thatsumtoexactly?fteen.

Doesthe?rstplayerhaveastrategythatassuresthatshewins?Whataboutthesecondplayer?

2.3Chess

Weassumethestudentsarefamiliarwithchess,butthedetailsofthegamewill,infact,notbeimportant.Wewillchoosethefollowing(non-standard)rulesfortheendingofchess:thegameendseitherbythecapturingofaking,inwhichcasethecapturingsidewinsandtheotherloses,orelseinadraw,whichhappenswhenthereaplayerhasnolegalmoves,ormorethan100turnshaveelapsed.

Assuch,thisgameshasthefollowingfeatures:

?Therearetwoplayers,whiteandblack.

?Thereare(atmost)100timesperiods.

?Ineachtimeperiodoneoftheplayerschoosesanaction.Thisactionisobservedbytheotherplayer.

?Thesequenceofactionstakenbytheplayerssofardetermineswhatactionstheactiveplayerisallowedtotake.

9

?Everysequenceofalternatingactionseventuallyendswitheitheradraw,oroneoftheplayerswinning.

Wesaythatwhitecanforceavictoryif,foranymovesthatblackchooses,whitecanchoosemovesthatwillendinitsvictory.Zermeloshowedin1913[

34

]thatinthegameofchess,asdescribedabove,oneofthefollowingthreeholds:

?Whitecanforceavictory.

?Blackcanforceavictory.

?Bothwhiteandblackcanforceadraw.

Wewillprovethislater.

Exercise2.1.Thesametheoremappliestotic-tac-toe.Whichofthethreeholdsthere?

10

2.4De?nitionof?niteextensiveformgameswithperfectinforma-

tion

Ingeneral,anextensiveformgame(withperfectinformation)GisatupleG=(N,A,H,P,{ui}i∈N)where

1.Nisa?nitesetofplayers.

2.Aisa?nitesetofactions.

3.Hisa?nitesetofallowedhistories.ThisisasetofsequencesofelementsofAsuch

thatifh∈Htheneverypre?xofhisalsoinH.eachh=(a1,a2,...,an)isaseriesofallowedlegalmovesinthegame.

4.ThesetofterminalhistoriesZ?HisthesetofsequencesinHthatarenotsubse-quencesofothersinH.ThusZisthesetofhistoriesatwhichthegameends.NotethatwecanspecifyHbyspecifyingZ;HisthesetofsubsequencesofsequencesinZ.

5.PisafunctionfromH\ZtoN.WhenP(h)=ithenitisplayeri’sturntoplayafterhistoryh.

6.Foreachplayeri∈N,uiisafunctionfromtheterminalhistoriestoR.Thenumberui(h)istheutilitythatplayeriassignstotheterminalhistoryh.Playersareassumedtopreferhigherutilities.Notethatthenumbersthemselvesdonotmatter(fornow);onlytheirorderingmatters.

WedenotebyA(h)theactionsavailabletoplayerP(h)afterhistoryh:

A(h)={a∈A:ha∈H}.

Astrategyforplayeriisamapσifromtheset{h∈H:P(h)=i}ofhistorieshatwhichP(h)=itothesetofactionsA.Astrategypro?les={si}i∈Nconstitutesastrategyforeachplayer.Givenastratgypro?leweknowhowplayersaregoingtoplay,andwedenotebyh(s)thepathofplay,i.e.,thehistorythatisrealized.Wealsodenotebyui(s)theutilitythatplayerirecievesunderthishistory.

2.5Theultimatumgame

Intheultimatumgameplayer1makesanoffera∈{0,1,2,3,4}toplayer2.Player2eitheracceptsorrejects.Ifplayer2acceptsthenshereceivesadollarsandplayer1receives4?adollars.If2rejectsthenbothgetnothing.Thisishowthisgamecanbewritteninextensiveform:

1.N={1,2}.

2.A={0,1,2,3,4,a,r}.

11

3.Z={0a,1a,2a,3a,4a,0r,1r,2r,3r,4r}.

4.O={(0,0),(0,4),(1,3),(2,2),(3,1),(4,0)}.Eachpaircorrespondstowhatplayers1re-ceivesandwhatplayer2receives.

5.Forb∈{0,1,2,3,4},u1(ba)=4?b,u2(ba)=bandu1(br)=u2(br)=0.

6.P(Φ)=1,P(0)=P(1)=P(2)=P(3)=P(4)=2.

Astrategyforplayer1isjustachoiceamong{0,1,2,3,4}.Astrategyforplayer2isamapfrom{0,1,2,3,4}to{a,r}:player2’sstrategydescribeswhetherornotsheacceptsorrejectsanygivenoffer.

Remark2.2.Acommonmistakeistothinkthatastrategyofplayer2isjusttochooseamong{a,r}.Butactuallyastrategyisacompletecontingencyplan,whereanactionischosenforeverypossiblehistoryinwhichtheplayerhastomove.

2.6Equilibria

Givenastrategypro?les={si}i∈N,wedenoteby(s?i,s)thestrategypro?leinwhichi’sstrategyischangedfromsitosandtherestremainthesame.

Astrategypro?les*isaNashequilibriumifforalli∈Nandstrategysiofplayeriitholdsthat

i,si)≤ui(s*).

Whensistheequilibriumh(s)isalsoknownastheequilibriumpathassociatedwiths.

Example:intheultimatumgame,considerthestrategypro?leinwhichplayer1offers3,andplayer2accepts3or4andrejects0,1or2.Itiseasytocheckthatthisisanequilibriumpro?le.

2.7Thecentipedegame

Inthecentipedegametherearentimeperiodsand2players.Theplayersalternateinturns,andateachturneachplayercaneitherstop(S)orcontinue(C),exceptatthelastturn,wheretheymuststop.Now,thereisapiggybankwhichinitiallyhasinit2dollars.Inthebeginningofeachturn,thisamountdoubles.Ifaplayerdecidestostop(whichshemustdoinperiodn),sheisawardedthreefourthofwhat’sinthebank,andtheotherplayerisawardedtheremainder.Ifaplayerdecidestocontinue,theamountinthebankdoubles.

Hence,inperiodm,aplayerisawarded3

4·2·2mifshedecidedtostop,andtheotherplayer

4·2·2m.

isgiven1

m=1

m=2

m=3

m=4

m=5

m=6

m=7

m=8

m=9

3

2

12

8

48

32

192

128

768

512

player1

1

6

4

24

16

96

64

384

256

1536

player2

12

Exercise2.3.De?nethecentipedegameformally,forn=4.Howmanystrategiesdoeseachplayerhave?MakesureyouunderstandRemark

2.2

beforeansweringthis.

Exercise2.4.Showthatthestrategypro?leinwhichbothplayersplaySineverytimeperiodisanequilibrium.

Theorem2.5.IneveryNashequilibrium,player1playsSinthe?rstperiod.

Proof.Assumebycontradictionthatplayer1playsCinthe?rstperiodundersomeequi-libriums.Thenthereissomeperiodm>1inwhichSisplayedforthe?rsttimeontheequilibriumpath.ItfollowsthattheplayerwhoplayedCinthepreviousperiodisawarded

period,

·2·2m.Butshecouldhavebeenawarded=·2·2mbyplayingSintheprevious

andthereforesisnotanequilibrium.

13

2.8Subgamesandsubgameperfectequilibria

AsubgameofagameG=(N,A,H,P,{ui}i∈N)isagamethatstartsafteragiven?nitehistoryh∈H.Formally,thesubgameG(h)associatedwithh=(h1,...,hn)∈HisG(h)=(N,A,Hh,P,{ui}i∈N),where

Hh={(a1,a2,...):(h1,...,hn,a1,a2,...)∈H}.

ThefunctionsPanduiareasbefore,justrestrictedtotheappropriatesubdomains.

AstrategysofGcanlikewiseusedtode?neastrategyshofG(h).Wewilldropthehsubscriptswheneverthisdoesnotcreate(toomuch)confusion.

AsubgameperfectequilibriumofGisastrategypro?les*suchthatforeverysubgameG(h)itholdsthats*(moreprecisely,itsrestrictiontoHh)isaNashequilibriumofG(h).WewillproveKuhn’sTheorem,whichstatesthatevery?niteextensiveformgamewithperfectinformationhasasubgameperfectequilibrium.WewillthenshowthatZermelo’sTheoremfollowsfromKuhn’s.

Asanexample,considerthefollowingColdWargameplayedbetweentheUSAandtheUSSR.First,theUSSRdecideswhetherornottostationmissilesinCuba.Ifitdoesnot,thegameendswithutility0forall.Ifitdoes,theUSAhastodecideiftodonothing,inwhichcasetheutilityis1fortheUSSRand-1fortheUSA,ortostartanuclearwar,inwhichcasetheutilityis-1,000,000forall.

Exercise2.6.Findtwoequilibriaforthisgame,oneofwhichissubgameperfect,andonewhichisnot.

Exercise2.7.Findtwoequilibriaoftheultimatumgame,oneofwhichissubgameperfect,andonewhichisnot.

Animportantpropertyof?nitehorizongamesistheonedeviationproperty.Beforeintroducingitwemakethefollowingde?nition.

Letsbeastrategypro?le.Wesaythatsisapro?tabledeviationfromsforplayeriat

historyhifsisastrategyforthesubgameGsuchthatui(s?i,s)>ui(s).

Notethatastrategypro?lehasnopro?tabledeviationsifandonlyifitisasubgameperfectequilibrium.

Theorem2.8(Theonedeviationprinciple).LetG=(N,A,H,P,{ui}i∈N)bea?niteextensiveformgamewithperfectinformation.Letsbeastrategypro?lethatisnotasubgameperfectequilibrium.Therethereexistssomehistoryhandapro?tabledeviations-iforplayeri=P(h)inthesubgameG(h)suchthats-i(k)=si(k)forallk=/h.

Proof.Letsbeastrategypro?lethatisnotasubgameperfectequilibrium.Thenthereisa

subgameG(h)andastrategysforplayeri=P(h)suchthatsisapro?tabledeviationfori

inG(h).Denotes′=(s?i,s),andnotethatui(s′)>ui(s).Lethbeahistorythatismaximal

14

inlengthamongallhistorieswiththisproperty.Letibegivenbys-i(k)=si(k)forallk=/h,

ands-i(h)=s(h).Bythemaximaldepthpropertyofhwehavethatiisstillapro?table

deviation,sinceotherwiseiwouldhaveapro?tabledeviationinsomesubgameofG(h).Wethushavethats-iisapro?tabledeviationforG(h)thatdiffersfromsiinjustonehistory.

2.9Thedollarauction

Twoplayersparticipateinanauctionforadollarbill.Player1actsintheoddperiods,andplayer2intheevenperiods.Bothplayersstartwithazerobid.Ineachperiodtheplayingplayercaneitherstayorquit.Ifshequitstheotherplayergetsthebill,bothpaythehighesttheyhavebidsofar,andthegameends.Ifshestays,shemustbid10centshigherthantheotherplayer’slastbid(exceptinthe?rstperiod,whenshemustbid5cents)andthegamecontinues.Ifoneofthebidsexceeds100dollarsthegameends,thepersonwhomadethehighestbidgetsthedollar,andbothpaythehighesttheyhavebidsofar.Soassumingbothplayersstay,inthe?rstperiodthe?rstplayerbids5cents.Inthesecondperiodthesecondplayerbids15cents.Inthethirdperiodthe?rstplayerbids25cents,etc.

Exercise2.9.Doesthisgamehaveequilibria?Subgameperfectequilibria?

15

2.10Backwardinduction,Kuhn’sTheoremandaproofofZermelo’sTheorem

LetG=(N,A,H,P,{ui}i∈N)beanextensiveformgamewithperfectinformation.RecallthatA(Φ)isthesetofallowedinitialactionsforplayeri=P(Φ).Foreachb∈A(Φ),letsG(b)besomestrategypro?leforthesubgameG(b).Givensomea∈A(Φ),wedenotebysathestrategypro?leforGinwhichplayeri=P(Φ)choosestheinitialactiona,andforeach

actionb∈A(Φ)thesubgameG(b)isplayedaccordingtosG(b).Thatis,s(Φ)=aandfor

everyplayerj,b∈A(Φ)andbh∈H\Z,s(bh)=s(b)(h).

Lemma2.10(BackwardInduction).LetG=(N,A,H,P,{ui}i∈N)bea?niteextensiveformgamewithperfectinformation.Assumethatforeachb∈A(Φ)thesubgameG(b)hasasub-gameperfectequilibriumsG(b).Leti=P(Φ)andletabeamaximizeroverA(Φ)ofui(sG(a)).ThensaisasubgameperfectequilibriumofG.

Proof.Bytheonedeviationprinciple,weonlyneedtocheckthatsadoesnothavedeviationsthatdifferatasinglehistory.Soletsdifferfromsaatasinglehistoryh.

Ifhistheemptyhistorythens=sG(b)forb=si(Φ).Inthiscaseui(sa)>ui(s)=ui(sG(b)),bythede?nitionofaasthemaximizerofui(sG(a)).

Otherwise,hisequaltobh′forsomeb∈A(Φ)andh′∈Hb,andui(s)=ui(s).ButsincesaisasubgameperfectequilibriumwhenrestrictedtoG(b)therearenopro?tabledeviations,

andtheproofiscomplete.

Kuhn[

22

]provedthefollowingtheorem.

Theorem2.11(Kuhn,1953).Every?niteextensiveformgamewithperfectinformationhasasubgameperfectequilibrium.

GivenagameGwithallowedhistoriesH,denotebyl(G)themaximallengthofanyhistoryinH.

ProofofTheorem

2.11.

Weprovetheclaimbyinductiononl(G).Forl(G)=0theclaimisimmediate,sincethetrivialstrategypro?leisanequilibrium,andtherearenopropersubgames.AssumewehaveprovedtheclaimforallgamesGwithl(G)<n.

Letl(G)=n,anddenotei=P(Φ).Foreachb∈A(Φ),letsG(b)besomesubgameperfectequilibriumofG(b).Theseexistbyourinductiveassumption,asl(G(b))<n.

Leta*∈A(Φ)beamaximizerofui(sa*).ThenbytheBackwardInductionLemmasa*isasubgameperfectequilibriumofG,andourproofisconcluded.

GivenKuhn’sTheorem,Zermelo’sTheorem,asstatedbelow,admitsasimpleproof.

Theorem2.12(Zermelo).LetGbea?niteextensiveformgamewithtwoplayersandwhereu1=?u2andu1(h)∈{?1,0,1}.Thenexactlyoneofthefollowingthreehold:

1.Thereexistsastragegysforplayer1suchthatu1(s,s2)=1forallstrategiess2of

player2.

16

2.Thereexistsastragegysforplayer2suchthatu2(s1,s)=1forallstrategiess1of

player2.

3.Thereexiststrategiess,sforplayers1and2suchthatu1(s,s2)≥0andu2(s1,s)≥0

forallstrategiess1,s2ofplayers1and2.

Proof.Lets*beasubgameperfectequilibriumofany?niteextensiveformgamewithtwoplayersandwhereu1=?u2andu1(h)∈{?1,0,1}.Considerthesethreecases.Ifu1(s*)=1thenforanysB

u2(s,s2)≤u2(s*)=?1.

Butu2≥?1,andsou2(s,s2)=?1.Thatis,player1canforcevictorybyplayings.The

sameargumentshowsthatifu2(s*)=1thenblackcanforcevictory.Finally,ifu1(s*)=0thenforanys2

u2(s,s2)≤u2(s*)=0,

sou2(s,s2)iseither0or?1.Bythesameargumentu1(s1,s)iseither0or?1foranys1,

andsowehaveproventheclaim.

17

3Strategicformgames

3.1De?nition

Agameinstrategicform(ornormalform)isatupleG=(N,{Si}i∈N,{ui}i∈N)where

?Nisthesetofplayers.

?Siisthesetofactionsorstrategiesavailabletoplayeri.WedenotebyS=niSithesetofstrategypro?les.

?Thefunctionui:S→Risplayeri’sutility(orpayoff)foreachstrategypro?le.

Wewillassumethatplayershavetheobviouspreferencesoverutility:moreispreferedtoless.WesaythatGis?niteifNis?niteandSis?nite.

3.2Nashequilibria

Givenastrategypro?les,apro?tabledeviationforplayeriisastrategytisuchthat

ui(s?i,ti)>ui(s?i,si).

Astrategypro?lesisaNashequilibriumifnoplayerhasapro?tabledeviation.ThesearealsocalledpureNashequilibria,forreasonsthatwewillseelater.Theyareoftenjustcalledequilibria.

3.3Classicalexamples

?Extensiveformgamewithperfectinformation.LetG=(N,A,H,P,{ui}i∈N)beanextensiveformgamewithperfectinformation,where,insteadoftheusualout-comesandpreferences,eachplayerhasautilityfunctionui:Z→Rthatassignsherautilityateachterminalnode.LetG′bethestrategicformgamegivenbyG′=(N′,{Si}i∈N,{ui}i∈N),where

–N′=N.

–SiisthesetofG-strategiesofplayeri.

–Foreverys∈S,ui(s)istheutilityplayerigetsinGattheterminalnodeatwhichthegamearrivewhenplayersplaythestrategypro?les.

Wehavethusdonenothingmorethanhavingwrittenthesamegameinadifferentform.Note,however,thatnoteverygameinstrategicformcanbewrittenasanextensiveformgamewithperfectinformation.

Exercise3.1.Showthats∈SisaNashequilibriumofGiffitisaNashequilibriumofG′.

18

Notethatadisadvantageofthestrategicformisthatthereisnonaturalwaytode?nesubgamesorsubgameperfectequilibria.

?Matchingpennies.Inthisgame,andinthenextfew,therewillbetwoplayers:arowplayer(R)andacolumnplayer(C).Wewillrepresentthegameasapayoffmatrix,showingforeachstrategypro?les=(sR,sC)thepayoffsuR(s),uC(s)oftherowplayerandthecolumnplayer.

H

T

HT

1,0

0,1

0,1

1,0

Inthisgameeachplayerhastochooseeitherheads(H)ortails(T).Therowplayerwantsthechoicestomatch,whiletherowplayerwantsthemtomismatch.

Exercise3.2.ShowthatmatchingpennieshasnopureNashequilibria.

?Prisoners’dilemma.

Twoprisonersarefacedwithadilemma.Acrimewascommittedintheprison,andtheyaretheonlytwowhocouldhavedoneit.Eachprisonerhastomakeachoicebetweentestifyingagainsttheother(andthusbetrayingtheother)andkeepinghermouthshut.Intheformercasewesaythattheprisonerdefected(i.e.,betrayedtheother),andinthelattershecooperated(withtheotherprisoner,notwiththepolice).

Ifbothcooperate(i.e.,keeptheirmouthsshut),theywillhavetoservetheremainderoftheirsentences,whichare2yearseach.Ifbothdefect(i.e.,agreetotestifyagainsteachother),eachwillserve3years.Ifonedefectsandtheothercooperates,thedefectorwillbereleasedimmediately,andthecooperatorwillserve10yearsforthecrime.

Assumingthataplayer’sutilityisminusthenumberofyearsserved,thepayoffmatrix