Comments welcome

-BoundedRationalityandInduction

UweDulleck¤yCommentswelcome

Abstract

InRubinstein´s(19)E-mailgamethereexistsnoNashequilib-riumwhereplayersusestrategiesthatconditionontheE-mailcom-munication.InthispaperIrestricttheutilizableinformationforoneplayer.IshowthatincontrasttoRubinstein´sresult,inapayo¤dominantNashequilibriumplayersusestrategiesthatconditiononthenumberofmessagessent.Therefore-inductionundertheas-sumptionofboundedrationalbehaviorofatleastoneplayerleadstoamoreintuitiveequilibriumintheE-mailgame.

Keywords:Induction,SubgamePerfectEquilibrium,Information

sets,ImperfectrecallJELClassi󰂅cation:C72

HumboldtUniversity,InstituteofEconomicTheory,SpandauerStr.1,D-10178Berlin,Germany,Ph.:+49-30-20935657,Fax.:+49-30-20935619,e-mail:dulleck@wiwi.hu-berlin.dey

IamgratefulforhelpfulcommentsbyJörgOechssler,UlrichKamecke,ElmarWolf-stetterandseminarparticipantsatUniversityCollegeLondon.FinancialsupportbytheDeutscheForschungsgesellschaft(DFG)throughSFB373isgratefullyacknowledged.

¤1

1Introduction

InhisElectronicMailgameRubinstein(19)󰀱illustratesthedi¤erencebe-tweencommonknowledgeand󰂔almostcommonknowledge󰂔.Usinghisex-ampleIillustrateanotherpuzzlinge¤ectontheequilibriumbehaviorofthisgamebyapplyinganotionofimperfectrecalltothemodel.Ishowthatboundedrationalbehaviorinthisgamealmostreestablishestheequilibriumthatexistsundercommonknowledgeandfullrationality.

IntheElectronicMailgametwoplayerseitherplayagameGa(with

1probability(1¡p)>2)orGb(withprobabilityp<1).Ineachgameplayers2choosebetweenactionAandB.Inbothgamesitismutuallybene󰂅cialforplayerstochoosethesameaction.Figure1describesthegame.Ingamea(b)theParetodominantequilibriumistheonewhereplayerscoordinateonA(B).Ifplayerschosedi¤erentactionstheplayerwhoplayedBispunishedby¡Lregardlessofthegameplayed.Theotherplayergets0.ItisassumedthatthepotentiallossLisnotlessthanthegainMandbotharepositive.

Figure1:TheEmailGame

Onlyplayer1isinformedaboutthegamethatisactuallyplayed.Afterthestateoftheworldisdeterminedtwomachines(oneforeachplayer)com-municateaboutthegame.Ifgamebprevails,player1´smachinesendsan

󰀱OsborneandRubinstein(1994)containsatextbookpresentationoftheproblem.

2

E-mailmessage(abeep)toplayer2´smachinewhichisautomaticallycon-󰂅rmed.Thiscon󰂅rmationiscon󰂅rmedandsoon.Witha󰂔small󰂔probability\"amessagegetslost.Communicationstops,whenoneofthemessages(theoriginalmessageoroneofthecon󰂅rmations)islost.Playersareinformedhowmanymessagestheirmachinesenttotheotherplayer.Thentheyhavetomaketheirdecision.

TheElectronicMailgamerepresentsaslightdeviationfromcommonknowledge(󰂔almostcommonknowledge󰂔inRubinstein´sterms).Combinedwithperfectrationalitythisleadstodiscontinuousdropinexpectedpayo¤s.Paradoxicallyinthiscasethegamehasanequilibrium,whereplayersneverplaythepayo¤dominantequilibriuminonegame(b)evenifmanymessagesweresent.

