多主体认知系统中的互知推理

在多主体认知系统中，每个主体都是一个推理者。多主体之间互知推理的复杂性在于，这种推理的对象中，不仅包括对象世界的知识，而且包含系统中其他的同样正在进行推理的主体；推理者对其他主体的思考及其结果进行推理，这些主体同样对推理者的思考及其结果进行推理。这使得推理的素材是弹性的，动态的，随着推理的过程不断变化的。这种推理，是对人的日常思维能力的挑战，也是对逻辑学的挑战。　
本文通过构造关于知道的模型，用逻辑语义学的 方法 ，来刻划多主体之间的互知。　
形式语言k　
在形式语言k中：　
1,2,…,n分别表示系统中n个不同的主体。　
p,q,r,s…分别表示如“旧金山正在下雨”、“冰冰额上有泥巴”这样一些原子命题，它们的集合φ构成作为主体认知和推理对象的外部世界的知识。　
模态算子k[,i]表示“主体i知道…”。因此，k[,i]p读作“主体i知道p”。　
原子命题是公式；如果a是公式，则┐a是公式；如果a和b是公式，则a∧b是公式。如果a是公式，则k[,i]a是公式。　
a∨b（读作“a析取b”，表示“a或者b”）定义为┐(┐a∧┐b)；　
a→b（读作“a蕴含b”，表示“如果a，那么b”）定义为┐a∨b；　
附图（读作“a当且仅当b”）定义为(a→b)∧(b→a)；　
t是p∨┐p这样的永真公式（称为重言式）的缩写，表示“真”；f定义为┐t，表示“假”。　
现在，我们可以把在 自然 语言中非常复杂的关于知道的命题表述得十分简明。例如，公式

　　k[,1]k[,2]p∧┐k[,2]k[,1]k[,2]p　
表示“主体1知道主体2知道p，但是主体2不知道主体1知道主体2知道p”。　
我们可以用“知道”来定义主观模态“可能”：主体i认为a是可能的，当且仅当主体i不知道┐a，即┐k[,1]┐a。而像“主体i不知道是否p”这样的断定，实际上是说“主体i认为p和┐p都是可能的”，也就是说“主体i既不知道┐p也不知道p”，即┐k[,i]┐p∧┐k[,i]p。　
考虑下面这个有关水门事件的断定：迪恩不知道尼克松是否知道迪恩知道尼克松知道麦卡德偷窃了奥博林在水门的办公室。令主体1表示迪恩，主体2表示尼克松，p表示“麦卡德偷窃了奥博林在水门的办公室”，则该断定可表达为

