ReasoningAboutKnowledgeandProbabilityRONALDIBMAInuzdetzFAGINANDJOSEPHY.HALPERNResecrrcbCenter,SCZnJo.w,Cul[fomiaAbstroct.Weprovideamodelforrcusonmgaboutknowledgeandprob~bilitytogether,Weallowexplicitmentionofprobabilitiesinformulas,sothatourkmguagchasformu]asthatessentiallysay“accordingtoagent~,formulapholdswithprobabi]ltyatleastb“ThelangutigcISpowerfulenoughtoallowrewoningabouthigher-orderproixibdities,aswellwti]lowinge~plicltcompar-isonsoftheprobabilitiesanagentplacesondistinctevents.Wepresentageneralframcw(>rkforinterpretingsuchformulas,andconsiderwmouspropertiesthatmightholdoftheinterrclatmn-shipbetweenagents’probabilityassignmentsatdifferentstates.Wepro~,icteacompleteaxlomati-zationforreasoningaboutknowledgeandprobabihty,proveasmallmodelproperty,andobtaindecisionprocedures,Wethenconsidertheeffectsofaddingcommonknowledgeandaprobabilis-ticvariantofcommonknowledgetothelanguage.OutputandDataCommunications]:Perfor-manceAnalysisandDesignAids—@wmlmodels;~enjcation;C,2.4[Computer-CommunicationNetworks]:NetworkOperations,D.2.4[SoftwareEngineering]:ProgramVerlflcaticm;F.2[AnaIy-sisofAlgorithmsandProblemComplexity];F.3,1[LogicsandMeaningsofPrograms]’SpecifyingandVerifyingandReasoningaboutPrograms;F.4.1[MathematicalLogicandFormalLanguages],MathematlcalLogic—/?zodclfheo~y;F.4.m[MathematicalLogicandFormaILanguages]:Miscella-Representationneous;G.3[ProbabilityandStatistics]:1.2.4[ArtificialIntelligence]:KnowledgeCategoriesandSubjectDescrlptor~:B4.4[Input/FormalismsGeneralandMethodsVerificationTerms:Theory,AdditionalKeyWordsandPhrases.Knowledge,modallogic.norrdeterminismvs.probabdity,possiblewords,probabdlsticcommonknowledge,probabilisticknowledge.reasomngaboutknowl-edgeandprobability1.IntroductionReasoningresearchers[Aumann,aboutknowledgediversehasbecomefieldsintelligenceanactivetopicofinvestigation1962],forinsuchasphilosophy[Hintikka,economics[Moore,1985].Recentlytheinterestoftheoreticalcomputerscientistshasbeensparked,sincereasoningaboutknowledgehasbeenshowntobeausefultoolinanalyzingdistributedsystems(seeHalpern[1987]foranoverviewandfurtherreferences).1976],andartificialofthispaperappearedinProceedzn3softlze?ndCotlferetzceonTheorctzcalAspectsofReaso/zzrzSaboutKno}tiledge,M.Y.Vardi.ed.Morgan-Kaufmann,StinMateo.Calif,.198S,pp.277-293.Authors’address:IBMAlmadenResearchCenter,65(IHarryRoad,SanJose,CA95120.Permissiontocopywithoutfeeallorpartofthismaterialisgrantedprovidedthatthecopiesarenotmadeordistributedfordirectcommercialadvantage,theACMcopyrightnoticeandthetitleofthepublicationanditsdateappear,andnoticeisgiventhatcopyzngisbypermissionoftheAssociationforComputingMachinery.Tocopyotherwme,ortorepublish,rcqun-esafeeand/orspecificpermission.01994ACM0004-11/94/0300-0340$03.50.loumdApreliminaryversionoftheA,mcntmnforCompulIngM~ch~n.~,\\rol41.No2,MachIYW,pp?4[)-3(17ReasoningaboutKnowledgeandProbability341Inmanyoftheapplicationareasforreasoningaboutknowledge,itisimportanttobeabletoreasonabouttheprobabilityofcertaineventsaswellastheknowledgeofagents.Inparticular,thisarisesindistributedsystemsapplicationswhenwewanttoanalyzerandomizedorprobabilisticprograms.Notsurprisingly,researchershaveconsideredknowledgeandprobabilitybe-fore.Indeed,allthepublicationsineconomicsonreasoningaboutknowledge,goingbacktoAumann’sseminalpaper[Aumann,1976],haveprobabilitybuiltintothemodel.However,theydonotconsideralogicallanguagethatexplicitlyallowsreasoningaboutprobability.Inthispaper,weconsideralanguagethatextendsthetraditionallogicofknowledgebyallowingexplicitreasoningaboutprobabilityalongthelinesdiscussedinacompanionpaper[Faginetal.,1990].Inthestandardpossible-worldsmodelofknowledge(whichwebrieflyreviewifinthenextsection),agentiknowsafactp,writtenK,p,inawoddorstatespistrueinalltheworldstheagentconsiderspossibleinworlds.Wewanttoreasonnotonlyaboutanagent’sknowledge,butalsoabouttheprobabilityheplacesoncertainevents.Inordertodothis,weextendthelanguageconsid-eredin[Faginetal.,1990],whichisessentiallyaformalizationofNilsson’sprobabilitylogic[Nilsson,1986].TypicalformulasinthelogicofFaginetal.[1990]includeW(q)>2w(~)andW(q)<1/3,wherepand$areproposi-tionalformulas.Theseformulascanbeviewedassaying“pistwiceasprobableas@”and“phasprobabilitylessthan1/3”,respectively.Sincewewanttoreasonabouttheprobabilitythatagentiplacesonevents,wemodifytheirlanguagetoallowformulassuchasWi(p)>2wi(*).Wealsoallowpand@heretobearbitraryformulas(whichmaythemselvescontainnestedoccur-rencesofthemodeloperatorsw,andKj)ratherthanjustpropositionalformulas.Thisgivesusthepowertoreasonabouthigher-orderprobabilities(seeGaifman[1986]formorediscussiononthissubject,aswellasaddedreferences)andtoreasonabouttheprobabilitythatanagentknowsacertainfact.Inordertogivesemanticstosuchalanguageinthepossible-worldsframe-work,weassumethat,roughlyspeaking,ateachstate,eachagenthasaprobabilityontheworldsheconsiderspossible.Thenaformulasuchasw,(p)>2wi(*)istrueatstatesif,accordingtoagenti’sprobabilityassign-mentatstates,theeventqistwiceasprobableas@.Fortechnicalandphilosophicalreasons,wefinditconvenienttoviewtheprobabilityasbeingplacedonanarbitrarysetofworlds,ratherthanthesetofallworldsthattheagentconsiderspossibleinagivenstate.Asweshallshowbyexample,differentchoicesfortheprobabilityspaceseemtocorrespondtodifferentassumptionsaboutthebackgroundcontext.Despitetherichnessoftheresultinglanguage,wecancombinethewell-knowntechniquesforreasoningaboutknowledgewiththetechniquesforreasoningaboutprobabilityintroducedin[Faginetal.,1990]toobtainanelegantcompleteaxiomatizationfortheresultinglanguage.Justastherearedifferentassumptionswecanmakeabouttherelationshipbetweentheworldsthatagenticonsiderspossible,leadingtodifferentaxiomsforknowledge(seeHalpernandMoses[1992]foranoverview),therearealsodifferentassump-tionsabouttheinterrelationshipsbetweenagents’probabilityassignmentspacesatdifferentstates,whichalsocanbecapturedaxiomatically.Wediscusstheseassumptionsandtheirappropriateness,andshowhowtheseassumptionscaneffectthecomplexityofthedecisionprocedureforthelanguage.342R.FAGINANDJ.Y.HA[YERNThispaperisrelatedtoanumberofotherworks.Wegiveabriefoverviewoftherelatedliteraturehere.Propositionalprobabilisticvariantsoftemporallogic[HartandSharir,1984;LehmanandShelah,1982]anddynamiclogic[Feldman,1984;Kozen,1985]havealsobeenstudied,withthegoalofanalyzingprobabilisticprograms.ProbabilistictemporallogicpapershavetraditionallylimitedthelanguagesothattheonlyprobabilisticstatementsthatcanbemadeareBooleancombinationsofformulasoftheform“qoccurswithprobability1984;Kozen,1985]dobearsomeone.”Thelogicsstudiedin[Feldman,superficialresemblancetooursinthatexplicitprobabilitystatementsareallowed,aswellaslinearcombinationsofstatements.Indeed,theprobabilitylogicconsideredin[Faginetal.,1990],wheretheonlyformulasinthescopeofthemodaloperatorwarepropositionalformulas,isafragmentofFeldman’slogic.However,therearesomefundamentaldifferencesaswell,whicharisefromthefactthatthemainobjectofinterestintheseotherlogicsareprograms.Asaresult,ourlanguageandthose[Kozen,1985]areincomparable.Thelanguages[Kozen,1985]arericherthantheoneusedin[Feldman,usedin[Feldman,1984]and1984]andhereinthattheyallowexplicitreasoningaboutprograms,butpoorerinthattheycantalkabouttheprobabilityofonlyarestrictedclassofformulas.Moreover,therearesignifi-canttechnicaldifferencesinthesemanticsofknowledgeoperators(ourK,’s)andtheprogramoperatorsof[Feldman,1984]and[Kozen,1985].Aswementionedabove,probabilisticknowledgehasbeenanissueofgreatinterestintheeconomicscommunity.Althoughtheyhavenotconsideredformallanguagescontainingknowledgeandprobability,theirmodelscanbeviewedasaspecialcaseofthemodelswediscussinthispaper.Inarecentpaper[MondererandSamet,19]intheeconomicsliterature,MondererandSametinvestigateprobabilisticconmlonknowledge,atopicthatshallalsoconcernushere.Wecompareourframeworktotheirsinmoredetailwhenwediscussprobabilisticcommonknowledge.Theframeworkdevelopedinthispaperhasalsobeenappliedtodistributedsystemsandcryptographyinsomerecentpapers[FisherandZuck19S7,1988:Halpernetal.,1988;HalpernandTuttle,1993],wheretheissuesraisedherehavebeenexaminedmorecarefullyinthecontextoftheseapplicationsareas.Finally,weshouldmentiontwootherpapersthatconsiderreasoningaboutknowledgeanduncertaintyinapossibleworldsframeworksomewhatsimilartoourown.HalpernandMcAllister[19]consideralanguagethatallowsreasoningaboutknowledgeandlikelihood,buttheirnotionoflikelihood,basedonthelogicoflikelihoodof[HalpernandRabin,1987]considersonlyaqualitativenotionoflikelihood,ratherthanexplicitprobabilities.Althoughthismaybeappropriateforsomeapplications,itisnotusefu]forananalysisofprotocols.Ruspini[1987]discussescertainrelationsthatholdbetweenknowl-edgeandprobabilityintheone-agentcase.andrelatesthisinturntoDemp-ster–Shaferbeliefji{nctiom[Shafer,1976].Therestofthispaperisorganizedasfollows:Thenextsectioncontainsabriefreviewoftheclassicalpossible-worldssemanticsforknowledgeandadiscussionofhowknowledgecanbeascribedtoprocessesinadistributedsystem.InSection3,wedescribetheextendedlanguageforknowledgeandprobabilityanddiscusssomeassumptionsthatcanbeplacedontheinterrela-tionshipsbetweenagents’probabilityassignmentsatdifferentstates.InSection4,wegiveresultsoncompleteaxiomatizationsanddecisionprocedures.InweconsiderReasoningaboutKnowledgeandProbabilitySection5,weextendthelanguagetoallowcommonknowledgeticcommonknowledge.InSection6,wegiveourconclusions.343andprobabilis-2.TheStandardKripkeModelforKnowledgeInthissection,webrieflyreviewthestandardS5possible-worldssemanticsforknowledge.ThereaderisreferredtoHalpernandMoses[1992]formoredetails.Inordertoreasonformallyaboutknowledge,weneedalanguage.Supposeweconsiderasystemwithnagents,say1,....n,andwehaveanonemptysetOofprimitivepropositionsaboutwhichwewishtoreason.(Fordistributedsystemsapplications,thesewilltypicallyrepresentstatements,suchas“ThevalueofvariablexisO“;innaturallanguagesituations,theymightrepresentstatementsoftheform“ItisraininginSanFrancisco.”)Forconvenience,wedefinetruetobeanabbreviationfortheformulapv~p,wherepisafixedprimitiveproposition.Weabbreviatemtruebyfalse.Weconstructmorecomplicatedformulasbyclosingoff@underconjunction,negation,andthemodaloperatorsK,,fori=1,...,rz(whereK,qisread“agenti.knowsq“).WegivesemanticstotheseformulasbymeansofKrzpkestructures[Kripke,1963],whichformalizetheintuitionsbehindpossibleworlds.AKripkestructureforknowledge(fornagents)isatuple(S,m,%,,...,=.),whereSisasetofstates(thoughtofasstatesofaffairsorpossibleworlds),n(s)isatruthassignmenttotheprimitivepropositionsof@foreachstates=S(i.e.,T(s)(p)={true,false}foreachprimitivepropositionpG@andstatescS),and~isanequivalencerelationonthestatesofS,fori=1,...,n.The~relationisintendedtocapturethepossibilityrelationaccordingtoagenti:(s,t)~~ifinworldsagenticonsiderstapossibleworld.1Wedefine~(s)={s’1(s,s’)G%}.Wenowassigntruthvaluestoformulasatastateinastructure.Wewrite(M,s)%PiftheformulaPistrueatstatesinKripkestructureM.(M,s)I=p(M,S)KP,A+(A4,s)kTP(forpiffiffiffe@)iffm(s)(p)and=true(J4,s)I=IIJ(M,s)I=p(1’vf,s)i#q(M,t)t=P(M,s)kK,pforallt=x(s).Thelastclauseinthisdefinitioncapturestheintuitionthatagentiknowspinworld(M,s)exactlyifqistrueinallworldsthaticonsiderspossible.GivenastructureM=(S,w,%1,...,%.),wesaythataformulapisualidinM,andwriteM1=p,if(M,s)1=pforeverystatesinS,andsaythatqissatisfiableinMif(M,s)i=pforsomestatesinS.WesaythataformulapisL]alidifitisvalidinallstructures,anditissatisfiableifitissatisfiableinsomestructure.ItiseasytocheckthataformulapisvalidkM(respectively,ifandonlyifTpisnotsatisfiableinM(respectively,notsatisfiable).vakO1Wecouldtake~tobeanarbitrmybinaryrelation,butfordistributedsystemsapplications,takingittobeanequivalencerelationseemsmostappropriate(seeHalpern[19S7]forfurtherdiscussionofthispoint).Ourresultscouldeasilybemodifiedtodealwiththegeneralcmewhere~isanarbitrarybinaryrelation.344Weareoftenformulasthatinterestedincharacterizingarevalid.AnaxiomsystemAXR.FAGINANDJ.Y.HALPERNbyanaxiomsystemthesetofissaidtobesoundforalanguageY’withrespecttoaclass.%ofstructuresAXisvalidwithrespecttoeverystructureifeveryformulainl%’provableinin..#’.ThesystemAXiscompletefor3’withrespecttot?’ifeveryformulainL?thatisvalidwithrespecttoeverystructurein.d’isprovableinAX.WethinkofAXascharacterizingtheclass.//ifitprovidesasoundandcompleteaxiomatizationofthatclass.Soundnessandcompletenessprovideaconnectionbetweenthe~ntacticno-tionofprovabilityandthesemanticnotionofvalidity.Itiswellknownthatthefollowing[1962],providessetofaxiomsasoundandinferencerules,whichforandcompleteaxiomatizationgoesbacktoHintikkathelogicstructuresK1.K2.K3.K4.K5.RI.IV?.ofknowledgeforknowledgejustdefined(seeHalpernwithrespecttotheclassofandMoses[1992]foraproof).KripkeAllinstancesofpropositionaltautologies.(K,pAK,(p=+~))*K,+.K,q+(p.K,p~K,Klp.lKlq*K,TK,q.Frompandq+@infer@(modusponens).FrompinferK,q(knowledgegeneralization).WeremarkthatthisaxiomsystemforthecaseofoneagenthastraditionallybeencalledS5.Philosophershavespentyearsdebatingtheappropriatenessofthissetofaxiomsand,indeed,ofthiswholeapproachforcapturingthenotionofknowledgeasappliedtohumanreasoning(seeLenzen[1978]forareviewofthepertinentliterature).Otheraxiomsystemsforknowledgehavebeenconsid-ered.Wementiontwohere,sincetheywillariseinourlaterdiscussion:theaxiomsystemK,consistingofKl,K2,Rl,andR2,andtheaxiomsystemKD45,consistingofKl,IC2,K4,K5,RI,R2andtheaxiomTK,(j2zke).ThesystemS5hasprovedparticularlyusefulindistributedsystemsapplications.Wenowbrieflyreviewhowknowledgeisascribedtoprocessesindistributedsystems.MorediscussionanddetailsonthemodelcanbefoundinHalpern[1987].Adistributedsystemconsistsofacollectionofprocesses,say1,....n,connectedbyacommunicationnetwork.Wethinkoftheseprocessesasrunningsomeprotocol.Atanytimeintheexecutionofsuchaprotocol,thesystemisinsomeglobalstate,whichisatupleoftheform(s,,s,,....s.),whereStisthelocalstateofprocessi,andSCisthestateoftheenclironnzerzt.Wethinkoftheglobalstateasprovidinga“snapshot”ofthestateofthesystematanytime.Theenvironmentincludeseverythingthatweconsiderrelevanttothesystemthatisnotdescribedinthestateoftheprocesses.Arunofasystemisjustafunctionfromthenaturalnumberstoglobalstates.Intuitively,arundescribesapossibleexecutionofasystemovertime(wherewethinkofthetimeasrangingovernaturalnumbers).Weidentifyasystemwithasetofruns(thesecanbethoughtofasthepossiblerunsofthesystemwhenrunningaparticularprotocol).Weoftenspeakofapair(r.m),consistingofarunr-andatimem,asapoint.Associatedwithanypoint(r,m)wehaver(m),theglobalstateofthesystematthispoint.Wecandefineequivalencerelations-,,fori=1,...,n,cmpointsvia(r,m)N,(/,m’)iffprocessihasthesamelocalstateattheglobalstatesr(m)andz-’(nz’).ReasoningaboutKnowledgeandProbability345Supposewefixaset@ofprimitivepropositions.Indistributedsystemsapplications,wecanthinkofthesepropositionsassayingthingslike“thevalueofvariablexisO“,“process1’sinitialinputis3“,andsoon.WedefineaninterpretedsystemYtobeapair(~,m),whereY?isasystem(setofruns),andTisatruthassignmenttotheprimitivepropositionsof@ateverypointin9.Withthisdefinition,itiseasytoviewaninterpretedsystemasaKripkestructure,wherethepointsplaytheroleofstatesandthe~relationisgivenbyN,.Truthisnowdefinedwithrespecttoapoint(r,m)inaninterpretedsystemY.Inparticular,wehave(=,r,rn)*K,qiff(~,r’,m’)1=qforall(r’,m’)-,(r,m).suchthat(r’,m’)SinceN,isanequivalencerelation,itiseasytocheckthatalltheaxiomsofS5holdforthisinterpretationofknowledge.3.AddingProbabilityTheformulaK,psaysthatqistrueatalltheworldsthatagenticonsiderspossible.WewanttoextendourlanguagetoallowsformulassuchasWl(p)>b,whichintuitivelysaysthat“accordingtoagenti,formulaPholdswithprobabilityatleastb.”Infact,itturnsouttobeconvenienttoextendthelanguageevenfurther.Specifically,ifp,,....p~areformulas,thensoisalw,(p,)+““”+a~w,(p~)>b,whereal,...,a~,barearbitra~rationalnum-bers,andk>1.Wecallsuchaformulaani-probabilityformula(orsimplyaprobabilityfo?mula,ifwedonotwishtospecifyi).Anexpressionoftheformalwl(pl)+““.+akw,(p~)iscalledaterrrz.Allowingarbitrarytermsini-prob-abilityformulas,ratherthanjustformulasoftheformWl(p)>a,givesusagreatdealofflexibilityinexpressingrelationshipsbetweenprobabilitiesofevents.Noticewedonotallowmixedformulassuchasw,(P)+~j(~)>b.zWeuseanumberofabbreviationsthroughoutthepaperforreadability.Forexample,weusew,(q)>w,($)asanabbreviationforw,(p)–Wl(~)>0,zblandw,(~)=bforw,(p)sbfor–w,(p)>–b,w,(p)
b).Intuitively,thissaysthat“agentiknowsthattheprobabilityofpisgreaterthanorequaltob.”ItmightseemthattheformulaWI(q)>bofpisgreaterthanshouldalreadysaythat“agentiknowsthattheprobabilityorequaltob”,evenwithouttheK,operator.ThisisnotthecaseunderourofPsemantics.Inagivenstates,theformulaw,(p)denotestheprobabilityaccordingtoagentsi’sprobabilitydistributioninstates.Althoughitmayatfirstseemcounterintuitive,itisusefultoallowagentinottoknowwhatprobabilitydistributionisbeingusedtocalculatew,(p).Forexample,ifagentiknowsthatoneoftwodistributionsgovernsq,andaccordingtoone,theprobabilityofqis1/2andaccordingtotheother,theprobabilityofpis3/4,thenwecanmodelthisbysayingthattherearetwostatesoftheworldthati=3/4inthecannotdistinguish,suchthatw,(p)=1/2inone.andw,(~)other.Insuchasituation,itwouldbethecasethatK,(w,(q)2Z1/2)holds.2Therewouldbenodifficultygivingsemanticstosuchformulas,butsomeofourresultsondecisionproceduresandaxiomatizationsseemtorequirethatwenotallowsuchmixedformulas.Wereturntothispointinthenextsection.346ThelanguageusedhereextendsthatconsideredR.FAGINANDJ.Y.HALPERNin[Faginetal.,1990]intwow,wehaveaustoreasonabouttheprobabilityassignedbydifferentagentstothesameevent.Secondly,ratherthanrestrictingtheformulasthatappearinthescopeoftheprobabilitymodalitytobepropositional,weallowthemtobearbitrary.Inparticular,weallowhigher-orderprobabilityformulassuchasWl(w,(p)>b))>c.Beforewegiveformalsemanticstothislanguage,webrieflyreviewsomematerialfromprobabilitytheory(seeHalmos[1950]formoredetails).Aprobabilityspaceisatuple(0,%,p)whereQisaset,calledthesamplespace,%isau-algebraofsubsetsof0(i.e.,asetofsubsetscontainingOandclosedundercomplementationandcountableunion),whoseelementsarecalledthenzeaszirablesets,andaprobabilitymeasurevdefinedontheelementsof%Notethatp,doesnotassignaprobabilitytoallsubsetsofQ,butonlytothemeasurablesets.OnenaturalwayofattachingaweighttoeverysubsetofQisbyconsideringtheinnermeasurep~inducedbyp;ifAcQ,wehaveK*(A)=sup{P(B)lBCAandBways.First,ratherthanhavingjustone“probabilityi,inordertoallowmodalityW,foreachagentmodality”q%}.Thus,theinnermeasureofAisessentiallythemeasureofthelargestmeasurablesetcontainedinA.Thepropertiesofprobabilityspacesguaranteethatp.iswelldefined,andthatifAismeasurable,thenW.(A)=W(A).3GivenastructureM=(S,w,51,...,~,),inordertodecidewhetheraproba-bilityformulaistrueatastatesinM,weneedtoassociatewitheachstatesaprobabilityspace.Thus,wetakeaKripkestructureforknowledgeandprobability(fornagents)tobeatuple(S,T,%,,...,%.,E),where@isaprobabilityassigmtent,whichassignstoeachagenti={1,...,n}andstates=SaprobabilityspaceAi,s)=(S,,,,,2;,,,p,,,),whereS,,,~S.Weshallusuallytheprobabilityspace9,,,describesagenti’swriteWi,s)asY,,.Intuitively,probabilitiesonevents,giventhatthestateiss.WeallowS,,,tobeanarbitrarysubsetofS.ItmightseemreasonabletotakeS,,,=~(s),thusrequiringthattheagentplacesprobabilityonpreciselyonthesetofworldsheconsiderspossible;however,asweshallseebelow,therearegoodtechnicalItisoftenandphilosophicalreasonstoallowS,,,tobedistinctfromZ(s).naturaltorequireatleastthatS,,,beasubsetof~(s);weconsidertheconsequencesofthisassumptionbelow.Wecangivesemanticstoformulasnotinvolvingprobabilityjustasbefore.Togivesemanticstoi-probabilityformulas,assumeinductivelythatwehavedefined(M,s)>pforeachstates=S.DefineS,,(P)={s’~S,,,1(M,s’)kq}.Then,theobviouswaytodefinethesemanticsofaformulasuchasW,l(v)>bis(~,s)%W1((0)>biffP,,,(S,,,(q))>b.TheonlyproblemwiththisdefinitionisthatthesetS,,,(q)mightnotbemeasurable(i.e.,notin~?~,,),sothatp,,,(S,,,(q))mightnotbewelldefined.Wediscussthisissueinmoredetailbelow(and,infact,providesufficientconditionstoguaranteethatthissetismeasurable),butinordertodealwith~Weremarkthatthereisalsoadualnotionofoutermeasure;theoutermeasureofA,denoted,u*(xl),]sessentiallythemeasureofthesmallestmeasurablesetcontainingA.ItiseasytoseethatW*(A)=1–K*(bistrueatthestatesifthereissomemeasurabletoagenti)containedinS(,,(q)whosemeasureisatleastb.MorewehaveThiscompletesthesemanticdefinitionforthewholelanguage.Beforewediscussthepropertiesofthislanguage,itishelpfultoconsideradetailedexample.Thisexampleillustratessomeofthesubtletiesinvolvedinchoosingtheprobabilityspacesateachstate.Supposewehavetwoagents.Agent2hasaninputbit,eitherOor1.Hethentossesafaircoin,andperformsanactionaifthecointossagreeswiththeinputbit,thatis,ifthecointosslandsheadsandtheinputbitis1,orifthecoinlandstailsandtheinputbitisO.Weassumethatagent1neverlearnsagent2’sinputbitortheoutcomeofhiscointoss.Aneasyargumentshowsthataccordingtoagent2,whoknowstheinputbit,theprobability(beforehetossesthecoin)ofperformingactionais1/2.Thereisalsoareasonableargumenttoshowthat,evenaccordingtoagent1(whodoesnotknowtheinputbit),theprobabilitythattheactionwillbeperformedis1/2.Clearlyfromagent1’sviewpoint,ifagent2’sinputbitisO,thentheprobabilitythatagent2performsactionais1/2(sincetheprobabilityofthecoinlandingheadsis1/2);similarly,ifagent2’sinputbitis1,thentheprobabilityofagent2performingactionais1/2.Thus,nomatterwhatagent2’sinputbit,theprobabilityaccordingtoagent1thatagent2willperformactionais1/2.Thus,itseemsreasonabletosaythatagent1knowsthattheaprioriprobabilityofagent2performingactionais1/2.Notethatwedonotneedtoassumeaprobabilitydistributionontheinputbitforthisargumenttohold.Thisisagoodthing:Wedonotwanttoassumethatthereisaninputontheprobabilitydistribution,sincenoneisprovidedbytheproblemstatement.Ofcourse,iftherewereaprobabilitydistribution,thenthisargumentwouldholdindepen-dentoftheactualprobabilitydistribution.Nowsupposewewanttocapturethisargumentinourformalsystem.Fromagent1’spointofview,therearefourpossibilities:(1,h),(1,t),(O,h),(O,1)(theinputbitwas1andthecoinlandedheads,theinputbitwas1andthecoinlandedtails,etc.).WecanviewtheseasthepossibleworldsorstatesinaKripkestructure.CallthemSI,Sz,Sj,andSJ,respectively;letSbethesetconsistingofallfourstates.AssumethatwehaveprimitivepropositionsA,H,T,Bo,andBIinthelanguage,denotingtheeventsthatactionaisperformed,thecoinlandedheads,thecoinlandedtails,agent2’sinputbitisO,andagent2’sinputbitis1.Thus,Histrueatstatess~ands~,Aistrueatstatess,andSd,andsoon.Whatshouldagent1’sprobabilityassignmentbe?Wenowdescribethreeplausibleanswerstothisquestion.(1)Wecanassociatewitheachstatethesamplespaceconsistingofallfourstates,thatis,allthepossibleworlds.Thismightseemtobethemostnaturalchoice,sincewearetakingtheprobabilityspaceateachstatestobe5,(s),sothatateachstate,agent1isputtingtheprobabilityontheset348R.FAGINANDJ.Y.HALPERNofstatesthatheconsiderspossible.Becauseweassumethatthereisnoprobabilityontheevent“theinputbitisO“(respectively,“theinputbitisl“),theonlycandidatesformeasurablesets(besidesthewholespaceandtheemptyset)are{sl,s~)(whichcorrespondstotheevent“thecoinlandedheads”)and{sz,SJ}(“thecoinlandedtails”).Eachofthesesetshasprobability1/2.CalltheresultingKripkestructureM(].Noticethattheevents{sl}and{sz}cannotbothbemeasurable,forthentheevent{sl,sz},whichcorrespondsto“theinputbitisl“,wouldalsobemeasurable.Similarly,wecannottake{sl,Sal},whichcorrespondstotheevent“actionaisperformed”,tobemeasurable.Thisisbecauseifitweremeasurable,then,sincethesetofmeasurablesetsisclosedunderfiniteintersectionandcomplementation,eachof{sl},{sg},{s~}.and{sq}wouldhavetobemeasurable.(2)Wecanassociatewithstatess,andSz,wheretheinputbitis1,thesamplespaceconsistingonlyofSIandSz,with{sl}and{sz}bothbeingmeasurableandhavingmeasure1/2.Similarly,wecanassociatewithstatess~andSqthesamplespaceconsistingonlyofs~andS4,with{s~}and{s4}eachhavingmeasure1/2.Thus,whentheinputbitis1,wetakethesamplespacetoconsistofonlythosestateswheretheinputbitis1,withtheobviousprobabilityonthatspace,andsimilarlyforwhentheinputbitisO.CallthisKripkestructureMl.(3)Finally,wecanmakethetrivialchoiceofassociatingwitheachstatethesamplespaceconsistingofthatstatealone,andgivingitmeasure1.CalltheresultingKripkestructureM?.OfthethreeKripkestructuresabove,itiseasytoseethatonlyM,supportstheinformalreasoningabove.Itiseasytocheckthatwehave(Ml,s)kKjl‘A,foreverystatesES.Ontheotherhand,ineverystateofM?,wehaveeitherWI(A)=1(instatesS1andSJ)orW’I(A)=O(instatesS2ands?).Thus,foreverystatesES,wehave(MQ,s)kK1((w1(A)=1)V(WI(A)=O))and(Mz,s)R~Kjl%l.Finally,inMO,theeventAisnotmeasurable,nordoesitcontainanynonemptymeasurablesets.Thus,wehave(M(,,s)RKl(wl(A)=O)(wherenowWIrepresentstheinnermeasure,sinceAisnotmeasurable).DoesthismeanthatMlissomehowthe“right”Kripkestructureforthissituation?Notnecessarily.Abetterunderstandingcanbeattainedifwethinkofthisasatwo-stepprocessdevelopingovertime.Atthefirststep,“nature”(nondeterministically)selectsagent2’sinputbit.Thenagent2tossesthecoin.Wecanthinkofikljasdescribingthesituationafterthecoinhaslanded.Itdoesnotmakesensetosaythattheprobabilityofheadsis1/2atthistime(althoughitdoesmakesensetosaythattheuprioriprobabilityofheadsis1/2),nordoesitmakesensetosaythattheprobabilityofperformingactionais1/2.Afterthecoinhaslanded,eitheritlandedheadsoritdidn’t;eitherawasperformedoritwasn’t.ThisistheintuitiveexplanationforwhytheformulaK1((w1(A)=1)V(WI(A)=O))isvalidinM2.Mldescribesthesituationafternaturehasmadeherdecision,butbeforethecoinistossed.Thus,agent1knowsthateithertheinputbitis1ortheinputbitisO(althoughhedoesn’tknowwhichone).Asexpected,theformulaKI((w1($BO)=1)v(wl(Bl)=O))holdsinthissituation.An(admittedlyweak)argumentcanbemadethatM’.describestheinitialsituation,beforenaturehasmadeherdecision.Atthispoint,theevent“theinputbitisO“isnotmeasurableandwecannotattachaprobabilitytoit.ReasoningaboutKnowledgeandProbability349Wecancapturetheseintuitionsnicelyusingruns.Therearefourruns,sayrl,rz,r~,rd,correspondingtothefourstatesabove.Therearethreerelevanttimes:O(beforenaturehasdecidedontheinputbit),1(afternaturehasdecided,butbeforethecoinistossed),and2(afterthecoinistossed).Agent1’slocalstatecontainsonlythetime(sinceagent1neverlearnsanythingaboutthecoinortheinputbit);agent2’slocalstatecontainsthetime,theinputbit(attimes1and2),andtheoutcomeofthecointoss(attime2).Wecanomittheenvironmentfromtheglobalstate;everythingrelevantisalreadycapturedbythestatesoftheagents.Thus,attime1inrunr~,agent1’slocalstateis1(sincethetimeis1),whileagent2’slocalstateisthepair(1,O),sincethetimeis1andtheinputbitisO.Thus,r~(l)=(1,(1,O)).Similarly,wehavethatr3(2)=(2,(2,O,h)).WenowinterpretthepropositionsA,H,etc.tomeanthattheactionahasbeenoreventuallywillbeperformed,headshasbeenoreventuallywillbetossed,etc.Thus,propositionAistrueatthepoint(r,,k)iftheactionaisperformedat(rj,3).Similarly,Histrueat(r,,k)ifheadsistossedinrunr],andsoon.Clearlyateachtimek=0,1,2,agent1considersthefourpoints(r,,k),spaceateachj=1,2,3,4,possible.AttimeO,wecandefinetheprobabilitystatetomakethislooklikeMO.Attime1,definingtheprobabilityspacessothatwegetKripkestructureMlseemstobeappropriate,whileattime2,KripkestructureMzseemsappropriate.Thus,althoughitseemsthat,insomesense,agent1’sknowledgeabouttheinputbitandtheoutcomeofthecointossdoesnotchangeovertime,theprobabilityassignmentsusedbyagent1maychange.Forexample,afterthecoinhasbeentossed,theprobabilityassignmentshouldchangetoreflectthefactthat,althoughagent1hasnotlearnedanythingabouttheoutcomeofthecoinflip,hedoesknowthatthecoinhasbeentossed.Butwhyandhowshouldthefactthatthecoinhasbeentossedaffecttheprobabilityassignmentusedbyagent1?Thisquestionisperhapsbestansweredintheframeworkdiscussedin[HalpernandTuttle,19],wherethepointofviewistakenthatthechoiceofprobabilityassignmentshouldreflecttheagent’sviewoftheadversaryitisplayingagainstor,moreaccurately,theknowledgeoftheadversaryitisplayingagainst.Differentchoicesofprobabil-ityassignmentcorrespondtoplayingadversarieswithdifferentknowledge.Supposeweplayanadversa~withcompleteinformationaboutallthathashappenedinthepast,butwhodoesnotknowtheoutcomeofprobabilisticeventsthatwilltakeplaceinthefuture.Thus,attime1,theadversa~doesnotknowtheoutcomeofthecointoss,whileattime2,hedoes.Asshownin[HalpernandTuttle,19],whenagentiisplayingagainstsuchanadversary,theprobabilityassignmentusedbyagentishouldreflectwhattheadversaryknowsaswellaswhatagentiknows.Technically,thisamountstotakingtheintersectionofthesetofpossiblewordsdescribingagenti’sknowledgewiththesetofpossibleworldsdescribingtheadversary’sknowledge.Thus,whenplayingagainstanadversarywithcompleteinformationaboutthepast,theassignmentdescribedbyMlisappropriateattime1,whiletheassignmentdescribedbyM,isappropriateattime2.(SeeHalpernandTuttle[19]fordetailsoftheargumentsregardingappropriateness.)Interestingly,theproba-bilityassignmentdescribedbyMe—whichinitiallymayhaveseemedtobethemostreasonablechoiceofprobabilityassignment—doesnotcorrespondtoplayingagainstanadversaryintheframeworkofHalpernandTuttle[19].Inretrospect,itisthehardestprobabilityassignmenttojustify.350R.FAGINANDJ.Y.HALPERNEveninthissimpleexample,wecanalreadyseethatthedecisionofhowtoassigntheprobabilityspacesisnotcompletelystraightforward.Ingeneral,itseemsthatitwilldependinmoredetailontheformoftheanalysis.Thisexamplealreadyshowsthatingeneralatastates,wedonotwanttotakeinMl,S,,,,=~(s).NotethatS,,=XI(s)onlyinMOabove;inparticular,wherewecancarlyouttheinformalreasoningwhichsaysthatactionaoccurswithprobability1/2,wehaveS,,,asastrictsubsetof%1(S).qAlthoughinthisexample,wedonotwantS,,,=%(s),wedowantS,,,G%(s).Thisisquiteanaturalcondition.Withoutit,itispossiblethatanagentcanplacepositiveprobabilityonafactthatheknowstobefalse;forexample,theformulaK,-p~w,(p)>0isconsistent.Wewouldviewanagentwhoplacespositiveprobabilityonaneventheknowstobefalseasinconsistent.Thus,wetermthefollowingconditionCONS(forcomistent).CONS.Foralliands,if=,,,=(S,,,,.~,,,K,,,),thenS,,,G%(s).NotethatCONSdoesnotimplythatsqS,,,;anagentisnotrequiredtoviewthestatethatheisinasoneofthesetofstatesinhisprobabilityspace.Althoughitmayseemunusual,therearetimes(inparticular,whenanalyzingasytzchro~zcwsdistributedsystems),whenitturnsouttobeappropriatenottorequirethatsES,,,[HalpernandTuttle.19].Insomeapplications.althoughtheagentshavedifferentsetsofpointstheyconsiderpossible,itisusefultomodelthemasagreeingonwhattheprobabil-ityspaceisateachpoint.Inthiscase,wesaythattheprobabilityassignmentisobjectil’e.Thisisaquitenaturalassumptionincontextswherealltheproba-bilisticeventsarecommonknowledge,forexample,ifthereisaglobalcoin.Alternatively,inthefra~meworkofHalpernandTuttle[19],itisappropriateiftheagentsareviewedasallplayingthesameadversary,whohasatleastasmuchknowledgeaseachoftheagentsindividually.Notethat,underthisassumption,theintersectionofthesetofstatesdescribingagenti’sknowledgewiththesetofstatesdescribingtheadversaty’sknowledgeisthesameforalli.Thismeansthat,accordingtotheframeworkofHalpernandTuttle[19],theagentsshouldallusethesameprobabilityassignment.Notethatthisassump-tionisappropriate,forexample,iftheagentsallplayanadversarywhohascompleteinformationabouttheglobalstateofthesystem,theywouldagreeonwhattheappropriateprobabilityspaceshouldbe,sInthecontextofaKripkestructureforknowledgeandprobability,havinganobjectiveprobabilityassignmentcorrespondstothefollowingcondition:OBJ.M’t,=~,,foralli,j,ands.NotethatifwehadrequiredthatS,,=E’(s)foreachagentiandeachstates,thenOBJcouldholdonlyinKripkestructureswhere~(,s)=.~(,s)forallagentsiand,jandallstatess.4ThcexamplepresentedhereISaslmpllficatlonofoncgl~enbyMarkTuttle.ItwasMarkwhofirstpointedouttousthatitisnotalwaysappropriatetotakeS,,,=.%(s).$MarkTuttleandYoramMosesfirstpointedouttousthatindistributedsystemsapplications,anaPPropri~t~choiceisoften~nObjectivepmbabdhywiththeprofmbdityspaceconsistingofallthepointswiththesameglobalsttite.Thisapprotichwwfirsttakenin[Halpern,1988].SeeFisherandZuck[19S8]andHalpernandTuttle[19]forfurtherdiscussionontheappropriatechoiceofprobabilityassignmentIndistributedsystems.ReasoningaboutKnowledgeandProbability351Wenowconsidersomeotherassumptionsabouttheinterrelationshipbe-tweenanagent’sprobabilityassignmentsatdifferentstates.Arathernaturalassumptiontomakeonthechoiceofprobabilityspaceisthatitisthesameinallworldstheagentconsiderspossible.Inthecontextofdistributedsystems,thiswouldmeanthatanagent’sprobabilityspaceisdeterminedbyhislocalstate.WecallthispropertySDP(state-determinedprobability).Formally,wehave:SDP.Foralli,s,andt,ift=x(s),thenY,,,=Y7,,,.OfthethreeKripkestructuresweconsideredabove,onlykf[lsatisfiesSDp.Asthediscussionin[HalpernandTuttle,19]shows,SDPismostnaturalinsituationswherenonondeterministic(or,perhapsbetter,nonprobabilistic)choicesaremadeby“nature”.(Inourexample,thechoiceoftheagent’sinputbitisnonprobabilistic;theoutcomeofthecointossisprobabilistic.)SDPisanassumptionthathasoftenbeenmade.Indeed,itisimplicitlyassumedinmuchoftheeconomists’work(e.g.,[Aumann,1976;Cave,1983]).Inthesepapers,itisassumedthateachagentinitiallydefinesaprobabilityspaceoverthesamplespaceofallworlds.Thus,foreachagenti,wehaveaprobabilityspace9,=(S,Y;,W,),whereSisthesetofallworlds:Agenti’sprobabilityofaneventeatastatesistakentobetheconditionalprobabilityofegivenagenti’ssetofpossibleworlds.ThismeansthatY,,=(~(s),~~,,,v,,,),whereq.3},and~,,,,(An.~(s))=’K,(A)/p,(Z(S)).7Notethat:&,$={An~(s)l~theresultingKripkestructurehastheSDPproperty.AlthoughMlandMzinourexampleabovedonotsatisfySDP,theydosatisfyaweakerpropertythatwecalluni~onnity.Roughlyspeaking,uniformityholdsifwecanpartitionZ(s)intosubsetssuchthatateverypointinagivensubsetT,theprobabilityspaceisthesame.Formally,wesayuniformityholdsifUNIF.ForY,,,=9,,,.alli,s,andt,ifY,,,=(S,,,,JY,,$,v,,,)andfqS,,,.thenNoticethatUNIFdoesnotrequirethatS,,,,c%;(s);thus,inordertobeabletopartitionq(s)intosubsetssuchthatatevegpointinagivensubsetT>theprobabilityspaceisthesame,werequirebothUNIFandCONS.Uniformityarisesinanaturalwaywhenconsideringappropriateprobabilityassignmentsindistributedsystems.EachsubsetofS,,,turnsouttocorrespondtotheresultof“nature”makingaparticularnonprobabilisticchoice,justasisthecaseinthestructureMlinourexample(seeHalpernandTuttle[19]fordetails).Uniformityalsohassomeinterestingconnectionswithawell-studiedprincipleregardinghigher-orderprobabilitiescalledMiller’sprinciple[Miller,1966;Skyrms,1980];wecommentonthisinalittlemoredetailbelow.NotethatCONSandSDPtogetherimplyUNIF,andthatallthestructuresinourexampleabovesatisfyUNIF.Thereisonelastpropertyofinteresttous,whichseemstohavebeenassumedinallpreviouspapersinvolvingreasoningaboutprobability,andthat6Aumannactuallyassumesthatthereisanobjectiveprobabilityonthewholespace,sothat~,=W,forallagentsiandj.Thiscorrespondstotheagentshavingacommonpriordistribution.7Thisapproachrunsintoslighttechnicaldifficultiesif~(s)isnotmeasurable,orhasmeasure0.However,itisalwaysassumedthatthisisnotthecase.352isthatallformulasdefinemeasurableR.FAGINANDJ.Y.HALPERNsets.Asshownin[Faginetal.,1990](andasweshallseeagainbelow),reasoningaboutprobabilityissimplifiedifweassumethatallformulasdefinemeasurablesets.Moreprecisely,westiythatformulasdefinemeasurablesetsinMifMEAS.Foralliandsandforeveryformula~,thesetS,,,(p)G.?~,,.(RecallthatS,,,(q)={s’ES,,,,I(M,s’)*q}.)Clearlyifprimitivepropositionsdefinemeasurablesets,thenallproposi-tionalformulasdefinemeasurablesets.However,thereisnoparticularreasontoexpectthataprobabilityformulasuchasw,(p)+w,(q)z1/2willdefineameasurableset(infact,itiseasytoshowthatingeneralitwillnot).LetPMEASbethepropertywhichsaysthatallprimitivepropositionsdefinemeasurablesets.(NotethatPMEASdoesnotholdinMt,,butdoesholdinMlandMS.)ThefollowinglemmadescribessufficientconditionsforMEAStohold.IfMisostnictusesotisfiingthenMsatisfiesMEAS.LEMMA3.1.PROOF.CONS,OBJ,UNIF,andPMEAS,AstraightforwardinductiononthestructureofformulasqshowsthatS,,,(p)ismeasurableforallformulasp.TheassumptionsCONSandOBJtogetherimplythatforallagentsiandj,wehaveS,,G%(s),soitiseasytoseethatS,,(K,p)iseitherS,,,or@.Ineithercase,itismeasurable.Similarly,wecansh’owthatOBJandUNIFtogetherimplythatforanyprobabilityformulag,wehavethatS,,,(p)iseitherS,,,,or0.uItseemsthatOBJ,UNIF,andPMEASareoftenreasonableassumptionsindistributedsystemsapplications,sothislemmaisofmorethanjustpuretechnicalinterest.Weclosethissectionbybrieflyconsideringonemorepropertyofprobabili-tiesthathasappearedintheliterature.Miller’sprincipleisanaxiomthatconnectshigher-orderprobabilities(thatis,probabilitiesonprobabilities)withprobabilitiesonformulas[Miller,1966;Skyrms,1980].Itsays:Itiseasytoseethat,ingeneral,thisaxiomdoesnotholdinstructuresforknowledgeandprobability.However,itisnothardtoshowthatourconditionUNIFimpliesthisaxiom.InsystemssatisfyingUNIF,wehaveeither(a)(wt(p)>b)isfalseatstates,inwhichcaseUNIFimpliesthatw,(w,(q)>b)=Oatstates,or(b)(wL(q)>b)istrueatstates,inwhichcaseUNIFimpliesthatW,(WJ[(p)>b)=1atstates.Ineithercase,itiseasytoseethatMiller’sprincipleholds.ItturnsoutthatthereisaprecisesenseinwhichMiller’sprinciplecompletelycharacterizesuniformstructures;seeHalpern[1991]fordetails.4.CompleteAxiomatizationsandDecisionProceduresWenowdescribeanaturalcompleteaxiomatizationforthelogicofprobabilityandknowledge.Theaxiomsystemcanbemodularizedintofourcomponents.Thefirstcomponentallowsustodopropositionalreasoning,thesecondallowsustoreasonaboutknowledge,thethirdallowsustoreasonaboutinequalities(soitcontainsaxiomsthatallowustodeduce,forexample,that2X>2JIReasoningaboutKnowledgeondProbabilityfollowsfromx>y),whilethefourthistheonlyonethatinferencerulesforreasoningaboutprobability.I.AxiomandruleforpropositionalreasoningAxiomK1andruleIllfromSection2II.AxiomsandruleforreasoningaboutknowledgeAxiomsK2–K5andruleR2fromSection2hasaxioms353andForreasoningaboutinequalities,weneedasystemthatallowsustoproveallvalidformulasaboutlinearinequalities;oneparticularsystemthatwilldothetrickisgivenin[Faginetal.,1990].Werepeatithere.111.Axiomsforreasoningaboutlinearinequalities>b)~(alwl(ql)+““.+a~w,(q~)+OW,(PL+l)Oterms).>b)*(a,,w,(p,,)+“..+aj,w,(qj,)>b),if12.(alwl(ql)+“.”+akw,(qk)j~isapermutationof1,...,k(permutation).jl...)13.(alw,(ql)+.“’+aLwl(pL)+o“”+aj,w,(p~)>b’)->b)A(a\\wl(pl)“””+(aL+a.~)wl(p~)>(b+b’)(additionofcoefficients).(al+a\\)wz(pl)+14.(alw,(ql)+““.+a~w,(p~)>b)-(dalw,(pl)+.“”+da~wl(q~)>db)ifd>0(multiplicationofnonzerocoefficients).15.(t>b)V(tsb)iftisaterm(dichotomy).16.(t>b)-(t>c)iftisatermandb>c(monotonicity).Finally,weneedaxiomsforreasoningaboutprobability.Theaxiomswetakeofthearealsogivenin[Faginetal.,1990];theyaresimplyatranslationstandardaxiomsforprobabilityinfinitedomainstoourlanguage.IV.AxiomsWI.W2.W3.W4.W5.forreasoningaboutprobabilities+“.”+a~wl(q~)11.(alw,(pl)>b)(addinganddeletingw,(q)20(nonnegativity).wl(true)=1(theprobabilityoftheeventtrueis1).W,(PA~)+W,(PA~~)=w,(p)(additivity).w,(q)=w,(~)ifq~~isapropositiontautology(distributivity).oftheeventfalseis0).8w,(fake)=O(theprobabilityAxiomW3correspondstofiniteadditivity.Althoughweallowinfinitedomains,asnotedin[Faginetal.,1990],wedonotneedanaxiomthatcorrespondstocountableadditivity.Indeed,wecouldnotevenexpresssuchanaxiominourlanguage.Roughlyspeaking,wecangetawaywithfiniteadditivitybecausewecanshowthatifaformulaissatisfiableatall,itissatisfiableinafinitedomain.Thingsgetmorecomplicatedifwedropthemeasurabilityassumption.Itiseasytocheckthatinthiscase,W3isnolongersound.Asshownin[Faginetal.,1990],thereisanotheraxiomwithwhichwecanreplaceW3togetacompleteaxiomatization.Thisaxiomisalsothekeyaxiomthatcharacterizes‘AxiomW5isactuallyredundant.Itisincluded,sinceitwillbeneededaxiomW3byanotheraxiominthenonmeasurablecase.laterwhenwereplace3beliefjhnctiotlstainty.intheDempster–ShaferR.FAGINANDJ.Y.HALPERNapproachtoreasoningaboutuncer-Althoughthisaxiommayappearsotnewhatmysterious,notethatifwereplace>by=,theninthemeasurablecase,thisbecomesaninstanceofthewell-knownitzclusion-exclzwionmleforprobabilities[Feldman,1984].ItturnsoutthatifwereplaceW3byW6,wegetacompleteaxiomatizationfori-probabilityformulasinthenonmeasurablecase.(SeeFaginetal.[1990]formoredetails,aswellasproofsofsoundnessandcompleteness.)LetAX~~~~consistsofK1–K5,11–16,W1–W5,andR1–R2.LetAXbetheresultofreplacingW3inAX~~~~byW6.ThefollowingtheoremsaysthattheseaxiomatizationsaresoundandcompletelyAX(respectilqe~,AX,ilfi,4,7)isasoundandconzpleteaxiomati-(z-espeetitwly,forstructureszationforthelogicofknowledgeandprobabilitysatisfvirzgA4EAS).THEOREM4.1.PROOF.Soundnessisstraightforward,asusual,sowefocusoncomplete-ness.Wesketchtheproofforthemeasurablecase;thenonmeasurablecasefollowsthesamelines.Inordertoprovecompleteness,weneedonlyshowthatiftheformulaqisconsistentwithAX~~,~s,thenqissatisfiableinaKripkestructureforknowledgeandprobabilitysatisfyingMEAS.LetSub(p)bethesetofallsubformulasofp,andletSub+(p)bethesetofsubformulasofpandtheirnegations.Letsbeafinitesetofformulas,andletp,betheconjunctionoftheifitisnotthecasethatAXK1~Asbformulasins.Wesaythatsisco)zsistentTP,,whereasusual,wewriteAX~~As+*iftheformulaVisprovableintheaxiomsystemAX~~As.consistentsubsetofThesetsisanzainzulSub+(p)ifitisconsistent,asubsetofSub+(q),andforeverysubformula*ofp,includesoneof#orm~.(Notethatitcannotincludeboth,forthenitwouldnotbeconsistent.)FollowingMakinson[1966](seealsoHalpernandMoses[1992]),wefirstconstructaKripkestructureforknowledge(butnotprobability)(S,n,%1,...,S.)asfollows:WetakeS,thesetofstates,toconsistofallmaximalconsistentsubsetsofSub+(p).Ifsandtarestates,then(s,t)EZ:preciselyifsandtcontainthesameformulasoftheformK,~.Wedefine~sothatforaprimitivepropositionp,wehavem-(s)(p)=trueiffpisoneoftheformulasinthesets.Ourgoalistodefineaprobabilityassignment9suchthatifweconsidertheKripkestructureforknowledgeandprobabilityA4:(S,71-,Z,,...,2?,,,9),thenforeverystatesGSandeveryformula~ESub+(p),wehave(Tf,s)~~iff4=s.WenowsketchthetechniquesfromFaginetal.[1990]requiredtodothis.Itiseasytoseethattheformulasq,,areprovablymutuallyexclusiveforsGS;thatis,AX~~~st-q,+1p~fors#t.Indeed,theproofusesonlyproposi-tionalreasoning,namelyK1andR1.Moreover,againusingonlypropositionalreasoning.wecanshowthatAXNiEAS+@*‘{,5ELyl!~ES)~57forall*G‘)TheproofsofthetechnicalresultsmthtssectionpresumefamiliaritywiththeresultsofFagmetal.[1990].andwithstandardproofsofcompletenessandcomplexityformodalIogics(cf.[HalpernandMoses.1992;Ladner,1977]).ReasoningaboutKnowledgeandProbability355Sub+(q).Usingtheseobservations,wecanshow,usingW1-W5,that~i(~)=(cf.[Faginetal.,1990,Lemma2.31).’”~{.,qSloqJ}A(%)isprovablein&i~~*~Usingthisfacttogetherwith11and13,wecanshowthatani-probabilityisprovablyequivalenttoaformulaoftheformformula*qSub’(p)Z,~~c,,v,(p,)>b,forsomeappropriatecoefficientsc,.FixanagentiandastatesqS.Wenowdescribeasetoflinearequalitiesandinequalitiescorrespondingtoiands,overvariablesoftheformx,,,,forS’GS.Wecanthinkofx,,,,asrepresenting~,,(s’),thatis,theprobabilityofstates’underagenti’sprobabilitydistributionatstates.Wehaveoneinequalitycorrespondingtoeveryi-probabilityformula~inSub’(q).Assumethat@isequivalenttoZ,~~c,,P,(p,,)>b.Observethatexactlyoneof~andinequalityis~~isins.If@qs,thenthecorrespondingIf1*=s,thenthecorrespondinginequalityisFinally,wehavetheequalityAsshowninTheorem2.2inFaginetal.[1990],sincep,isconsistent,thissetoflinearequalitiesandinequalitieshasasolutionx~,$,s’=S.setofinequalitiesseparately.Foreachiands,wesolvethecorrespondingWenowdefineYsothatY,,,=(S,2s,I-L,,,),whereifAGS,thenK,,,,(A)=x,,E~x;y,.SinceZ,q~x~,,,=1,itiseasytoseethat~,,,isindeedaprobabil-itymeasure.Notethat,intheprobabilityspace@t,~,everysetismeasurable.ThisprobabilityassignmentdoesnotnecessarilysatisfyCONS;itmaywellbethecasethattherearesetsdisjointfrom~(s)thatareassignedpositivemeasureunderw,,,.Aswesaidabove,wenowwanttoshowthatforeveryformula~eSub+(p)andeverystateins,wehave(M,s)R~iffOEs.Theproofproceedsbyinductionon*.If~isaprimitiveproposition,theresultisimmediatefromthedefinitionofn-.Thecaseswhere~isanegationoraconjunctionarestraightforwardandlefttothereader.Thecasewhere*isani-probabilityformulafollowsimmediatelyfromtheargumentsabove,sincetheappropriateinequalitycorrespondingto~issatisfiedby~1,,.Finally,if@isoftheformK,~’,theproofproceedsusingwell-knownargumentsfrommodallogic(cf.[HughesandCresswell,1968;HalpernandMoses,1992]).Wesketchafewofof.%,foralltcZ(s),wethedetailshere.IfK,*’qs,then,byconstructionhaveK,#ct.SincetisamaximalconsistentsubsetofSub+(P),itmUStbethecasethatoneof+’or=t’isint.FromAxiomK3,itfollowsthatitmustinfactbe~’.Bytheinductionhypothesis,wehavethat(M,t)!=IJJ’.Sincethiswehavethat(M,s)+K,~’.argumentholdsforallt=~(s),‘“Notethatthisprw]fmakescrucialuseofW3;thisformulaisnotprovableusingtheaxiomsystemAX.356R.FAGINANDJ.Y.HALPERNNowsupposethat(M,s)!=K,~’.WewanttoshowthatK,+’=s.Lets’bethesubsetofsconsistingofallformulasinsoftheformK,+“or1K,+“.s’includesoneofK,y’J’or7K,~’;weplantoshowNoticethat,inparticular,thatinfactitmustincludeK,+’.WeclaimthatForsupposenot.Thenq,,,~mo’isconsistent.Thus,thereisamaximalconsistentsubsetofSub+(p),sayt,thatincludess’U{1~’}.Butthen,byconstructionof~,wehave(s,t)=S;,andbytheinductionhypothesis.(M,t)R1*’.Butthiscontradictsourassumptionthat(M,s)+K,~’.Thus,(1)holds.ByIQfrom(1),wehave(2)UsingA2andpropositionalreasoning,itfollowsthat(3)Everyconjunctofq,,isoftheformK,~“ornK,~“.Thus,ifoisoneoftheconjunctsofyJ,T,usingeitherAxiomA4orA5,itfollowsthatItiswellknown(andcanbeprovedformulasmlandUQ,wehaveusingKl,K2,RI,andR2)thatforanyThus,from(4),itfollowsthatFrom(3)and(5),wenowgetitnowfollowsthatmK,~’cannotbeoneoftheconjunctsofp,,,andhencethatKl4’cs,asdesired.Ifpisconsistent,itmustbeinoneofthemaximalconsistentsubsetsofSub+(p).Thus,itfollowsthatifqisconsistent,thenitissatisfiableinthestructureM.Thiscompletetheproofinthemeasurablecase.Notethattheproofshowsthemodularityoftheaxiomsystem.Inordertodealwithi-probabilityformulas,wejustneedtheaxiomsforreasoningaboutprobabilityandinequalities(togetherwithpropositionalreasoning);theaxiomsforreasoningaboutknowledgeplaynorole.Similarly,inordertodealwithknowledgeformulas,wejustusedtheaxiomsforreasoningaboutknowledge.Thismodularityisimportantwhenitcomestodealingwiththenonmeasur-ablecase.Wemustnowreplacetheargumentsaboveforconstructing$ZZbyanalogousargumentsfromTheorem3.8ofFaginetal.[1990]forthenonmea-surablecase.Astheseargumentsshow,itisnotquitethecasethatwecanconstructaKripkestructuresatisfyingpwhosesetofstatesisthesetSaboveconsistingofmaximalconsistentsubsetsofSub+(q).Rather,weneedtomakecopiesofeachofthemaximalconsistentsets.Thus,foreachmaximalconsis-tentsets,therewillbestates,sl,.,.,s,,(asshownin[Faginetal.,1990],wecantakenslSub(P)I).WecannowdefineaprobabilityassignmentYonthisset;itwillnolongerbethecasethatintheprobabilityspaceYZ{,,,,allsetsareSincep,,andhencep,,isconsistent,ReasoningaboutKnowledgeandProbability357measurable.Modulothischangeto9,wecanconstructaKripkestructureMtoaforknowledgeandprobabilitysuchthatforeachstateSkcorrespondingmaximalconsistentsetsandeachformula~=Sub+(q),wehave(M,Sk)1=~iff+=s.Theprooffollowsidenticallinestothatofthemeasurablecase.Theonlychangecomesindealingwithi-probabilityformulas.Again,thisisdonebyconstructingacollectionoflinearequalitiesandinequalitiesthat~,,~mustsatisfy,intheproofofTheorem3.7ofFaginetal.[1990].Weomitfurtherudetailshere.Wecanalsocapturesomeoftheassumptionswemadeaboutsystemsaxiomatically.Inaprecisesense(asweshallsee),CONScorrespondstotheaxiomW7.K,p*(W,(p)=1).Thisaxiomessentiallytellsusthatthesetofstatesthatpossiblehasmeasure1(accordingtoagenti).OBJcorrespondstotheaxiomagenticonsidersAxiomW8saysthateachi-probabilityformulaimpliesthecorrespondingj-probabilityformula.Thisisclearlysoundifwehaveanobjectiveprobabilitydistribution.UNIFcorrespondstotheaxiomW9.q+(wl(q)=1)ifpisani-probabilityi-probabilityformula.formulaorthenegationofanSinceagiveni-probabilityformulahasthesametruthvalueatallstateswhereagenti’sprobabilityassignmentsisthesame,thesoundnessofW9instruc-turessatisfyingUNIFiseasytoverify.SDPcorrespondstotheaxiom:WIO.q=K,pifpisani-probabilityabilityformula.formulaorthenegationofani-prob-SinceSDPsaysthatagentiknowstheprobabilityspace(inthatitisthesameforallstatesin~(s)),itiseasytoseethatSDPimpliesthatinagivenstate,agentiknowsalli-probabilityformulasthataretrueinthatstate.AxiomsW7andWIOtogetherimplyW9,whichisreasonablesinceCONSandSDPtogetherimplyUNIF.Thenexttheoremprovesourclaimsaboutcorrespondencebetweenvariouspropertiesandvariousaxioms.Let.&beasubsetof{CONS,OBJ,UNIF,SDP}thecowespondingsubsetof{W7,W8,W9,W10}.ThenAXuAAX~~~sUA)isasoundandcompleteaxionlatizotionforthelogicandprobabili~forstructuressatisfyingJZZ(respectively.MEASUd.TFIEOREM4.2.PROOF.Again,soundnessisstraightforward,sowefocusWeobtaincompletenessineachcasebyarelativelystraightforwardtionoftheproofofTheorem4.1.Wejustsketchthedetailshere.andletAbe(respectively,ofknowledge11modifica-oncompleteness.1‘AlthoughitisstraightforwardtoextendTheorem4.1tothecasewherewehavemixedformulasmodificationstoaxioms11,12,13,and14),theoftheformw,(p)+w,(~))>b(withappropriatesituationseemsmuchmorecomplicatedinthepresenceofthepropertiesUNIFandSDP.Itisductothesecomplexitiesthatwedonotallowsuchmixedformulasinourlanguage.358R.FAGINANDJ.Y.HALPERNFirst,considertherelationshipbetweenCONSandaxiomW7.AssumethatW7isincludedasanaxiom.Inthiscase,itiseasytoseethatwecanmodifyourconstructionintheproofofTheorem4.1sothatwecantakeY,,=(S’l,,,.’?:,,,w,,,)suchthatSt,,c%(s).Wesketchthedetailsinthemeasurablecase.Recallthatinthiscase,intheproofofTheorem4.1,wetook9[,=(S,2’7,P,,,),sothatallsetsweremeasurable,and~,,,wasdefinedinterms’ofasolutiontoasetoflinearequalitiesandinequalities.Nowweclaimthatinthethenq,*(K,(~,)presenceofW7,wecanshowthatifsqSands’<~(s),=O)isprovable.Toseethis,observethatq,+K,(~q,,)isprovableusingK4orK5.Thus,applyingW7,wehavethatp,=(P,(1q~,)=1)isprovable.Finally,byusingW?,W3,andW4,itisnothardtoshowthatp,*(P,(p,)=O)isprovable.Asaconsequence,wecanaugmentthelinearsystemofequalitiesandinequalitiesdefining~,,,byaddingx,,,,=Ofors’G~(,s).Theproofthatshowsthattheconsistencyofp,impliesthattheoriginallinearsystemwassatisfiablecaneasilybeextendedtoshowthattheaugmentedsystemmustnowbesatisfiableinthepresenceofW7.Again,wecanusethesolutiontothissosystemtodefinew,,,.Sincex,,,=Ofors’6S;(S),wecantakeS,,,~~(,s),thatCONSissatisfied.NotethatifW7istheonlyadditionalaxiom,thenwecantakeS,,tobeZ-<(s);asweshallsee,someoftheotheraxiomsmayforceS,,,tobea’strictsubsetof%(s).NowconsidertherelationshipbetweenOBJandaxiomW8.AssumethatW8isincludedasanaxiom.Itiseasytoseethatthesubscriptsini-probabilityformulascanthenbeignored(i.e.,wecanthinkofWI(p)assimplyW(q)).Thus,wecaneasilymodifytheconstructionofTheorem4.1soastotakethattheKripkestructureforknowledgeandY’l,=9,,.ThisguaranteesprobabilitythatweconstructsatisfiesOBJ.Next,considertherelationshipbetweenUNIFandaxiomW9.AssumethatW9isincludedasanaxiom.Let~(s)bethesetofstatesthatcontainpreciselythesamei-probabilityformulasandnegationsofi-probabilityformulasass.JustasweshowedthatthepresenceofW7allowedustoassumewithoutlossofgeneralitythatS,,isasubsetof~(s),weshowthatthepresenceofW9allowsustoassume‘thatS,,isasubsetofT,(s).Again,weconsideronlythemeasurablecasehere.Supposethats’~T,(s).Thensands’disagreeonsomei-probabilityformula,say~.Withoutlossofgenerality,~Esand~Gs’.Thus,arebothprovable.Since,byW9.$=(p,,(~)=1)is~,+~hand$~lv,provable,iteasilyfollowsusingtheaxiomsofprobabilityandpropositionalreasoningthatp,~(~,(q,,)=(J)isprovable.Thus,wecanaugmentthelinearsystemofequalitiesandinequalitiesdefiningp,,,byadding.x,,,,=()fors’ET,(,~).JustasinourproofoftherelationshipbetweenW7andCONS,wecannowshowthatwecantakeT,(s)tobeasubsetof,S,,.NOWnotethatforteS,,,wemusthave~l(,s)=~,(t).Since,astheproofofTheorem4.1shows,the“definitionofp,,~dependsonlyonthei-probabilityformulasandnegationsofi-probabilityatstatet,itfollowsthatwecantakeY,~=,YJ,,,foralltGT,(s).Thus,UNIFholds.WeremarkthatifouronlyadditionalaxiomisW9,thenwecanactuallytakeS(,=~(s);however,ifwehavebothW7andW9,thenbycombiningtheargumentsusedineachcase,wecanshowthatwecantakeS,,tobeY,(s)n~(.s).Finally,chnsidertherelationshipbetweenSDPandaxiomW1O.AssumethatW10isincludedasanaxiom.WewanttoshowthatwecanslightlymodifytheconstructionofTheorem4.1sothatiftG~“(s),thentcT,(s).ThisistrivialeachReasoningaboutKnowledgeandProbability359todo:Wejustchangethedefinitionofthe~relationsothattE%(s)iffitisthecaseboththattG~(s)andthatsandtcontainallthesamesubformulasoftheformK,~.Withthischange,wecanassumewithoutlossofgeneralitythatiftc~”(s),thenY,,=@,,t,since,aswehavealreadynoted,thedefinitionofp,,,,dependsonlyonthei-probabilityformulasandnegationsofi-probabilityformulasatstatet.NowforthestructureMconstructedinthisway,westillwanttoshow(inthemeasurablecase)that(M,s)I=~iff*ES.TheproofisalmostidenticaltothatgivenforTheorem4.1.Thereisonlyonecasewherewemustbealittlecareful:whenprovingthatif(M,s)>K,~’,thenK,~’es.Ratherthantakings’tobethesubsetofsconsistingofallformulasinsoftheformK,~“or~K,~“,wenowextendittoconsistofalltheseformulastogetherwithalli-probabilityformulasornegationsofi-prob-abilityformulasins.Withthischange,theproofnowproceedsasbefore.ItisstillthecasethatforeveryformulaoEs’,wehavethatu*K,misprovable;forformulasoftheformK,*“weuseK4,forformulasoftheformvK,~“weuseK5,andifaisani-probabilityformulaorthenegationofani-probabilityformula,weuseW1O.Let.w’beasubsetof{CONS,OBJ,UNIF,SDP},andletAbethecorre-spondingsubsetof{W7,W8,W9,W1O}.IfAisincludedamongtheaxioms,thenourdiscussionshowsthatgivenaconsistentformulap,wecanmodifyouroriginalconstructionofaKripkestructureforknowledgeandprobabilitysatisfyingptogetaKripkestructurethatnotonlysatisfiesp,butalsotheuconditionsin.@.Thisprovescompleteness.Asisoftenthecaseinmodallogics,theideasinourcompletenessproofcanbeextendedtogetasmallmodelpropertyandadecisionprocedure.Inordertostateourresultshere,weneedafewdefinitions.RecallthatSub(p)isthesetofallsubformulasofp.ItiseasytoseethatanupperboundonthesizelSub(p)lofSub(p)isthenumberofsymbolsinp,wherewetreatarationalnumberasasinglesymbol.WealsodefinethesizeofaKripkestructure(s,%->%,>...,XI,9)tobethenumberKripkestructuremaybeinfinite.)THEOREM4.3.ofstatesinS.(NotethatthesizeofaLet.c#beasubsetof{MEAS,CONS,OBJ,UNIF,SDP].TheformulapissatisfiableinaKripkestructuresatisjjing.&iffitissatisfiableinaKripkestructuresatisjjingJ%ofsizeatmostlSub(9)121s”h(‘)1(orjust2“s[’h(‘)1fMEASE.@).PROOF.WeneedonlyshowthattheKripkeprobabilityconstructedintheproofofTheoremgiveninthestatementofthistheorem.IfMEASsimplypandthesetofmaximalitsnegationcannotconsistentbothbesubsetsinstructureforknowledgeand4.2isnobiggerthanthesizee.w’,thenthesetofstatesisp).Nowconsistentasubformulasubset,ofsotheofSub’(amaximalcardinalityofamaximalthenumberofstatesinconstructedintheproofIfMEAS@&,then,consistentsubsetisatmostequaltoIsub(P)I-Hence,theKripkestructureforknowledgeandprobabilityofTheorem4.2isatmost2Is”b(‘)l.aswementionedintheproofofTheorem4.1,weptobethemaximalcopiesofthesets.AsofeachucannottakethestatesoftheKripkestructuresatisfyingconsistentsubsetsofSub’(q).Rather,wemustmakeshownin[Faginetal.,19901,weneedtomakeatmostlSub(q)lcopiesstate,sothesizeoftheresultingstructureisatmostlSub(q)12Isub(‘)l.360ItR.FAGINANDJ.Y.HAI.PERNcanbeshownthatthisresultisessentiallyoptimal,inthatthereisasequenceofformulasPl,Pz,...andaconstantc>0suchthat(1)ISW5(9L)Iq.ForeachformulamGZ,,,,oftheform1K1~,weselectsomestatet,,suchthat(M,t.)>T*(thereissuchastatetv,since(M,SO)k7KIq’J).LetTconsistsofs,,,alongwitheachofthesestatest(,.NotethatthecardinalityofTisatmost1+lSub(P)I.DefineM’=(S’.w’,~,Y’)bylettingS’betheunionofthesamplespacesofXZi,,Let12TheideaNthatpkforcesastructuretocontainabinarytreeofdepthk.Infact,theresultfollowsfromthecorrespondingresultforthemodalIoglcK(cf.[HalpernandMoses,1992;Ladner,1977]).Withoutanyassumptionsontheprobabilityassignment,1~,(q)=1actsliketheuoperator.Weomitdetailshere.St,GSbeastatesuchthatReasoningaboutKnowledgeandProbability361foreachs=T,bylettingT’ben-restrictedtoS’,byletting~=S’xS’,andletting9’(1,s)=Y;,.Itisstraightforwardtoshowthat(M’,,s.)+q,thatuM’satisfiesd,andthat‘M’isofsizepolynomialinlSub(9)1.Wenowconsiderthecomplexityofdecisionproceduresforthevalidityproblem.Thedifficultyofdecidingwhetherpisvalidwillbeafunctionofthelengthofq,writtenIql.Incomputingthislength,wealsoincludethelengthofthecoefficientsinprobabilityterms.(Sinceallcoefficientsarerational,thelengthofthecoefficientisjustthesumofthelengthsofthenumeratoranddenominator,writteninbinary.)IfCONSE.c#,butitisnotthecasethatUNIForSDPisinw’,tilentheualidiyproblemwithrespecttostmcturessatisfying.disconlpleteforexponentialtime(i.e.,thatisanalgorithmthatdecidesifaformulapisualidinallstructuresin~p~,andeletyexponentialtimesatisfying.c/thatmnsintimeexponentialproblemcanbereducedtotheLalidi~problen~).IfCONSe.tiorUNIForSDPisTHEOREM4.5.LetQ’beasubsetof{MEAS,CONS,OBJ.UNIF,SDP].ins/,thentheualidivforpolynomialPROOF.lowerandetal.,readerTheboundboundslogics1990],Theproblemwithrespecttostructuressatisfying.c#iscompletespace.proofrequirescomplexityWeMoses,lowerbounds,combiningofthebriefly1992]boundalonelet111qvalidityin[Halpernsketchandfollowsbethe[Fagin[Halpernantechniquesproblemandmainetal.,fromtheandforforideas1990]Moses,ofMoses,forprovinglogicshere,1992]upperandand[Faginthedetails.lowerthe1.WeFor=ontheofknowledgereferringfurtherspace1992].Wl(q)ofprobability,respectively.andspaceoflowerasdiscussedto[HalpernpolynomialforlogicstimepolynomialknowledgeexponentialabbreviationcanviewB,asamodaloperator,justlikeK,.IfUNIForSDPisin.aljthenitcanbeshownthatB,satisfiestheaxiomsofthemodalsystemKD45,but(inparticular,itsatisfiesonlywithouttheseassumptions,B,isunconstrainedtheaxiomsofthemodalsystemK).IfCONSisinM,Moretheneverythingsup-“reachableprobabilistically”isalsoconsideredpossible.formally,posewehaveprobabilisticallyasequenceofstatesSO,SI,...,SksuchthatSkisreachablefromSO,asfarasagent1isconcerned;thatis,s]+,isinS1,,,andPI,({sl+1})>0,forOl,G,ReasoningaboutKnowledgeandProbability363whereE~E~E~q(p.isanabbreviationforE~q,andE;+19isanabbreviationforItiswellknown(again,seeHalpernandMoses[1992])thatwecangetacompleteaxiomatizationforthelanguageofknowledgeandcommonknowl-edgebyaddingthefollowingaxiomsandruleofinferencetotheaxiomsystemdescribedinSection2:axiom,saysthatC~pcanbeviewedasaAxiomC3,calledtheftied-pointfixedpointoftheequationX=EJqA~).Infact,withalittleworkitcanbeshowntobethegreatestfixedpointofthisequation,thatis,itisimpliedbyallotherfixedpoints.Formostofourapplications,itisthefixed-pointcharacterizationofcommonknowledgethatisessentialtous(seeHalpernandMoses[1990]foradiscussionoffixedpoints).TheruleofinferenceRC1iscalledtheinductionrule.Thereasonisthatfromthefactthatp*ECpisvalid,wecaneasilyshowbyinductiononkthatp=E:qisvalidforallk.Itfollowsthatp=C~pisvalid.Infact,thesameproofcanbeusedtoshowthatforanystructureM,ifq-E~pisvalidinM,thenq*C~qisvalidinM(seeHalpernandMoses[1990]forfurtherdiscussionofthesepoints).ItisperhapsnotsurprisingthatifweaugmentAX~~~~withtheaxiomsforcommonknowledge,wegetacompleteaxiomatizationforthelanguageofknowledge,commonknowledge,andprobabilityforstructuressatisfyingMEAS.Ifwewanttodealwithnonmeasurablestructures,wemustusetheaxiomsystemAXratherthanAX~~~s.Andagainwegetsmallmodeltheoremsandanexponential-timecompletedecisionprocedure(regardlessofwhataddi-tionalassumptionsamongMEAS,OBJ,UNIF,andSDPwemake).Theproofsinvolveacombinationofthetechniquesfordealingwithcommonknowledge,andthetechniquesforprobabilityintroducedin[Faginetal.,1990]andtheprevioussection.Weomitdetailshere.In[HalpernandMoses,1990],itwasobservedthatcommonknowledgeisoftennotattainableinpracticaldistributedsystems,butweakervariantsofitare.Oneobviousvarianttoconsiderisaprobabilisticvariant(indeed,thiswasalreadymentionedassomethingtoconsiderin[HalpernandMoses,1990]).RecallthatwedefinedK,hptobeanabbreviationforK,(w,(p)>b).WenowextendoursyntaxtoallowmodaloperatorsoftheformE:andC~.Wedefine(A4,s)>E~qiff(hf,s)I=K,hpforalliqG.ByanalogytoC~p,wewantC;vtobethegreatestfixedpointoftheofC~q,equationX@E:(pAX).Theobviousanaloguetothedefinitionnamely,E;PA(E&)zqA““”doesnotwork.Forexample,considerastructureMforknowledgeandprobabilitydefinedasfollows:TherearefourstatesinM,sayS1,S2,S3,S4.Agent1cannotdistinguishs,fromS2andcannotdistin-guishs~fromS4,whileagent2cannotdistinguishs,froms~andcannotsymmetricclosureofdistinguishsofromS4.Thus,%,isthereflexive{(s,,SZ),(s~,S4)}(i.e.,~istheleastrelationcontaining(sl,Sz)and(s~,S4)thatisreflexiveandsymmetric)whileEZisthereflexivesymmetricclosureof{(s1,S3),(S2,S4)}.WetaketheprimitivepropositionptobetrueatS2ands3,3R.FAGINANDJ.Y.HALPERNFIG.1.TheKripkestructureM..1.Weremarkthatthisactuallyisageneralizationofthenonprobabilisticcase.ThereasonisthatifwedefineF;p==trueandF~+1P=E~(pAF:q),thenwegetFc~p=E~p(sincebothE~(pA$)wE~qAE~#andE~p*parevalid).Theanalogousfactsdonotholdonceweaddprobabilities,aswehavealreadyobserved.13Thefollowinglemmashowsthatthisdefinitionindeeddoeshavetherightproperties:h3’wMAX+that5.1.C;pE$.(qAX).Wefirstc’:p*ist}legreatestftied-pointsolutionsolutionoftheequationequation,PROOF.is,thatshowthatC;qisafixed-pointoftheE~(qAC:p)isvalid.Oneimplicationisstraightforward:ifE:.(PAC:p)holdsat(M,s),thensodoesE:(pA(F$)kq)foreachk,sinceC:p~(F$~pisvalid.Thatis,(F$k+‘pholdsforeachkat(M,s),andsoC:pholdsat(M,s).Asfortheotherimplication,assumethatC:pholdsat(M,s).Hence,(F~)~+lq,thatis,E:(PA(F/?)kq’),holdsat(M.s)foreachk.Foreachagenti,letA,,~bethesetofstatesinS,,wherepA(~~)kqholds,itfollowsthat(V,,,,)*(A,,L)fork=1,2....Since(M,s)%E~(pA(F~)kq),131tismtercstingtonotethatthemfmiteconjunctionE:pAslightlydifferentfixed-pojntequation,namelyX-E~pAE:X.MondercrandSamct[1980].Bothcfefmitionsaregeneralizationssince,asweobservedabove,E(,(qA.Y)isequivalenttoEC;qAtothefixed-pointequationEbpAEC,X.Thetwodefimtlonsareonctouseseemstodependontheapplication.Ourdefinition)ZAisasolutiontoaThisisthedefinitiontakenbyofthenonprobabilisticcase,E(JX,soCcpISalsoasolutlonquitesimilar.Whichistherightseemstobesomewhatmore(E:[HalpernandTuttle,1993].aPProPri~teinanalyzingprobabilisticcoordinatedattackandByzantine~greementprotocolsReasoningaboutKnowledgeandProbability365theory>b,foreachagentiandforallk.ItisastandardresultofprobabilitycA,,ksuchthatB,,~ismeasurableandp,,,(B,,k)>bthatthereexistsB,~_[Halmos,1950;Neveu,19].Itisstraightforwardtoverify,byinductiononk,that(F~)~+1P+(~&)$Pisvalid.(pROOF.Thecasek=Oiseasy,since(F:)(~=~cftrue.Forthereductivestep,notethatthevalidityof(F~)~+lp*(f’:)$pA(F~)k+lP)-E~(pA(F~)kp).ButthislastimpliesthevalidityofE&pformulaisprecisely(F$L+2P=(F&+‘p.)Thus,wehaveA,,>,4,~2Al~~....Withoutlossofgenerality,wecanassumealsothatB,,~B,,~5B,,~~0”4(sincewecanalwaysreplaceB,,~bytheunionofB,,~,fork’>k).ThesetB=(lv=,B,,~kameasurableset;itiseasytoseethatitmusthavemeasurepAC:(p)holdsatB,..Itthusfollowsthata;’leastb.Byconstruction,E:(pAC$Jp))holdsat(M,s),asdesired.WenowshowthatC;qisthegreatestfixedpoint.Assumethat#isafixedpointinastructureM,thatis,thatM>#=E:(pAI/J).Wewanttoshowonk,thatM+++(F:)$P.thatill>~-C:p.Wefirstshow,byinductionSince(F~)Op=~,~truebydefinition,theresultisimmediateinthecaseofk=O.Fortheinductionstep,supposeM&~*(F:)’”p.ItfollowseasilythatHence,sinceM1=+=E~(qA+),weMbE~(pAq?)_E~(pA(F$’’ip).mustalsohaveM1=++E~(pA(F~)’’p).But(F&’)n+1P=~C~E~(pASoMkY*(F.)b“’+lP.Thiscompletestheinductivestep.Itnow(F:)”@).followsthatif(M,s)i=@,then(M,s)I=(F~)Apforallk,andhencethat(M,S)i=C~p.Thus,Mk+=C:p.ThisprovesufixedpointoftheequationX*E:(pAX).ItisnoweasytocheckthatwehavethefollowingforE~andC~.CP1.CP2.RCP1.E~p*A,.~Klh(p.thatC:pisthegreatesttotheaxiomsanaloguesC~p*E~(pAC~p).From+=E~(~Ap)infer~*C:p.Weremarkthattheseaxiomsandruleofinferencearesoundinallstructuresforknowledgeandprobability.Andagain,wecanactuallyshowthefollowingstrengtheningofRCP1:ForanystructureM,if*=E:(q!JAp)isvalid,inMthenq!J~C;pisvalidinM.Itcanbeshownthattheseaxiomsandinferencerule,togetherwiththeaxiomsandinferencerulesC1–C3andRC1forcommonknowledgediscussedaboveandAX~~A~(respectively,AX)givesusasoundandcompleteaxiomati-zationforthisextendedlanguageinthemeasurablecase(respectively,inthegeneralcase).Moreover,wecanproveasmallmodeltheorem,andshowthatthevalidityproblemforallvariantsofthelogiciscompleteforexponentialtime.Theseproofsarequitedifficult;wehopetoprovidethedetailsinalaterpaper.6.ConclusionsWehaveinvestigatedalogicofknowledgeandprobabilitythatallowsexplicitreasoningaboutprobability.Wehavebeenabletoobtaincompleteaxiomatiza-sometionsanddecisionproceduresforourlogic.Wehavealsoidentifiedimportantpropertiesthatmightholdoftheinterrelationshipbetweenagents’probabilityassignmentsatdifferentstates.Itseemstousthatthemostimportantareaforfurtherresearchliesinhavingabetterunderstandingofwhattheappropriatechoiceofprobability366R.FAGINANDJ.Y.HALPERNspaceis.Somediscussionofthisissueappearsin[FischerandZuck,1988];amoregeneraltreatmentappearsin[HalpernandTuttle,1993].UsingtheideasinthispapertogetherwithMoses’recentwork[1988]onresource-boundedandHalpernhavemadeprogressoncapturingreasoning,Moses,Tuttle,inter-actiL’eproofsandzeroknowledge[Goldwasseretal.,19]intheframeworkofknowledgeandprobabilitydiscussedinthispaper.Theseresultsappearin[Halpernetal.,1988].Theanalysisin[Halpern&al..1988]isdoneusingthesamestyleofprobabilityassignmentasinourexamplesinSection3,thatis,theytakeS,,,,,,,~toconsistofallpointswiththesameglobalstateas(r,m).ThisprobabilityassignmentsatisfiesOBJandUNIF,butnotnecessarilySDP.Althoughthisisnottheonlychoiceofprobabilityassignmentthatisreason-ableinthiscontext,therearegoodgroundsforbelievingthatnoreasonablechoicewillsatisfySDP.Iftherearenonprobabilisticeventsinasystemaswellasprobabilisticevents,SDPseemsinappropriate.Aswesaidearlier,ageneralframeworkfordecidingwhichchoiceofprobabilityassignmentisappropriate,presentedintermsofadversaries,appearsin[HalpernandTuttle,1993].Asthisdiscussionmaysuggest,althoughourunderstandingofthesubtleinteractionbetweenknowledgeandprobabilityisincreasing,moreworkneedstobedoneinthisarea.Itwouldbeespeciallyusefultohavealargerbodyofexamplesonwhichtotestourideas.Theeconomicsandgametheoryliteraturemaybeagoodsourceforsuchexamples.Weexpectthatfurtherprogresscanbemadebycombiningtheintuitionsfrombothcomputerscienceandgametheory.ThefoundationsofthispaperweregreatlyinfluencedbydiscussionsthesecondauthorhadwithYoramMosesandMarkTuttleinthecontextoftheirjointworkoncapturinginteractiveproofs[Halpernetal.,1988].Inparticular,theirobservationthatitwasnecessarytoallowS,,,tobeasubsetof~(s)causedustorethinkmanyofourideas.TheyalsosuggestedtakingK,fi~tobeanabbreviationforKl(wl(p)>b)ratherthanw,(p)>b,aswasdoneinanearlydraftofthispaper.Asusual,MosheVardi’scommentshelpedimproveboththestyleandcontentofthepaper.Finally,wewouldliketothankananonymousrefereeforaclosereadingofthepaperandmanyusefulcommentsandsuggestionsthatimprovedthepresentationoftheresults.ACKNOWLEDGMENTS.REFERENCESAUMANN,R.J.,1976.Agreeingtodisagree..4nn.Stat.4,6,I?36–1239,CAVE,J.1983.Learningtoagree.Econ.Lett.12,147-152.FAGIN,R.,HALPIZRN,J.Y.,ANDMEGIDDO,N.,1990.Alogicforreasoning87,1/2,78–128.Inj.Comput.FELDMAN,Y.1984.~boutprobabdities.probabili-1.Wiley,J,Adecidable63,11–38.AnZntroductlonRpropositionalprobabilisticTheoydynamicandlogicwithexphcltvolumeties.Inf.FELLER,FISCHER,Comput.W.Control,1957.toProbcitrdlQE.,ltsAppkrtlons,NewYork.M.J.ANDLADNER,1979.PropositionaldynamicIoglcofregularprograms,$sf.Scl.18,2,194–211.FISCHER,M.J.ANDZUCK,L.D.,1987.Relatlveknowledgeandbelief(extendedabstract).Tech.Rep.YALEU\\DCS/TR-5.YaleUniv.FISCHER,M.J.ANDZUCK,L.D.,1988.Reasoningaboutuncertaintyinfault-tolerantdistributedsystems.Tech.Rep.YALEU/DCS/TR-3.YaleUniv.GAIFMAN,H.,1986.Atheoryofhigherorderprobabdities.InTbeoretwalAspectsofReasoningaboutKnowledge:Proceedingsofthe1986Conferettce,J.Y.Halpern,cd.,Morgan-~aufmdnn,SanMateo,Calif.,pp.275-292.ReasoningGOLDWASSER,aboutKnowledgeandProbabilityThe367knowledgecomplexityofinteractiveS.,MICALI,S.,ANDR.ACKOFF,C.,19.proofsystems.SIAMJ.Cornpaf.18,1(Feb.),186-208.HALMOS,P.,1950.MeasureTheo~.VanNostrand,NewYork.HALPERN,J.Y.,1987.Usingreasoningaboutknowledgetoanalyzedistributedsystems.InAnnualReliewofComputerScience,vol.2.J.F.Traub,B.J.Grosz,B.W.Lampson,andN.J.Nikson,eds.AnnualReviewsInc.,PaloAfto,Calif.,pp.37-68.HALPERN,Artif.tat.Int.HALPERN,HALPERN,J.Y.,1991.Therelationshipbetweenknowledge,belief,andcertainty.,4fzrz.Math.4,301-322.J.Y.ANDMCALLISTER,D.A.,19.Knowledge,likelihood,andprobability.Compu-Znt.5,151–160.J.Y.ANDMOSES,Y.,1990.Knowledgeandcommonknowledgeinadistributedenvironment.J.ACM37,3(July),9–587.AguidetocompletenessandcomplexityformodallogicsHALPERN,J.Y.ANDMOSES,Y.,1992.ofknowledgeandbelief.Artif.Int.,319–379.HALPERN,J.Y.,MOSES,Y.,ANDTUTTLE,M.R.,1988.Aknowledge-basedanalysisofzeroonTheo)yofCompating(Chicago,Ill.,knowledge.InProceedingsofthe20thACMSymposaunMay2-4).ACM,NewYork,pp.132-147.Ardf.Int.32,3,HALPERN,J.Y.ANDRABLN,M.O.,1987.Alogictoreasonaboutlikelihood.379-405.HALPERN,J.Y.ANDTUTTLE,M.R.,1993.Knowledge,probability,andadversaries.J.ACM40,4(Sept.),917-962.H.AR’r,S.ANDSHARLR,M.,1984,Probabilistictemporallogicsforfiniteandboundedmodels.InProceedingsofthe16thACMSymposiumonTheoyofComputing(Washington,DC,Apr.30-May2).ACM,NewYork,pp.1-13.HINTIKKA,J.,1962.KnowledgeandBelief.CornellUniversityPress,Ithaca,NY.toModalLogic.Methuen,London.HUGHES,G.E.ANDCRESSWELL,M.J.,1968.AnIntroductionProbabilisticPDL.J.COnZpUt.Syst.SCZ.30,162-178.KOZEN,D.,1985.KRLPKE,S.,1963.Asemanticalanalysisofmodallogic.I:Normalmodalpropositionalcalculi.Z.Math.LogikGrundl.Math.9,67-96.(AnnouncedinJ.Symb.Logic24,1959,p.323.)LADNER,R.E.,1977.Thecomputationalcomplexityofprovabilityinsystemsofmodalproposi-6,3,467–480.tionallogic.SIAMJ.Compat.LISHMANN,D.ANDSHELAH,S.,1982.Reasoningabouttimeandchange.Inf.Control53,165-198.LENZEN,W.,1978.RecentworkmepistemicMAKINSON,D.,1966.OnsomecompletenessMath.12,379-384.logic.ActsPhil.Fen.30,1-219.theoremsinmodallogic.Z.Math.LogikGrandl.MILLER,D.,1966.Aparadoxofinformation.Iht.J.Phil.Sci.,17.MONDERER,D.ANDSAMET,D.,19.ApproximatingcommonknowledgeGamesandECOtIOnUCBehaL1iorWorld,1,170-190.withcommonbeliefs.MOORE,R.C.,1985.ConunomenscAformaltheoryofknowledgeandaction.InFormalTheoriesoftheJ.HobbsandR.C.Moore,eds.AblexPublishingCorp.,Norwood,N.J.,knowledge.InProceedingsofthe2ndconferenceM.Y.Vardi,cd.,Morgan-Kaufmann,onTheoret-pp.319-358.MOSES,Y.,1988.icalAspectsResource-boundedaboutofReasoningKno}vledge.SanMateo,Calif.,pp.261-276.daCalCUldesProbabil&.Mason.NEVEU,J.,19,BasesMathentatlqueslogic.Artif.Znt.28,71-87.NILSSON,N.,1986.ProbabilisticPRATT,V.R.,1979.ModelsofprogramIogics.InProceedalgsofthe20thIEEEFoundationsofComputerSccence.IEEE,NewYork,pp.115-122.RUSPINI,E.H.,1987.EpistemicJointAMathematicallogics,ConferenceTheoryprobability,onArtificialandthecalculusIntelligenceofevidence.ofthe10thInternationalSHA.CER,G.,1976.(IJCAI-87),SymposuanonofEcidence.PrincetonUniversityInProceedingspp.924–931.Press,Princeton,ofN.J.EssaysinHonorSKYRm,B.,1980.Higherorderdegreesofbelief.InProspectsforPragmatism:F.P.Ramsey.D.H.Mellor,cd.,CambridgeUniversityPress,Cambridge,U.K.RECEIVEDAPRIL1990;REVISEDAUGUST1992;ACCEPTEDOCTOBER1992JwrndoftheAwxi~ttontorComputmgM~chmery,Vol.$1,No2,Mmch199.!
