公共知识与共有知识

1.经典问题

陶哲轩教授在多年前贴出过一道经典的蓝眼睛棕眼睛问题,后被广为流传为“红眼睛蓝眼睛问题”。

1.1 问题描述

一个岛上有100个人,其中5个人是红眼睛,95个人是蓝眼睛。每个人都无限聪明,且都遵守一系列规矩:不允许交流眼睛颜色,一旦知道自己眼睛颜色是红色则当晚必须自杀。同时岛上没有任何其他方式可以获悉自己眼睛的颜色,如反射等等。

有一天岛上来了一个游客,在离开的前一天,岛上所有人一起办了一场聚会。聚会期间游客不小心说了一句“没想到能在这里遇见红色眼镜的人”,说完后所有人都安静了下来。游客也很慌张,第二天匆匆离开。

离开后游客心想“岛上有红眼睛的人”这件事他们每个人早就知道,不应该有任何影响才对,于是放下了心。

没想到仅过了5天,岛上的5个红眼睛都自杀了。为什么?

1.2 传统分析

假设岛上只有一个红眼睛的人,因目光所及无红眼睛的其他人,显然会自知红眼且在第一晚自杀。

假设岛上有两个红眼睛的人,任意一人能且仅能看见一个红眼睛的人。如果假设自己不是红眼睛,则根据刚才的分析,应知对方会在第一夜自杀,如果没有,则知自己是红眼睛,且在第二晚自杀。

假设岛上有三个红眼睛的人,用类似上方所述逻辑,如果第二晚没有发现人自杀,则会在第三晚自杀。

以此类推,于是,当岛上有五个红眼睛的人,则会一起在第五个晚上自杀。

1.3 对传统分析的疑惑

主要两方面疑惑

  1. 在红眼人数足够多的情况下,归纳的前提,即“只能看到一两个红眼睛的人”明显不再成立,那演绎还能有效吗?
  2. 传说此问题和共有知识,即“任何人知道任何人知道任何人知道…岛上有红眼睛”的有关系,但从传统分析表面看起来只需要使大家同步一起天数应该也能让红颜睛自杀吧?似乎没有共有知识什么事。

2.解决疑惑

我们尝试用最笨的推导方式来重新审视这个问题(“排出所有可能性,留下来的就是事实”的硬推导)

2.1 笨办法考虑一名红眼睛

假设岛上有一个红眼睛的人,我们将其编号为1,且记为

{1R}

对1号而言,他认为有两种可能,即自己是红眼或自己是蓝眼,记作

1think{1R}
1think{1B}

一开始,1号没有任何方式获知哪行是真的或哪种是假的。但一旦得知游客告知的知识,即红色的数量大于 0,即 N(R)>0 则可以很容易地发现和 1think{1B} 有冲突,于是可以排出它,仅留下一行

1think{1R}

即剩下唯一可能性:“自己是红眼”,因而在获知 N(R)>1 的当晚自杀。

由此可见,笨办法确实很笨。将一句话的问题延展出了这么多废话。

且这里没有考虑蓝眼睛的影响,不过我们可以稍作尝试后发现蓝眼睛的人在这里不会提供有用的信息或知识影响,和岛上的一颗石头无异。

综上,仅对一个红眼睛,我们可以发现,游客的知识在此时是直接产生了作用。

2.2 笨办法考虑两名红眼睛

假设岛上有两个红眼睛与一个蓝眼睛(看看蓝眼睛是如何不产生作用的),即

{1R,2R,3B}

对于1号而言,他可以看见别人的眼睛颜色,可以猜测自己的眼睛颜色,还可以猜测在别人眼中的自己的眼睛颜色,还可以猜测别人猜测的别人的眼睛颜色…

以至于任何一种可能性中都可以包含无穷元素,以及可以有无穷种可能性。那怎么列出来呢?

嗯,用省略号即可

1think{1R,2R,3B,....}
1think{1B,2R,3B,....}

但此时,当他得知 N(R)>0 ,这是符合每一种既有可能性的,于是没有办法排掉任一,似乎陷入了死胡同。不急,我们尝试把省略号拓展出来一部分,使显性列出 1 对自己颜色猜测和 1猜测2 对2自己颜色的猜测的所有组合