ThepointImakeisthatbyreducingtheabilitytoprocessinformationtheexistenceofanadditionalsubgameperfectequilibriumisguaranteed.TheextensionIproposeisthataplayercannotdistinguishamongtheelementsinacertainsetofnumbers,i.e.hecannotdistinguishwetherT;T+1;:::;T+lmessagesweresent.Ifasu¢cientnumberofmessagesissent,playersinthisnewequilibriumcoordinateonthepayo¤dominantequilibriuminbothgamesandthereforethatequilibriumParetodominatesanequilibriumwhereplayersdonotplaythepayo¤dominantequilibrium.

AsinrelatedworkbyDulleckandOechssler(1996)theE-mailgameisanexamplewhereinductionunderboundedrationalityleadstodi¤erentresults.Thereforethehypothesisimpliedbyexperimentaldatathatagentsdonotuseinductioncorrectly ,maybeduetothefactthattheyfacelimitationsonutilizableinformationwhichareduetoboundedrationality.TheE-mailgameshowsthatagentsmightuseinductioncorrectlybutinadi¤erenten-vironment.

Onefurtherresultfollowsfromthemainresultsofthepaper:

Giventhefollowingdescendingorderofthequalityoftheinformationalstructure:󰂔commonknowledge󰂔,󰂔almostcommonknowledge󰂔,󰂔almostcom-monknowledgeandnon-distinguishability󰂔,and󰂔noknowledgeatall󰂔theexpectedpayo¤oftheequilibriumunderthedi¤erentregimesvarynon-monotonically.Thisisincontrasttoresultspresentedintheeconomiclit-eraturewhereeitherknowinglessaboutacharacteristicofthestateoftheworldisanadvantagebutthenknowingevenlessusuallydoesnotworsenthe

McKelveyandPalfrey(1992)andRosenthal(1981)amongotherspresentexperimentsonthecentipedegamethatimplythishypothesis.

3

outcomeforaplayer.Orinothercases,knowingmoreisbetterbutusuallyknowingevenmoredoesnotworsentheresult.Notetheadditionalreduc-tionIproposeisinthesame󰂔dimension󰂔asthereductioninRubinstein´soriginalcontribution.

TheproposedargumentcanalsobeappliedtosolvetherelatedparadoxoftheCoordinatedAttackproblem(seee.g.inFaginetal(1995),Chapter6).

2

TheElectronicMailGameanditsexten-sion

UsingthenotationofRubinstein(19)thefeasiblestatessoftheworldarerepresentedasatripleconsistingofthegameactuallyplayedandthenumberofmessagessentbyplayer1andbyplayer2,i.e.s2f(a;0;0);(b;1;0);(b;1;1);(b;2;1);(b;2;2);:::(b;T1;T2):::g.T1andT2arethenumbersobservedbyplayer1andplayer2respectively,T22fT1¡1;T1g.Forsimplicityofno-tationIwillonlyuseapairconsistingofthenumbersofmessagessent.WemustbeingamebifandonlyifT1¸1.Herebyweruleoutthatthemachineofplayer1failstosendamessagealthoughweareinstateb.Notehoweverthatwedonotruleoutthatthismessagegetslost.

Figure2givesagraphicalrepresentationofthisgame,wheretheauto-maticmoves(bynature)ofthemachinesarerepresented.The󰂔outcomes󰂔arethenumbersplayersobservebeforemakingtheirdecisions.

Figure2:Information󰂔Outcomes󰂔oftheemailgame

4

InRubinstein´sgame,player1cannotdistinguishbetweenthe󰂔out-comes󰂔(T1;T1¡1)and(T1;T1)(andplayer2cannotdistinguishbetweenthestates(T2;T2)and(T2+1;T2)).InthiscasehealwaysonlyobservesT1(T2).Aplayerchooseshisstrategyconditionedonthenumberofmessagessentbyhismachine.Astrategywillbeplayedintwostatesoftheworld-thetwostatesweretheplayeriobservesthatTimessagesweresentbyhismachine.Hehastobuildbeliefsaboutwhichinformational󰂔outcome󰂔istheactualone.

