来源：图文/中国科学院哲学研究所  编辑/王雨荍  

2023年5月5日下午2点，应中国科学院哲学研究所与中国科学院大学人文学院联合邀请，阿姆斯特丹大学、斯坦福大学和清华大学Johan van Benthem教授到访中国科学院哲学研究所，做了题为“Graph Games and Logical System Design（图博弈与逻辑系统设计）”的讲座。本次报告为2023年第8期“科学与人文”讲座。

Johan van Benthem教授

中国科学院哲学研究所负责人、中国科学院大学人文学院哲学系系主任郝刘祥教授出席并致欢迎辞，中国科学院哲学研究所李大柱博士主持了本次讲座。

郝刘祥教授

讲座主题是探索图博弈与逻辑系统间的关联，尤其关注玩家在博弈过程中的知识、推理模式、策略和互动以及博弈与逻辑系统的计算复杂度。van Benthem教授依次分析了旅行博弈（travel games）、蓄意破坏博弈（sabotage games）与捉迷藏博弈（hide and seek games）三个具体的博弈及与之匹配的逻辑系统，并从具体博弈所具有的特征概括出图博弈对更广泛的逻辑学议题的启发。

第一个例子：旅行博弈

 

博弈规则：两名玩家“旅行者”和“恶魔”在给定的图中从给定结点出发，轮流沿图的边移动；若无论恶魔如何行动，旅行者总能在下一步继续移动，则旅行者获胜。

从逻辑学的角度来看，旅行博弈可以完美地用标准模态逻辑刻画。van Benthem教授明确给出了点与点之间的可达性、旅行者针对恶魔行动的回应策略，以及在有限图上定义旅行者存在必胜策略的结点的模态语言，并指出可在模态μ-演算（modal mu-calculus）中给出更一般的定义。

标准模态逻辑具有许多良好的性质，包括可公理化性和可判定性，并能应用于计算机科学中的计算复杂度理论和哲学中的知识论、信息论，是分析图博弈策略、设计图博弈的有力工具。

 活动现场

第二个例子：蓄意破坏博弈

 

博弈规则：在图上给定出发点和目标区域；在每一轮行动中，先由恶魔删除图上的一条边，再由旅行者沿图中依然存在的边移动；若旅行者能移动至目标区域，则旅行者获胜。

有趣的是，van Benthem教授提出这一博弈模型的原始情境，是在交通网络逐渐瘫痪的情况下是否还能到达目的地这一现实问题。他指出，该博弈是一个需要在干扰（恶魔删除边的行为）下进行的图论中的搜索问题。相较于传统图论搜索的单人算法选择，蓄意破坏博弈是一个双人博弈。然而，策梅洛定理（Zermelo’s theorem）表明，所有有限的、完美信息的双人零和博弈中，其中一方有必胜策略。蓄意破坏博弈仍旧满足策梅洛定理的前提，旅行者的路径搜索是一个复杂度为PSPACE-complete的问题。

van Benthem教授指出，标准模态逻辑不足以单独刻画该博弈的决策树。从逻辑的角度看，随着图上的边被删除，逻辑公式也会相应的改变真值。关于蓄意破坏博弈的逻辑系统，van Benthem教授讲授了计算复杂度、表达力、公理化、零一律等方面的研究。

活动现场


第三个例子：捉迷藏博弈

 

博弈规则：两名玩家“旅行者”和“恶魔”在给定的图中从给定结点出发，轮流沿图的边移动；若无论恶魔如何行动，旅行者总能保证双方不在同一结点，则旅行者获胜。

van Benthem教授在这一部分着重介绍了李大柱、Sujata Ghosh、刘奋荣和涂雅欣的相关工作。他总结了捉迷藏的逻辑系统，指出尽管图形本身保持不变，但需要刻画点对的性质；而引入点对间的恒等关系后，甚至会使得该逻辑变得不可判定，从而让该逻辑能被用于刻画具有更高计算复杂度的问题。



展望：非完美信息与现实中的博弈

 

在玩家不再具有完美信息的前提下，策梅洛定理不再适用。这所带来的困难是显著的：玩家所采取的策略很可能成为短视的、仅仅是局部最优的策略。van Benthem教授以捉迷藏博弈的一些变形和推广，简要讨论了信息论、动态逻辑、时序逻辑、认知逻辑等可能为捉迷藏博弈新加的修正或约束，以及它们所能提供的有力工具。

除了逻辑学与图论相关研究领域以外，van Benthem教授还谈到了图博弈所涉及的更广阔的跨学科视角。例如，图博弈反映了参与者的推理模式和选择倾向，从而能够被用于孩童的心智发展研究；而除了图论搜索类型的问题，图博弈与逻辑的关联可能被进一步用于公式赋值、模型比较、模型构建、证明搜索、形式论证等方面的问题。

最后，van Benthem教授总结了图博弈与逻辑系统的研究方向，鼓励有兴趣的研究者在分析具体博弈算法问题、构建逻辑系统和设计具有独特逻辑系统的博弈等方向上，做出新的工作。

演讲结束后，van Benthem教授就讲座中的问题与在场师生进行了互动交流。讲座在出席师生的热烈掌声中圆满结束。

合影留念



【主讲人简介】

    Johan van Benthem 教授是阿姆斯特丹大学逻辑、语言与计算研究所创始主任，现为斯坦福大学Henry Waldgrave Stuart教授，清华大学金岳霖讲席教授，荷兰皇家科学院院士，欧洲科学院院士，国际哲学学院院士，美国艺术与科学院外籍院士，同时也是中国教育部海外名师。他是当今最著名的逻辑学家之一，有着广泛的国际影响力。个人主页：http://staff.fnwi.uva.nl/j.vanbenthem



责编：中国科学院哲学研究所

Powered by Froala Editor