1think{1R,2R,3B,2think{1R,2R,3B,...},...}//1认为自己是红色且认为2认为2自己是红色
1think{1R,2R,3B,2think{1R,2B,3B,...},...}//1认为自己是红色且认为2认为2自己是蓝色
1think{1B,2R,3B,2think{1B,2R,3B,...},...}//1认为自己是蓝色且认为2认为2自己是红色
1think{1B,2R,3B,2think{1B,2B,3B,...},...}//1认为自己是蓝色且认为2认为2自己是红色

这里因1无限聪明,所以排除了类似“1自己是蓝色的情况下,2认为1是红色”这种不可能存在的情况

  • 2能看见1的眼睛,所以2的想法中1的眼睛颜色就是事实眼睛颜色

此时“公共场合公开宣告”的价值才提体现出来。公开宣告提供了不仅仅为每个人提供了 Xthink{N(R)>0} 这样的旧知识,还提供了 Xthink{Xthink{N(R)>0}} 这样的新知识。于是1可以排除

1think{1B,2R,3B,2think{1B,2B,3B,...},...}//1认为自己是蓝色且认为2认为2自己是红色

这行,剩下

1think{1R,2R,3B,2think{1R,2R,3B,...},...}//1认为自己是红色且认为2认为2自己是红色
1think{1R,2R,3B,2think{1R,2B,3B,...},...}//1认为自己是红色且认为2认为2自己是蓝色
1think{1B,2R,3B,2think{1B,2R,3B,...},...}//1认为自己是蓝色且认为2认为2自己是红色

之后 1 可以先假设自己是蓝色,即第三行

1think{1B,2R,3B,2think{1B,2R,3B,...},...}//1认为自己是蓝色且认为2认为2自己是红色

可推知这样的假设下,2一定知道2自己是红色,且应在当晚自杀。

如果第二天发现2没有自杀,则知自己不是蓝色,于是应在第二晚自杀。

但显然2不会在第一夜自杀(正如1不会在第一夜自杀)

综上,两个红眼在第二晚自杀需要两组重要信息

  1. 任何人知道任何人知道 有红眼睛的人
  2. 任何人知道 第一晚没有人自杀

由于对这两个信息的依赖,致使 游客的公开场合的话 等待一天 第二天大家公开见面 这三件事非常必要。

2.3 笨办法考虑三名红眼睛

这里开始简略一些说明

{1R,2R,3R,4B,5B,...}//3个红眼睛与不定数量的蓝眼睛

1号心中的各种可能性,显性列出1对自己的颜色想法,和1心中2对2自己的颜色想法,和1心中的2心中的3对自己的颜色想法组合(8行)

1think{1R,2R,3R,4B,2think{1R,2R,3R,3think{1R,2R,3R}...},...}//注意1认为的2认为的3认为的1或2的颜色需要与1外部括号一致
1think{1R,2R,3R,4B,2think{1R,2R,3R,3think{1R,2R,3B}...},...}

1think{1R,2R,3R,4B,2think{1R,2B,3R,3think{1R,2B,3R}...},...}
1think{1R,2R,3R,4B,2think{1R,2B,3R,3think{1R,2B,3B}...},...}

1think{1B,2R,3R,4B,2think{1B,2R,3R,3think{1B,2R,3R}...},...}
1think{1B,2R,3R,4B,2think{1B,2R,3R,3think{1B,2R,3B}...},...}

1think{1B,2R,3R,4B,2think{1B,2B,3R,3think{1B,2B,3R}...},...}
1think{1B,2R,3R,4B,2think{1B,2B,3R,3think{1B,2B,3B}...},...}

当1得知Xthink{Xthink{Xthink{N(R)>0}}} 即1知道任一人知道任一人知道 N(R)>0 后即可排除

1think{1B,2R,3R,4B,2think{1B,2B,3R,3think{1B,2B,3B}...},...}

此时1假设自己是蓝色,且假设2在假设2自己是蓝色,则应仅剩下

1think{1B,2R,3R,4B,2think{1B,2B,3R,3think{1B,2B,3R}...},...}

一行,即此番嵌套假设下,1认为2一定认为3一定认为3自己是红色,且应在第一夜自杀。

但显然3并不会在第一夜自杀(正如1不会在第一夜自杀)

于是1知道,如果继续坚持假设自己是蓝色的假设,即只剩下

1think{1B,2R,3R,4B,2think{1B,2R,3R,3think{1B,2R,3R}...},...}
1think{1B,2R,3R,4B,2think{1B,2R,3R,3think{1B,2R,3B}...},...}//必存在
1think{1B,2R,3R,4B,2think{1B,2B,3R,3think{1B,2B,3R}...},...}