TheextendtheE-mailgamebyaddingnon-distinguishabilityofnum-bers.Intheextendedsetuponeplayerisnotabletodistinguishthenumberst2fT;T+1;:::;T+lgwherel2N.Thisinformationstructureiscom-monknowledge.Irefertothisversionastheextendedgame.Otherwisetheplayersplaythegameasitisdescribedabove.

Thenon-distinguishabilityrepresentsthecasewhereaplayercannotob-serveorinterprettheinformationaboutthenumberofmessagessentiftheybelongtotheinterval[T;T+l].Thismightbeduetothefactthatheisnotabletodistinguishthenumbers(interpretthenumbersintherightway)orthatthemachineisnotabletoshowdi¤erentsymbolsiftisinthecriticalinterval.

Thismodi󰂅cationseemstobeobviousgivenl!1,whichisthecasewherethemachineortheplayerlosetrackatstageT.Justi󰂅cationsforthisassumptioncouldbethe󰂔over󰂇ow󰂔ofthemachine´scapacities(itcanonlycountuptoacertainnumber)orthatrealplayersactuallystopcountingaftertheysentacertainnumberofmessages.TheresultinthiscaseisidenticaltoRubinstein´s(19)problemwherethemaximumnumberofmessagestobesentislimited.Ishowthattheweakerconditionthatplayerscannotdistinguishbetweensomestatesisenoughtoyieldasubgameperfectequilibriumwithcoordination.Thisweakerconditionmaybeduetominorproblemsintheprocessingofinformation,e.g..aplayercanonlyobserveevennumbers.

Languagedi¤erencesmaybeareasonwhyaplayercannotdistinguishbetween,letussay,17and18(e.g..hemaybeunsureoftherightorderof17and18)!.Orthemachinemaynotbeabletoshow18andthereforeitstayson17fortwoturnsandthenjumpsto19.\"

AssumethatoneplaystheEmailgameinChinausingtraditionalchinesenumbers(whichweretaughtbefore)-Iamsureonewouldgetconfusedinterpretingthesymbols.\"

Theproposedlogiccanalsobeappliedtoasituationwhereoneorbothplayerscounteg.onlyevennumbers.Necessaryforthepresentresultsisthattheinformationsets

!

5

Giventhismodi󰂅cationofnon-distinguishabilityonehasaproblemwhichanalysisissimilartothatoftheproblemofimperfectrecall#inthesensethataplayerforgetshowmanybeepshehasheardormessagedhereceivedbeforebutheisremindedonceinawhileabouttheactualnumber.Theplayercannotdistinguish/rememberwhetherhismachinesentT;T+1;:::orT+lmessagesandthereforehehastochooseoneactionforallobservationsintheinterval.

3Results

Intheoriginalgame,Rubinstein(19)provesthatthereisnoNashequi-libriumwhereplayersconditiononthenumberofmessagessent:

Proposition1(Rubinstein(19))ThereisonlyoneNashequilibriuminwhichplayer1playsAingameGa.InthisequilibriumplayersplayAindependentlyofthenumberofmessagessent.

TheformalproofisprovidedinRubinstein(19).

Thebasicideaoftheproofisthatinstates(0;0)and(1;0)theobviousequilibriumis(A;A)-givenp<1.Usingthisasthestartofaninduction,2onehasthatuptotheobservationofT¡1foreachplayeritisoptimaltoplay

\"tobeatthe󰂅rstoftwoindistinguishableA:Theconsistentbeliefz=\"+\"(1¡\")󰂔outcomes󰂔(T;T¡1)and(T;T)forplayer1[or(T¡1;T¡1)and(T;T¡1)

1.Giventhestatedbeliefandthatuptostateforplayer2]isgreaterthan2(T¡1;T¡1)[or(T;T¡1)forplayer2]thebestreplyoftheotherplayerisA,itisabestaanswertochooseAiftheinformationsetisreachedbecausethisdecisionisindependentofthestrategyoftheotherplayeratthesecondindistinguishable󰂔outcome󰂔intheinformationset.ByinductionthisistrueforeveryobservedT.