　　┐k[,1]┐(k[,2]k[,1]k[,2]p)∧┐k[,1](┐k[,2]k[,1]k[,2]p)　
形式语言k的语义解释，关于“知道”的模型　
模型m，是一个克里普克结构(w,v,r[,1],…,r[,n])，其中，w是一可能世界集；v是一个解释，它给任一可能世界，指派以一个确定的真值赋值，即对任一w[,i]∈w，和任一原子命题p∈φ，v(p,w[,i])=t或v(p,w[,i])=f，但不能二者。如果p表示“旧金山正在下雨”，则v(p,w[,i])=t表示在可能世界w[,i]中，旧金山正在下雨；r[,i]是w上的二元关系。如果w[,j]和w[,k]有关系r[,i]，记为w[,j]r[,i]w[,k]，表示主体i依据在可能世界w[,j]中的信息，认为可能世界w[,k]是可能的。（一个世界，是一个事件集，只要其中不包括矛盾事件，就是一个可能世界；但一个可能世界，对于某个主体来说，完全可能是不可能世界，如果这个主体知道这个可能世界中某个事件的矛盾事件。）这里，我们进一步规定r[,i]是同时满足自返、对称和传递关系的等价关系，这样，如果主体i在可能世界w[,j]中觉得w[,k]是可能的，这说明在可能世界w[,j]和w[,k]中，主体i具有对外部世界同样的信息，从而对他来说，这两个世界是无法区分的。因此，w[,j]r[,i]w[,k]也表述为“主体i无法区分w[,j]和w[,k]”。　
一个公式a在一个结构（模型）m的一个给定的可能世界w[,i]中真，记作附图　
附图　
上述模型所表达的核心意思是：主体i知道p，当且仅当p在主体i认为可能的所有可能世界中都真。我们用一个实例的图示来描述这一点，克里普克结构的优点之一是可图示的。　
附图　
上图所示的模型m=(w,v,r[,1],r)，其中，w=｛w[,1],w[,2],w[,3]｝，p在w[,1]和w[,3]中真，而在w[,2]中假。主体1不能区分w[,1]和w[,2]（即主体1在w[,1]认为w[,2]是可能的，由r的对称性，自然在w[,2]同样认为w[,1]是可能的，即w[,1]r[,1]w[,2]和w[,2]r[,1]w[,1]成立），主体2不能区分w[,1]和w[,3]。标有1,2的线段在w[,i](i=1,2,3)从自身指向自身，表示r关系的自返性，即表示w[,i]r[,j]w[,i](i=1,2,3;j=1,2)，例如表示w[,3]r[,1]w[,3]；标有1的线段的两端指向w[,1]和w[,2]，表示主体1不能区分w[,1]和w[,2]，并表示r关系的对称性。同样，标有2的线段表示主体2不能区分w[,1]和w[,3]。　
令p表示“北京天晴”，则依据上图，可得出以下结论：　
结论1。在可能世界w[,1]，北京天晴，但主体1并不知道这一点，因为他在w[,1]中认为w[,1]和w[,2]都是可能的（或者说依据他在w[,1]的知识，他无法确定w[,1]和w[,2]究竟哪个是真实世界，即无法区分w[,1]和w[,2]），而p在w[,1]中真，但在w[,2]中假。　
结论2。主体2在可能世界w[,1]知道北京天晴，因为在可能世界w[,1]，主体2认为可能的世界是w[,1]和w[,2]，在这两个可能世界中，p都是真的。　
结论3。主体2在可能世界w[,2]知道并非北京天晴，因为主体2在w[,2]中认为可能的世界只有w[,2]自身，而在w[,2]中，┐p真。同理，主体1在可能世界w[,3]中知道北京天晴。　
结论4。在可能世界w[,1]，主体1知道主体2知道北京是否天晴，因为在可能世界w[,1]，主体1认为可能的两个世界是w[,1]和w[,2]，在这两个世界中，主体2都知道北京的天气（见结论2和结论3）。也就是说，虽然在可能世界w[,1]，主体1并不知道北京是否天晴，但是他知道主体2知道这一点。　
结论5。和结论4成为对比的是，在可能世界w[,1]，虽然主体2知道北京天晴（结论2），但是他不知道主体1不知道这一点。因为在可能世界w[,1]，主体2认为可能的两个世界是w[,1]和w[,3]，在w[,1]中，主体1不知道北京天晴（结论1），但在w[,3]中，主体1知道北京天晴（结论3）。　
以上结论，可以用一个逻辑表达式概括：　
附图　
前面已经指出，一个可能世界是一个事件集，相应的命题在其中真或假。在以上的讨论中，构成w[,1]和w[,3]的事件都是“北京天晴”，因此，似乎是两个相同的世界因而可以略去一个。但事实上却不能这样。因为一个可能世界的规定，不光基于构成它的事件，而且基于主体认为它是否可能。例如，在可能世界w[,1]，主体1认为可能世界w[,2]是可能的，但在可能世界w[,2]，他却不这么认为，这样，他在w[,1]不知道北京天晴，而在w[,3]则知道这一点。　
多主体系统中的共同知识　
在n主体系统中，如果所有的主体都知道所有的主体都知道…（重复≥n遍）a，则称这n个主体掌握了关于a的共同知识，或称a是这n个主体的共同知识。这一多主体认知系统中的重要概念，最早是由路易斯在讨论“协约”时提出的，他认为，某种东西要成为多方的“协约”，必须成为缔约各方的共同知识，也就是说，缔约各方不但都要知道协约的 内容 ，而且要知道各方都知道协约的内容，等等。　
为了对共同知识进行形式刻划，需要在语言k中增加新的算子e[,g]和c[,g]，满足：如果a是公式，则e[,g]、c[,g]都是公式。　
g表示主体集｛1,2,…,n｝。e[,g]a表示“g中每个主体都知道a”；c[,g]a表示“a是g中所有主体的共同知识”。在不引起歧义的情况下，作为下标的g可以省略，即e[,g]a和c[,g]a分别记为ea和ca。　
如果｛1,2,…,i｝是g的一个真子集（即i表示在｛1,2,…,i｝中每个主体都知道a。这种写法同样用于c。这样，附图就表示主体3知道p不是主体1和主体2的共同知识。　

