多主體之間的互知推理研究

初心時見多主體的恰當決策有人知道下午下雨，下午回家時應該注意一把傘。這是一個單主體系統。一般地說,單主體系統中主體A的某個恰當決策,取決于他是否知道事實(或原理)P。曹操敗走華容道岔口,大路并無動靜,小路幾處煙起。曹操不走大路,偏走小路華容道,因為他知道諸葛亮深知“用兵虛則實之,實則虛之”,結果反而中了諸葛亮的埋伏。這里,問題出在曹操光知道諸葛亮知道“用兵虛則實之,實則虛之”,但不知道諸葛亮知道曹操知道諸葛亮知道“用兵虛則實之,實則虛之”。諸葛亮勝在他的“知道”比曹操的高出了一階。這是一個二主體系統。一般地說,二主體系統中主體A的恰當決策,不光取決于A是否知道事實P,而且取決于A是否知道另一個主體B是否知道P,如果答案都是肯定的,那么還要取決于A是否知道B知道A知道B知道P,……,等等。奕棋,商務談判,都是典型的二主體系統。如果主體超過兩個,是三個,四個,甚至更多,這樣的多主體系統中關于知道的推理及基于這種推理之上的恰當決策,將變得極為復雜。例如,假設:汽車駕駛員只有在確信別的駕駛員都遵守交通規則時自己才遵守規則,那么,一個汽車駕駛員光知道“紅燈停,綠燈行”的交通規則是不會按該規則開車的,因為他并不知道所有駕駛員都知道這條規則。現在的問題是,如果一個駕駛員不光自己知道這一規則,而且知道所有的駕駛員都知道這條規則,他是否一定遵守規則呢?回答是仍然不一定。因為他雖然知道所有的駕駛員都知道這條規則,但是并不一定知道所有的駕駛員都知道所有的駕駛員都知道這條規則。如果事實上他并不知道所有的駕駛員都知道所有的駕駛員都知道這條規則,那么,他有理由認為,除了他以外的所有駕駛員雖然都知道這條規則,但可能都不知道別的駕駛員知道這條規則,因而都不遵守規則,因而他自己也不遵守規則。這樣的問題可以類似地問下去,回答都是“不一定”,直到問題中的“知道”重復的遍數等于駕駛員的人數。也就是說,假設這樣的駕駛員有n個,這n個駕駛員就組成了一個n(元)主體系統,在這個系統中,每個駕駛員都遵守“紅燈停。綠燈行”的交通規則的必要條件是:所有的駕駛員都知道所有的駕駛員都知道所有的駕駛員都知道……(重復n遍)這一規則。(當然,這里假設每個駕駛員都有完備的推理能力)認知邏輯的發展多主體之間的互知推理的復雜性在于,這種推理的對象中,不僅包括對象世界的知識,而且包含多個具有推理能力的主體;推理者對其他主體的思考及其結果進行推理,這些主體同樣對推理者的思考及其結果進行推理。這使得推理的素材是彈性的,動態的,隨著推理的過程不斷變化的。這種推理,是對人的日常思維能力的挑戰,也是對邏輯學的挑戰。對于知道推理的形式分析,最早可追溯到20世紀50年代初。芬蘭哲學家馮·賴特(G.H.vonWright)在1951年出版的《模態邏輯》一書,首次提出和論述了認知邏輯的思想;芬蘭哲學家辛提卡(J.Hintikka)繼續了這方面的研究,他于1962年發表的《知識與信念》一書,為認知邏輯奠定了理論基礎。但一般地說,認知邏輯所研究的有關知道(以及信念)的性質及其推理,還只限制于單主體系統。運用現代邏輯的方法,對多主體系統中的知道特別是互知推理的研究,是近十年的事。推動上述研究的主要動力,直接來自于經濟學、軍事學、計算機科學和人工智能等學科對邏輯實用性的要求。經濟學中的市場和戰爭學中的戰場,都是典型的多主體系統,和中國做飛機生意的美國波音公司,就是一個站在華容道前的曹操,他不光要知道波音飛機的實際價值,而且要知道中國是否知道這種實際價值,而且要知道中國是否知道美國知道中國知道這種實際價值…。關于知道的推理,特別是多主體系統中關于互知推理的研究成果,首先受到了上述這些學科站在實用立場上的重視和歡迎。反映這方面研究成果的一本代表性論著,是由美國學者羅納德·費金(Ronald.Fagin)等四人所著的《關于知道的推理》,(《ReasoningAboutKnowledge》),1995年出版,1996年再版。該書出版后,立即受到了學術界的重視和高度評價,有的經濟學家甚至認為,該書對于“互知(interactiveknowledge)”的研究,是經濟學近十年的最重要的成果之一。本文將圍繞典型實例分析,通過構造關于知道的模型,看看邏輯語義學的方法,是如何成功地運用于分析多主體之間的互知的。根本原因:有兩組孩子額上有現實的信息一個教室中有10個孩子。其中,有7個孩子額上沾有泥巴。每個孩子都能看到別的孩子額上是否有泥巴,但無法看到自己的。這時老師走進教室,對孩子們說:“你們之中至少有一人額上有泥巴”。然后,他問:“誰知道自己額上有泥巴?知道的請舉手。”他如是連續問了六遍,無人舉手,當問到第七遍的時候,所有額上有泥巴的孩子都有舉起了手。假設所有的孩子都有最佳的邏輯分析能力,那么,他們是如何思考并得出結論的?先運用日常思維的方式來求解。假設只有一個孩子額上有泥巴,那么,在老師第一遍提問時,他就會舉手,因為他看到除他之外所有的孩子額上都沒有泥巴,既然至少有一個孩子額上有泥巴,那么這個有泥巴的孩子自然是自己;假設有兩個孩子額上有泥巴,他們都看到并且只看到一個孩子額上有泥巴,當老師第一遍提問時,他們無法確定自己是否有泥巴因而都不舉手,但是當老師的第一遍提問結束后,他們立即都明白自己額上有泥巴,因為如果自己額上無泥巴,則說明只有一個孩子有泥巴,在老師第一遍提問后這個唯一有泥巴的孩子就會舉手。這樣,當老師第二遍提問時,兩個有泥巴的孩子都舉起了雙手;同理,如果有三個孩子額上有泥巴,他們就會根據第二遍提問時無人舉手而立即判斷出自己額上有泥巴,因而在第三遍提問時舉手。因此,一般地,額上沾泥巴的孩子的人數,正好等于他們都舉手時老師提問的次數。細心的讀者會發現一個很有意思的問題。在老師進教室之前,事實上每個孩子都已經知道他們之中至少有一個人額上有泥巴,因此,老師所說的“你們之中至少有一人額上有泥巴”,似乎是句新信息量為零因而完全可以不說的廢話;但另一方面,沒有老師的這句話,老師的提問即使重復一萬遍,也不會有孩子舉手。這是怎么回事呢?事實上,如果至少有兩個孩子額上有泥巴,那么,所有孩子都知道至少有一個孩子額上有泥巴,但是,如果恰有兩個孩子有泥巴,那么,雖然所有的孩子都知道至少有一個孩子額上有泥巴,但并非所有的孩子都知道所有的孩子都知道至少有一個孩子有泥巴(額上有泥巴的孩子A會認為,如果自己額上無泥巴,那么額上有泥巴的孩子B就會猜測,沒有孩子額上有泥巴,這就是說,A并不知道所有的孩子都知道至少有一個孩子額上有泥巴);一般地,如果n個孩子額上有泥巴,那么“所有的孩子都知道…(重復n-1遍)至少有一個孩子額上有泥巴”成立,但“所有的孩子都知道…(重復n遍)至少有一個孩子額上有泥巴”不成立。而在上例中,“所有的孩子都知道…(重復n遍)至少有一個孩子額上有泥巴”,是n個額上有泥巴的孩子作出正確判斷的必要條件。老師當眾說的那句話,使得“所有的孩子都知道…(重復≥n遍)至少有一個孩子額上有泥巴”成立。因此,老師的話當眾而說,對于該題的解決是必不可少的。如果說前一段的分析尚在日常思維的能力之內的話,那么后一段則有點超出這種能力了。這就需要提供形式的工具。建立“知道”的語義模型,就是這樣一種嘗試。主體i不明知p在形式語言K中:1,2,…,n分別表示系統中n個不同的主體。p,q,r,s…分別表示如“舊金山正在下雨”、“冰冰額上有泥巴”這樣一些原子命題,它們的集合Φ構成作為主體認知和推理對象的外部世界的知識。讀作并表示“并非”,讀作“合取”,表示“并且”。模態算子Ki表示“主體i知道…”。因此,Kip讀作“主體i知道p”,如果p表示“舊金山在下雨”,那么Kp就表示“主體i知道舊金山并不在下雨”;而Kip則表示“主體i不知道舊金山在下雨”;原子命題是公式;如果A是公式,則A是公式;如果A和B是公式,則A∧B是公式。如果A是公式,則KiA是公式。A∨B(讀作“A析取B”,表示“A或者B”)定義為(A∧B);A→B(讀作“A蘊含B”,表示“如果A,那么B”),定義為A∨B;AB(讀作“A當且僅當B”),定義為(A→B)∧(B→A)T是p∨p這樣的永真公式(稱為重言式)的縮寫,表示“真”;F定義為T,表示“假”。現在,我們可以把在自然語言中非常復雜的關于知道的命題表述得十分簡明。例如,以下公式K1K2p∧K2K1K2p表示“主體1知道主體2知道p,但是主體2不知道主體1知道主體2知道p”。我們可以用“知道”來定義主觀模態“可能”:主體i認為A是可能的,當且僅當主體i不知道A,即K1A。而象“主體i不知道是否p”這樣的斷定,實際上是說“主體i認為P和p都是可能的”,也就是說“主體1既不知道p也不知道p”,即K1p∧K1p。考慮下面這個有關水門事件的斷定:迪恩不知道尼克松是否知道迪恩知道尼克松知道麥卡德偷竊了奧博林在水門的辦公室。令主體1表示迪恩,主體2表示尼克松,p表示“麥卡德偷竊了奧博林在水門的辦公室”,則該斷定可表達為形式語言K的語義解釋,關于“知道”的模型以上討論的是形式語言K的語法,下面討論K的語義,即要構造模型,用以判定K語言中公式的真假。這樣的模型,記為M,是一個克瑞普克結構(W,V,R1,…,Rn),其中,W是一可能世界集;V是一個解釋,它給任一可能世界,指派以一個確定的真值賦值,即對任一wi∈W,和任一原子命題p∈Φ,V(p,wi)=T或V(p,wi)=F,但不能二者。如果p表示“舊金山正在下雨”,則V(p,wi)=T表示在可能世界wi中,舊金山正在下雨;Ri是W上的二元關系。如果wi和wj有關系Ri,記為wiRiwj,表示主體i依據在可能世界wi中的信息,認為可能世界wj是可能的。(一個世界,是一個事件集,只要其中不包括矛盾事件,就是一個可能世界;但一個可能世界,對于某個主體來說,完全可能是不可能世界,如果這個主體知道這個可能世界中某個事件的矛盾事件)這里,我們進一步規定Ri是同時滿足自返、對稱和傳遞關系的等價關系,這樣,如果主體i在可能世界wi中覺得wj是可能的,這說明在可能世界wi和wj中,主體i具有對外部世界同樣的信息,從而對他來說,這兩個世界是無法區分的。因此,wiRiwj也表述為“主體i無法區分wi和wj”。一個公式A在一個結構(模型)M的一個給定的可能世界wi中真,記作(M,wi)|=A,讀作(M,wi)滿足A。(M,wi)KA當且僅當對任一wj∈W,如果wiRiwj,則(M,wj)KiA。上述模型所表達的核心意思是:主體i知道p,當且僅當p在主體i認為可能的所有可能世界中都真。我們用一個實例的圖示來描述這一點,克里普克結構的優點之一是可圖示的。上圖所示的模型M=(W,V,R1,R2),其中,W={w1,w2,w3},p在w1和w3中真,而在w2中假。主體1不能區分w1和w2(即主體1在w1認為w2是可能的,由R的對稱性,自然在w2同樣認為w1是可能的,即w1R1w2和w2R1w1成立),主體2不能區分w1和w3。標有1,2的線段在wi(i=1,2,3)從自身指向自身,表示R關系的自返性,即表示wiRjwi(i=1,2,3;j=1,2),例如表示w3R1w3;標有1的線段的兩端指向w1和w2,表示主體1不能區分w1和w2,并表示R關系的對稱性。同樣,標有2的線段表示主體2不能區分w1和w3。令p表示“北京天晴”,則依據上圖,可得出以下結論:結論1:在可能世界w1,北京天晴,但主體1并不知道這一點,因為他在w1中認為w1和w2都是可能的(或者說依據他在w1的知識,他無法確定w1和w2究竟哪個是真實世界,即無法區分w1和w2),而p在w1中真,但在w2中假。結論2:主體2在可能世界w1知道北京天晴,因為在可能世界w1,主體2認為可能的世界是w1和w2,在這兩個可能世界中,p都是真的。結論3:主體2在可能世界w2知道并非北京天晴,因為主體2在w2中認為可能的世界只有w2自身,而在w2中,p真。同理,主體1在可能世界w3中知道北京天晴。結論4:在可能世界W1,主體1知道主體2知道北京是否天晴,因為在可能世界w1,主體1認為可能的兩個世界是w1和w2,在這兩個世界中,主體2都知道北京的天氣(見結論2和結論3)。也就是說,雖然在可能世界w1,主體1并不知道北京是否天晴,但是他知道主體2知道這一點。結論5:和結論4成為對比的是,在可能世界w1,雖然主體2知道北京天晴(結論2),但是他不知道主體1不知道這一點。因為在可能世界w1,主體2認為可能的兩個世界是w1和w3,在w1中,主體1不知道北京天晴(結論1),但在w3中,主體1知道北京天晴(結論3)。以上結論,可以用一個邏輯表達式概括:前面已經指出,一個可能世界是一個事件集,相應的命題在其中真或假。在以上的討論中,構成w和w的事件都是“北京天晴”,因此,似乎是兩個相同的世界因而可以略去一個。但事實上卻不能這樣。因為一個可能世界的規定,不光基于構成它的事件,而且基于主體認為它是否可能。例如,在可能世界w,主體1認為可能世界w是可能的,但在可能世界w3,他卻不這么認為,這樣,他在w1不知道北京天晴,而在w3則知道這一點。作為下標的的g在n主體系統中,如果所有的主體都知道所有的主體都知道…(重復≥n遍)A,則稱這n個主體掌握了關于A的共同知識(CommonKnowledge),或稱A是這n個主體的共同知識。在上文的實例分析中,可以看到共同知識在多主體系統的知道推理中的重要作用。這一多主體認知系統中的重要概念,最早是由路易斯在討論“協約”時提出的,他認為,某種東西要成為多方的“協約”,必須成為締約各方的共同知識,也就是說,締約各方不但都要知道協約的內容,而且要知道各方都知道協約的內容,等等。為了對共同知識進行形式刻劃,需要在語言K中增加新的算子EG和CG,滿足:如果A是公式,則EG、CG都是公式。G表示主體集{1,2,…,n}。EGA表示“G中每個主體都知道A”;CGA表示“A是G中所有主體的共同知識”。在不引起歧義的情況下,作為下標的G可以省略,即EGA和CGA分別記為EA和CA。如果{1,2,…,i}是G的一個真子集(即i<n),則E{1.2,…i}A表示在{1,2,…,i}中每個主體都知道A。這種寫法同樣用于C。這樣,K3C1,2p就表示主體3知道p不是主體1和主體2的共同知識。在模型M中作如下定義:(M,wi)EA,當且僅當對任一i∈G,(M,viKiA,即在可能世界wi中,EA真,當且僅當每個主體都知道A。令E1A表示EA,Ek+1A表示EEkA,則(M,wi)CA,當且僅當(M,wi)EkA(k≥n),即在可能世界wi中,CA真(A是所有主體的共同知識),當且僅當所有的主體都知道所有的主體都知道…(重復≥n遍)A。(注意,事實上,對于任意k>1和任意wi∈W,如果(M,wi)EkA,則(M,wi)Ek-1A)對共同知識可以作出一種有意思的直觀圖示,為此,先來定義何為從一個可能世界到另一個可能世界可通達。(1)對任意可能世界wj1和wj2,如果存在主體i,wj1Riwj2,則稱從wj1至wj2可通達,并稱這種通達為一步可通達;(2)對任意可能世界wj1、wj2和wj3,如果從wj1至wj2可通達,并且從wj2至wj3可通達,則從wj1至wj3可通達。并且,如果從wj1至wj2是k步可通達,從wj2至wj3是1步可通達,則從wj1至wj3是k+1步可通達。雖然一般模態邏輯都把結構中的R關系稱為可通達關系,但這里定義的可通達關系不同于Ri關系。第一,Ri關系是相對于某個主體i而言的,可通達關系不是相對于某個主體而言的,第二,存在可通達關系的可能世界之間,不一定有R關系成立。例如,圖1中從w2至w3可通達,但w2R1w3和w2R2w3都不成立。關于可通達關系,有兩條重要推論。推論1(M,wi)EkA,當且僅當(M,wi)A并且對所有wj,如果從wi至wjk步可通達,則(M,wj)A推論2(M,wi)CA,當且僅當對所有wj,如果從wi至Wj可通達,則(M,wj)A對k施歸納,易證推論1;推論2是推論1的直接推論。可以設想這樣一個示圖,其中,每個可能世界表示為一個點,任意兩個一步可通達的可能世界之間用線段聯接。以上兩個結論的意義在于,判定A是否為可能世界wi上的共同知識,只須看A是否在從wi可通達的點(可能世界)上都真;判定EkA在wi上是否為真,只須看A是否在從wik步可通達的點上都真。“雙側頭”的模型現在,嘗試構造語義模型,對“額上沾泥巴的孩子”作形式分析。假設孩子有n個,要證明的是,沾泥巴的孩子的人數,正好等于他們都舉手時老師提問的次數。自然需要假設,題目陳述的條件,例如,所有的孩子都足夠聰明,對所有孩子都是共同知識。令1,2,…,n分別表示n個不同的孩子。(xl,…,xn)表示可能世界,其中任一xi,xi=1,或者xi=0。如果xi=1,則表示孩子i額上有泥巴,否則表示沒有。顯然,對于n個孩子,這樣的不同可能世界共2個。例如,如果只有3個孩子,則可能世界{1,0,1}表示孩子1和孩子3有泥巴。假設這個可能世界就是真實世界。在這個世界中,在老師說話之前,孩子1能看到孩子2沒有泥巴而孩子3有泥巴,他唯一不能確定的是自己額上是否有泥巴,因此,他認為(1,0,1)(即真實世界)和(0,0,1)都是可能的。也就是說,孩子i在可能世界(a1,…,an)認為可能世界(b1,…,bn)是可能的,即(a1,…,an)Ri(b1,…,bn),當且僅當除了ai≠bi以外,(a1,…,an)和(b1,…,bn)完全相同。令Φ={p1,…,pn,p},其中pi表示“孩子i有泥巴”(i=1,…,n),p表示“至少有一個孩子有泥巴”。(M,(x1,…,xn))pi當且僅當x1=1。(M,(x1,…,xn))p當全僅當存在xj,xj=1。這樣,完成了對模型M=(W,V,R1,…,Rn)的定義。這一模型的優點之一是基于之上可以作出清晰直觀的圖示解析。令2n個點表示上述2n個不同的可能世界,并在任意兩個一步可通達的點之間用標有數字i的線段聯接(即如果孩子i在wi認為wj可能,則用標有i的線段聯接表示這兩個可能世界的點),這樣,長于空想想象的讀者可以知道,我們因此得到了一個n維立方體。下圖表示的就是當n=3(即假設只有3個孩子)時這樣的一個三維立方體。圖2中共有8個點,表示所有的8個可能世界。每兩個可能世界之間都有標有數字的線段聯接,例如,標有1的線段聯接(1,1,1)和(0,1,1),表示孩子1在這兩個世界的任何一個中都認為另一個世界是可能的。圖中也說明,從任何一個可能世界出發,其余的可能世界都是可通達的。從圖2立即可以得出(證明)許多結論,例如:結論1:每個孩子都知道除自己外哪個孩子額上有泥巴。不妨設可能世界(1,0,1)是現實世界,在這一世界中,孩子1認為可能的世界是(1,0,1)和(0,0,1),在這兩個可能世界中,孩子3都有泥巴,因此,孩子1知道孩子3有泥巴;同理,孩子2知道孩子1和孩子3有泥巴;孩子3知道孩子1有泥巴。結論2:“每個孩子都知道除自己外哪個孩子額上有泥巴”是所有孩子的共同知識。結論1的證明所選擇的可能世界帶有任意性,因此,“每個孩子都知道除自己外哪個孩子額上有泥巴”在所有可能世界中真,即在從任意一個可能世界可通達的所有可能世界中真,因此,是共同知識。結論3:(M,(1,0,1))Ep,即在可能世界(1,0,1)中,所有的孩子都知道至少有一個孩子額上有泥巴。自(1,0,1)一步可通達的可能世界有(1,1,1)、(1,0,0)和(0,0,1),在這四個可能世界中,p即“至少有一個孩子有泥巴”都真。結論4:(M,(1,0,1))E2p,即在可能世界(1,0,1)中,并非所有的孩子都知道所有的孩子都知道至少有一個孩子額上有泥巴。因為存在自(1,0,1)兩步可通達的可