are󰂔divided󰂔bythecorrespondinginformationsetsoftheotherplayerinawaythatthe󰂅rstpart(thestatesthatareinthecorresponding󰂅rstinformationsetoftheotherplayer)issmallerthantherestoftheinformationset.ThereforethenextinformationalstructurethatwouldyieldtheRubinsteinresultiswherebothplayercannotdistinguishthreesucceedingnumbersandtheinformationsetsoverlapexactlythewaythatineachsetthree󰂔outcomes󰂔areineachofthecorrespondingsetsoftheotherplayer.#

PiccioneandRubinstein(1996)andAumannetal.(1996)inadditiontoaspecialissueofGamesandEconomicBehavior1996(forthcoming)covertheproblemofimperfectrecallinanexampleofanabsent-mindeddriver.AnapplicationtothecentipedegamecanbefoundinDulleckandOechssler(1996).

6

Thefollowingpropositionstatesthemainresultsofthepaperfortheextendedgamewhereoneplayersu¤ersfromnon-distinguishability.

Proposition2IfLisnottoolargerelativetoMthenthereexistsaNashequilibriumsuchthatbothplayersplayBiftheirmachinesentt¸Tmes-sagesandAinallothercases,givenoneplayersu¤ersfromnon-distinguishabilitydistinguishamongthet2fT;T+1;:::;Tdistinguishtheresultamonggivenplayerthet12su¤ersfT;T+from1;non-distinguishabilitytheweproceedasinRubinstein:::;(19)ToftheoftheargumentworldwhereaboveortazA=󰂔outcome󰂔22l+1\"(1¡\")i

to(T;beTat¡1)󰂔outcome󰂔fromi=0

\"Aforsureinthespeci󰂅edequilibrium.ofplayingplayer+lgreply2B.

by(toisplayerplayoptimalBatthisinformation2ifishetoobservesplayBwheneverat¸T).playBwhenevertheyobserveat2fT;areintheydosofort>T+l.At󰂔outcome󰂔(TTtwosenttheisinformationtoplayBgivensetwherethestrategyheobservesoflgdistinguishindistinguishable󰂔outcomes󰂔inthistheinformationthesuccessorsbelieftobetween󰂔outcomes󰂔whereisbeagainat󰂔outcome󰂔zA.The(sameT;T)insteadtheplayercase1thatsu¤ersonefromnon-distinguishability.

argumentg.Withoutlossatoftheplayersu¤ersonlywithLetgeneralityperiodszA=Iwhereheobserve22l+1\"assume.thatplayeri=0

\"(1¡\")i

7

lg:

lupg.Toshowthetoreplyformal󰂔out-to2(lT;+T1¡suc-1)1¡zAzAM=

22l+1givenithe

=1

observesplayertl;+1:::;any;TT++lg,playert¸l)observesset.oftappliesoneofprobabilityoneanymay

t2suchthathecannot+Proof.Firstweproofsuchthathecannot+thatthisisanequilibrium,come󰂔(T;T¡1).Seeforproof.ForanystatebestplayAregardlessIfPlayer1cannotitscessorsheformswhereplayer2playsIf

i