在模型m中作如下定义：　
附图，当且仅当对任一附图，即在可能世界w[,i]中，ea真，当且仅当每个主体都知道a。　
令e[1]a表示ea，e[k+1]a表示ee[k]a，则　
附图，当且仅当附图，即在可能世界w[,i]中，ca真（a是所有主体的共同知识），当且仅当所有的主体都知道所有的主体都知道…（重复≥n遍）a。（注意，事实上，对于任意k>1和任意w[,i]∈w，如果附图，则附图附图。）　
对共同知识可以作出一种有意思的直观图示，为此，先来定义何为从一个可能世界到另一个可能世界可通达。(1)对任意可能世界w[,j1]和w[,j2]，如果存在主体i，w[,j1]r[,i]w[,j2]，则称从w[,j1]至w[,j2]可通达，并称这种通达为一步可通达；(2)对任意可能世界w[,j1]、w[,j2]和w[,j3]，如果从w[,j1]至w[,j2]可通达，并且从w[,j2]至w[,j3]可通达，可从w[,j1]至w[,j3]可通达。并且，如果从w[,j1]至w[,j2]是k步可通达，从w[,j2]至w[,j3]是1步可通达，则从w[,j1]至w[,j3]是k+1步可通达。　
虽然一般模态逻辑都把结构中的r关系称为可通达关系，但这里定义的可通达关系不同于r[,i]关系。第一，r[,i]关系是相对于某个主体i而言的，可通达关系不是相对于某个主体i而言的；第二，存在可通达关系的可能世界之间，不一定有r关系成立。例如，图1中从w[,2]至w[,3]可通达，但w[,2]r[,1]w[,3]和w[,2]r[,2]w[,3]都不成立。　
关于可通达关系，有两条重要推论。　
推论1。附图，当且仅当附图并且对所有w[,j]，如果从w[,i]至w[,j]k步可通达，则附图　
推论2。附图，当且仅当对所有w[,j]，如果从w[,i]至w[,j]可通达，则附图　
可以设想这样一个示图，其中，每个可能世界表示为一个点，任意两个一步可通达的可能世界之间用线段联接。以上两个结论的意义在于，判定a是否为可能世界w[,i]上的共同知识，只须看a是否在从w[,i]可通达的点（可能世界）上都真；判定e[k]a在w[,i]上是否为真，只须看a是否在从w[,i]k步可通达的点上都真。　
下面，运用以上的模型 方法 ，来 分析 一个很有意思的实例。　
“额上沾泥巴的孩子”　
一个教室中有10个孩子。其中，有7个孩子额上沾有泥巴。每个孩子都能看到别的孩子额上是否有泥巴，但无法看到自己的。这时老师走进教室，对孩子们说：“你们之中至少有一人额上有泥巴”。然后，他问：“谁知道自己额上有泥巴？知道的请举手。”他如是连续问了六遍，无人举手，当问到第七遍的时候，所有额上有泥巴的孩子都举起了手。假设所有的孩子都有理想的逻辑分析能力，那么，他们是如何思考并得出结论的？　
现在，尝试构造语义模型，对“额上沾泥巴的孩子”作形式分析。假设孩子有n个，要证明的是，沾泥巴的孩子的人数，正好等于他们都举手时老师提问的次数。　
自然 需要假设题目陈述的条件，例如，所有的孩子都足够聪明，对所有孩子都是共同知识。　
令1,2,…,n分别表示n个不同的孩子。(x[,1],…,x[,n])表示可能世界，其中任一x[,i],x[,i]=1，或者x[,i]=0。如果x[,i]=1，则表示孩子i额上有泥巴，否则表示没有。显然，对于n个孩子，这样的不同可能世界共2[n]个。例如，如果只有3个孩子，则可能世界｛1,0,1｝表示孩子1和孩子3有泥巴。假设这个可能世界就是真实世界。在这个世界中，在老师说话之前，孩子1能看到孩子2没有泥巴而孩子3有泥巴，他惟一不能确定的是自己额上是否有泥巴，因此，他认为(1,0,1)（即真实世界）和(0,0,1)都是可能的。也就是说，孩子i在可能世界(a[,1],…,a[,n])认为可能世界(b[,1],…,b[,n])是可能的，即(a[,1],…,a[,n])r[,i](b[,1],…,b[,n])，当且仅当除了a[,i]≠b[,i]以外，(a[,1],…,a[,n])和(b[,1],…,b[,n])完全相同。　
令φ=｛p[,1],…,p[,n],p｝，其中p[,i]表示“孩子i有泥巴”(i=1,…,n)，p表示“至少有一个孩子有泥巴”。附图当且仅当x[,i]=1。附图当且仅当存在x[,j],x[,j]=1。　
这样，完成了对模型m=(w,v,r[,1],…,r[,n])的定义。　
这一模型的优点之一是基于之上可以作出清晰直观的图示解析。　
令2[n]个点表示上述2[n]个不同的可能世界，并在任意两个一步可通达的点之间用标有数字i的线段联接（即如果孩子i在w[,i]认为w[,j]可能，则用标有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。附图，即在可能世界(1,0,1)中，所有的孩子都知道至少有一个孩子额上有泥巴。自(1,0,1)一步可通达的可能世界有(1,1,1)、(1,0,0)和(0,0,1)，在这四个可能世界中，p即“至少有一个孩子有泥巴”都真。　
结论4。附图，即在可能世界(1,0,1)中，并非所有的孩子都知道所有的孩子都知道至少有一个孩子额上有泥巴。因为存在自(1,0,1)两步可通达的可能世界(0,0,0)，其中p假，即没有孩子有泥巴。　
结论5。在可能世界(1,0,1)中，孩子1虽然认为(0,0,0)是不可能的，但认为孩子3可能在(0,0,1)中认为(0,0,0)是可能的。　
当老师说至少有一个孩子额上有泥巴后，这个命题立即成为所有孩子的共同知识，这样，任一孩子都不可能在任一可能世界中认为(0,0,0)是可能的，这样，通向(0,0,0)的可通达关系中断，(0,0,0)世界可移去，图2中的立方体因而坍塌成如下图所示：　
附图　
由图3可得：　
结论6。在可能世界(1,0,0)，主体1知道自己额上有泥巴。因为在(1,0,0)，孩子1认为可能的世界只有(1,0,0)（注意r关系的自返性。图2、3省略了图1中表示自返关系的圆弧线段），而在(1,0,0)中，孩子1额上有泥巴。同理，在可能世界(0,0,1)，主体3知道自己额上有泥巴，在可能世界(0,1,0)，主体2知道自己额上有泥巴。由结论6直接可得：　
结论7。如果事实上只有一个孩子有泥巴（即真实世界是(1,0,0)或(0,1,0)或(0,0,1)），那么，在老师第一遍提问后有泥巴的孩子就会举手。　
结论8。结论7是所有孩子的共同知识。不难验证，结论7在图3所有的可能世界中都真。例如，结论7在(1,0,1)中真，因为在该可能世界中，有两个孩子有泥巴，因此，作为条件句的结论7的前件假，结论7自身因而真。再如，由结论6，立即可得结论7在(1,0,0)中真。　
当老师的第一遍提问后无人举手时，由结论8，所有的孩子都立即知道(1,0,0)、(0,1,0)和(0,0,1)是不可能世界。这样，任一孩子都不可能在任一可能世界中认为这三个世界是可能的，这样，通向这三个世界的可通达关系中断，这三个世界可因此移去，图3继续坍塌而成下图所示：　
附图　
图4显示，当老师的第一遍提问后无人举手时，如果只有两个孩子有泥巴，他们立即明白自己有泥巴。　
一般地，在上述语义图中，如果老师的第k遍提问后无人举手，那么即可移去包含k个1的可能世界，并显示如果只有k+1个孩子有泥巴，那么，这些孩子都知道自己有泥巴。另一方面，如果老师不告诉大家至少有一个孩子有泥巴，老师的任何一次提问，都不会使上述语义图发生任何变化。　
博奕、商业谈判、战争谋略等都是典型的进行互知推理的多主体系统。这里的对手们，就是一个个沾有或不沾有泥巴的孩子。对多方体认知系统中互知推理的 研究 ，是近十年来国际上新 发展 起来的研究领域，其成果对于 经济 学、军事学、博奕论、人工智能和 计算 机 科学 的发展具有重要的价值，正引起密切的关注。

【 参考 文献 】　
①　ronald fagin etc:reasoning about knowledge, the mit press.1995．　
②　halpern,j.y.:"reasoning about only knowing with many agents",in al conference on ai(93)．　
③　aumann,r.j.:"agreeing to disagree",in annals of statistics．

本文链接：http://www.qk112.com/lwfw/wenxuelunwen/luojixue/25789.html