一共3行可能性。由于1知道2知道3第一天没有自杀,于是1知道2知道3一定在第一天认为自己有蓝色的可能性(只有第二行,因如果没有蓝色的可能性3必自杀),这行可对应着1知道2知道3知道2是红色,而3知道的就是看到的,即假设满足能推出2知道2自己是红色。

所以如果1自己蓝色假设要成立,1推到后能知道2会在第二夜自杀

但显然2也不会在第二夜自杀(正如1不会在第二夜自杀)

所以1只能推翻自己是蓝色的假设,并在第三夜去自杀。

综上,三个红眼在第三晚自杀需要几组关键信息

  1. 任何人知道任何人知道任何人知道 有红眼睛
  2. 任何人知道任何人知道 第一晚没人自杀
  3. 任何人知道 第二晚没人自杀

由此可知 游客的话、第二天二级确认生死(任何人确认任何人知道任何人的生死)、第三天相互确认生死(任何人知道任何人的生死)

2.3 笨办法考虑多名红眼睛

不再详细说明过程,基于前面几次分析进一步推论就知道通用的本办法分析方式:

  • 红眼睛可以递归着用“假设是蓝眼睛”进行反证
  • 每个白天多级确认没人死亡,而一步步减少递归假设的深度,且最终在打破自己是蓝眼睛的假设后自杀

并且可以发现,N 个红眼睛在第 N 晚自杀需要的信息有

  • N 阶知识的 有红眼睛
  • N-1 阶知识的 第一晚没人自杀
  • N-2 阶知识的 第二晚没人自杀
  • 1 阶级知识的 第 N-1 晚没人自杀

由此顺便可以知道如果岛民不想自杀,一种解决方案是约定未来各自宅在家里再也别相互见面,或错峰见面别聚会(使有谁死亡这件事不构成足够的高阶知识),或干脆云游四方。

3.共有知识

通常,把 (任何人知道)^N 的一个知识叫做 N 阶知识。

逻辑学上,将包含了1至无穷阶知识 的一个知识 叫做共有知识。

容易发觉共有知识的建立事实上非常难,要求充分的信任与沟通。

共有知识(多数时候有限阶知识就足够了)的建立在红蓝眼睛的奇葩岛上有着致命后果,但在很多合作领域有着重要的价值。

3.1 将军通讯问题

两将军需要合作,协商一起进攻,如果单方进攻则一定会失败。通讯仅依赖通讯兵,但通讯兵有可能路上被抓。

而理论上两将军应需要“对方知道自己知道对方知道自己知道…要在XX时间进攻”这样一个共有知识,才能保证一定一齐进攻。

因此在这样的环境下,不可能严格建立共有知识。

对于类似情形,两将军可以通过事先的协商,用类似三次握手规则,保证能在有限时间内确定一个时间点进攻。虽然有概率最终依旧只有一方进攻,但也许比无限通讯无法进攻好。

3.2 打破囚徒困境

打破双人囚徒困境的一种方式是多次合作博弈,且都公告要以牙还牙,可以迫使大家合作。

但要严格地达成合作,其实也需要依赖“下次还有合作”和“对方会以牙还牙”都是公共知识,否则还是会出现一些背叛(作为可能的优势策略)。

  • 如猜测对方可能老好人,则自己优势策略显然是一直背叛
  • 如猜测对方不知道下次有合作,则认为对方一定会背叛,所以应背叛

3.3 情侣或朋友沟通问题

容易发现身边很多的人际矛盾并非真正的利益冲突,而是猜忌。如

  • 他这样做是不是不爱我了
  • 他这样做是不是为了不还钱
  • 他是不是不把我当朋友了

而由猜忌导致行为表现异常,进一步引起对方猜忌。

解决起来其实很简单,就是建立共有知识(需要确认自己不坏,且相信对方对自己不坏)。

但建立共有知识的过程是很难的,需要无限充分交流,以至于很多时候我们需要类似将军问题那样靠规矩终止无限循环的可能性。

不过由此可看出亲密交流中有几大忌

  • 冷战(拒绝交流,仅靠猜)
  • 不信任(无效交流)
  • 恶意欺骗(摧毁信任)

而建立良好关系的良药,也由此很明确:

  • 坦诚且主动交流
  • 信任

4. 参考资料

知乎问题

陶哲轩博客

留下评论