(1¡\")>Lthensetspeci󰂅edstrategyGiven1´sstrategythebesthe2fT;T+1;:::;TGiventhatplayers+1inductionimpliesthat+player1´sbestreplythatT+l+1messagesotherwhoplaysBattheIfplayer2cannothe2fT;T+1;:::;T+thenon-distinguishableasinthecasewhereNextIanalyseaof´fromnon-distinguishabilityfT;T+1;:::;T+lsu¤erfromnon-distinguishability.(2¡\")MzAProposition3If1¡M>Land(1¡´)·thenthereexistsaNashzAM+LequilibriumwherebothplayersplayBwhenevertheyobserveat¸T+1givenplayer1su¤erswithprobability´fromnon-distinguishabilitysuchthathecannotdistinguishamongthet2fT;T+1;:::;T+lg:ForM=Lthis

\".impliesthatsuchanequilibriumexistsif´¸12fersThefollowingstrategiesaretheequilibriumotherwise.fromnon-distinguishabilityBIfplayerhechoosesobserveswheneverheobserves1doesatnot>Tsu¤erandgivenProof.theastatedt¸TrestrictionsandAotherwise.onMIcome󰂔proposition(TI¡proof1;T¡that1)thethestrategiesstrategies,LfollowarehisIfplayer1.

1su¤ersfromnon-distinguishabilityheobservesdoesbestnotreplysu¤erisgivenfromasnon-distinguishabilitydescribedgivenobservesplayaTtis>toTplayAbytheargumentset.Banswers.

Thereforebecausegivenplayerthengiventhe2playsthestrategyBstatedatbothofheobservesGiventhethatstrategyexactlyofplayerTmessages1thepayo¤´M+(1¡´)(z(wherez=\"of(T+1;T).Player\"+\"(1¡\"2)istheconsistent´spayo¤is0ifheif(1)Bquestion.

becauseGiven¸0.theThisisequivalentto(1¡´)playerobservation1choosesofBanyattboth>TForlargeThereforeM=Lgiventhecondition(1¡´)aNashenoughequilibriumcomparedthewheretoprobabilitythetoplayersprobabilityconditionBifinhequestion:observesotherwise.non-distinguishability,Playerbest´proof.

thatthisfromreplytheargumentstrategies.thestatedpropositioninthehisbeststrategyreplyoftheofproofplayerof2propositionhis2󰂔outcomes󰂔player1´sstrategiesinbeentoplayersent2isifgivenheL)+(1¡z)M)

beliefthatthestatechooses(2

¡\")M

A:ThereforebyM+Lasstatedin󰂔outcomes󰂔player2hisinbesttheinformation(2¡\")Msu¤erM+Lsimpli󰂅esthatfromnon-distinguishabilitytoonathemessagenumbergetstPlayer¸heTchoosesand1suf-AequilibriumBifheUpthetoproof󰂔out-ofensurestoplayerthatwhere2.If1.IfheinformationreplyishetoarebestBwhenever(1)

T;T)insteadabestreply

proposition.istochoosesetin12\".thereexistsissent.

IfafromA2chooseswillisanandin2ofupstrategybesthisplayerplayshaveby

¡is(Bisthe·reply·´¸lostofmessages8

Note,givenM=Lthisprobabilitymaybein󰂅nitesimalsmallgivenasmall\".

Whenthe(potentially)non-distinguishablestatesarereacheditisopti-maltoplayB.IncontrasttoRubinstein´s(19)resultforthecasethatthenumberofmessagessentislimited(whichisequivalenttol=1)itissu¢cientthatnon-distinguishabiltyappearsonlyinearlierstages(l<1).OnceitisoptimaltoplayBatanystagetheninductionleadstotheresultthatinthesucceedingstages,playingBistheoptimalstrategy.

Inthecasewhereoneplayersu¤ersfromnon-distinguishability,playersinthepayo¤dominantequilibriumuseastrategywheretheyconditiontheiractiononthenumberofmessagessent.

Corollary1Ifoneplayersu¤ersfromnon-distinguishabilitytheoptimalstrategiesforplayerswhoobservethatexactlyTmessageshavebeensentdi¤ercomparedtothecasewithoutnon-distinguishability,giventheobservednumberofmessagessentisgreaterthenthenumberwherethenon-distin-guishabilitya¤ectstheutilizableinformation.

Therefore,thedecisionofplayersdoesnotonlydependontheinformationtheyhaveatthepointoftimewheretheyhavetotaketheirdecision.Italsodependsontheinformationavailabletothematanearlierpointintime.EventhoughthenumberplayersobserveinRubinstein´soriginalgameandthepresentedextendedversionisthesame,thebest-reply-strategiesdi¤erbecauseofaninformationalde󰂅ciencywhichcouldhavearisenatanearlierstageinthegame(butwhichactuallymightnothavehadanye¤ectontheutilizableinformation).

Corollary2Theexpectedpayo¤sinthecoordinationgamethatisthebasisfortheE-mailgamevarynon-monotonicallyintheinformationstructure.Theexpectedpayo¤undercommonknowledgeintheE-mailgameis¦=M.GivenRubinstein´s󰂔almostcommonknowledge󰂔theexpectedpayo¤is¦e=pM.Introducingnon-distinguishabilityandthereforeafurtherreductionofutilizableinformationatonlyone-pointintimeonegetslim

\"¡!0

e

¦=M.Inthecasethatonlyoneplayerisinformedofthestateoftheworldandnocommunicationtakesplace,oneisbackat¦e=pM.

e

9

4Conclusions

Rubinstein(19)employstheElectronicMailgametoillustratethatthepayo¤svarydiscontinuouslyintheassumedinformationstructure,i.e.󰂔al-mostcommonknowledge󰂔leadstodi¤erentoptimalbehaviorcomparedtotheoptimalbehaviorundercommonknowledge.Inthisgameboundedratio-nalityleadstoacontinuityintheexpectedpayo¤sifonereducesthequalityoftheavailableinformation(fromcommonknowledgeto󰂔almostcommonknowledge󰂔).Havingatonestageintimeadi¤erentoptimalstrategy,induc-tioniscarriedoutinadi¤erentwayandleadstodi¤erentoptimalbehavior.Rubinstein´scaseshowsthatknowinglessimpliesawelfaredecreaseforbothagents.Theextensionofhisgameillustratesthatknowingevenlessthanintheoriginalgamewithimperfectinformationincreaseswelfarealmosttothelevelthatisreachedundercommonknowledge.Afterall,giventheworstsituationinthisgame(nobodyoronlyplayer1knowsthestateoftheworld)wehaveagainauniqueequilibriumasunder󰂔almostcommonknowledge󰂔withthelowexpectedpayo¤s.Thereforethisisanexampleofnon-monotonicityinavailableinformation.

Anotherparadoxicalaspectofthisgameisthatevenifagentsknowthedi¤erencebetween16,17and18andtheyobserve17,theyplayBiftheycannotdistinguishbetweenletussay7and8.Alocalde󰂅ciencyininfor-mationprocessingabilitieschangestheoptimalstrategyeventhoughatthedecisionmakingpointintimetheavailableinformationisthesameasinthecasewherenolocalde󰂅ciencyexists.

References

[1]Aumann,R.J.,Hart,S.andPerry,M.(1996),󰂓TheAbsent-Minded

Driver󰂔,DiscussionPaper#94,HebrewUniversityofJerusalem(GamesandEconomicBehavior,forthcoming)[2]Dulleck,UweandOechssler,Jörg(1996),󰂔TheAbsent-MindedCen-tipede󰂔,EconomicsLetters,forthcoming[3]Fagin,Ronald,Halpern,JosephY.,Moses,Yoram,Vardi,MosheY.

(1995),󰂔ReasoningAboutKnowledge󰂔,MITPress,Cambridge[4]McKelvey,R.andPalfrey,T.(1992),󰂔Anexperimentalstudyofthe

centipedegame󰂔,Econometrica,60,p.803-836

10

[5]Osborne,MartinJ.andRubinstein,Ariel(1994),󰂔Acourseingame

theory󰂔,MITPress,Cambridge[6]Piccione,M.andRubinstein,Ariel(1996),󰂔OntheInterpretationofDe-cisionProblemswithImperfectRecall󰂔,GamesandEconomicBehavior,forthcoming[7]Rosenthal,R.(1981),󰂔Gamesofperfectinformation,predatorypricing

andchain-storeparadox󰂔,JournalofEconomicTheory,25,p.92-100[8]Rubinstein,Ariel(19),󰂔TheElectronicMailGame:StrategicBehavior

Under󰂔AlmostCommonKnowledge󰂔󰂔,AER,Vol.79,No.3,p.385-391

11