博弈分析逻辑（八）

6.2 其他逻辑相关游戏

游戏逻辑和逻辑游戏之间的区别并不总是很明显。最近的文献中出现了许多设计与逻辑相关的游戏，但它们本身并非旨在分析逻辑概念。许多此类游戏都是基于图进行的，图是玩家可以执行不同动作的底层游戏板。图游戏在计算文献中被广泛用于分析逻辑和算法任务（Flum、Grädel 和 Wilke，2007）。然而，在本节中，我们仅重点介绍一种特殊的图游戏，因为它与逻辑有着丰富的联系，这暗示了一些不寻常的问题。

破坏游戏示例。

破坏游戏被提出用于分析不利环境下的算法任务。考虑以下欧洲城市之间的网络：

这是一张四座城市围绕第五座城市形成的环状图。扩展描述（图片标题中的链接）将描述这棵树。

图 24. ⓘ

在阿姆斯特丹和德国小镇萨尔布吕肯之间往返旅行都很容易。现在，让一个恶意的“恶魔”开始取消网络中的连接。在每个阶段，让“恶魔”移除一条连接，而旅行者随后可以沿着剩余的连接继续前进。这将一个单智能体的规划问题变成了一个双人破坏游戏。策梅洛式推理表明，从萨尔布吕肯出发的德国旅行者仍然拥有制胜策略，而在阿姆斯特丹，恶魔拥有对抗荷兰旅行者的制胜策略，即首先切断靠近萨尔布吕肯的一条线路。原始搜索问题的对称性被打破。

破坏游戏已被应用于各种场景，包括学习（Gierasimczuk、Kurzen 和 Velázquez-Quesada，2009）和通信网络（Aucher、van Benthem 和 Grossi，2018）。在有限图上，游戏结果已明确确定，确定谁拥有制胜策略的计算复杂度是 P 空间完全的（Löding 和 Rohde，2003）。

该制胜策略的存在性可以用一阶公式表示。更具体地说，获胜条件可以用双峰逻辑来定义，该逻辑将行进步骤的标准模态与单步箭头删除的新模态相结合，并在模型 M=(W,R,V) 中解释：

M,s⊨[−]φ 对于 R 中的每条边 (u,v)：(W,R−{(u,v)},V)⊨φ

该逻辑与破坏博弈非常吻合。最重要的是，它是图的一阶语言的自然片段。令人惊讶的是，该逻辑是不可判定的（Löding & Rohde 2003），使其成为任意模型上不可判定模态逻辑的最简单示例之一。

还有其他类似精神的图博弈，包括 Duchet 和 Meyniel (1993) 的毒药博弈，其中“恶魔”会毒害节点，而不是删除边。 Areces、Figueira 等人 (2011)；Areces、Fervari 和 Hoffmann (2015)；以及 Aucher、van Benthem 和 Grossi (2018) 的论文对用于变化图的模态逻辑和用于定义图博弈通用解的 μ 演算进行了广泛的研究。van Benthem 和 Liu (2019) 提出了一种图博弈的分类，其中包括复杂目标公式和不完美信息的影响。关于此类模型变化推理逻辑的一种观点是第 6.1 节中的语义博弈方法。在标准评估博弈中，初始模型不会改变。然而，模型变化的模态需要一个公式评估过程，其中评估模型会发生变化，例如，量词的证人不会被替换（这与一阶逻辑的标准语义学不同），或者移动会通过破坏可及性关系来改变事实。在其他情况下，类似的模态可以通过改变所研究现象的物理测量来证明其合理性 (Hintikka 2002; Renardel 2001; Ågotnes & Wáng 2017)，而另一个自然的例子是游戏玩法讨论中提到的用于信息更新的动态认知逻辑 (Baltag & Renne 2016)。这种广义的语义形式具有独立的逻辑意义。

例如知识博弈。

新的逻辑博弈也会在游戏玩法触发的信息、知识或信念的动态变化中自然产生（参见第 4 节）。具体来说，信息更新指的是目标相似或不同的参与者之间进行的对话游戏。这些游戏可能是合作性的，参与者的目标是汇集信息，从而将分散的知识转化为共同知识 (Meyer & van der Hoek 1995)。但它们也可能是竞争性的，例如，当参与者力争成为第一个知道某个相关命题是否成立的人时。两种模式的混合也会出现，例如，一些参与者的目标是传达一个外人不应该知道的事实 (van Ditmarsch 2003)。

一个具体的例子是Ågotnes和van Ditmarsch (2011)的“公告游戏”。参与者同时发言，并且只说一次，在追求目标的过程中，这些目标被指定为认知公式。言语表达通过公开声明建模，参与者的偏好是二元的。他们更喜欢目标公式成立的最终模型，而不是目标公式不成立的最终模型。

这些博弈是在不完全信息下进行的，因为参与者可能不知道其认知模型的真实状态。因此，相关策略需要统一。参与者必须在所有他们无法区分的状态下说同样的话。因此，一般来说，许多解决方案概念会产生混合的策略结果。事实上，可以证明，在纯策略中存在简单的声明博弈，没有任何唯一的均衡。然而，逻辑在其中发挥着重要的作用。假设所有目标陈述都是“通用的”，即仅通过应用合取、析取、知识算子和具有通用声明的动态模态，由文字构成。当从模型过渡到子模型时，这些公式的真实性得以保留。因此，认知不确定性的危害性降低，具有通用目标的知识博弈在纯策略中也存在均衡。近年来，知识博弈得到了进一步扩展，将问答作为问题变化和信息变化的独立行动纳入其中 (Ågotnes, van Benthem et al. 2012)。

布尔博弈示例。

介于博弈逻辑和逻辑博弈之间的第三个博弈设计示例是 Harrenstein 等人 (2001) 以及 Gutierrez、Harrenstein 和 Wooldridge (2015) 的布尔博弈，这些博弈已被多次提及。每个玩家被赋予对命题变量子集的控制权，并可以随意选择这些变量的真值。使用时间逻辑中指定的目标，这些博弈可以模拟大量相关的代理场景。目前，越来越多的研究探讨了布尔博弈的各个方面，包括其计算特性（单次和迭代）、博弈论性质和均衡（Gutierrez、Harrenstein & Wooldridge 2015），以及它们与社交网络博弈的联系（Seligman & Thompson 2015）。更多讨论请参见“联盟力量”条目。

6.3 专题

博弈逻辑与逻辑博弈之间的来回转换 本节主题提出了逻辑与博弈两种视角之间的循环。给定一个逻辑系统，可以为其设计逻辑博弈，然后可以使用某种合适的博弈逻辑对其进行研究。相反，给定一个博弈，可以引入一种描述它的逻辑，然后引入该逻辑的评估博弈，依此类推。有时，这些循环会达到不动点，例如，描述某个博弈公式的评估博弈与该博弈本身同构。但有时，这种循环仍在继续。相关讨论请参阅 Rebuschi (2006) 和 van Benthem (2014)。

不完美信息 逻辑博弈自然支持不完美信息，即博弈者无法完全了解对手的行为。认知变异会对相应的逻辑产生深远的影响。其中尤为突出的框架是 Hintikka 和 Sandu (1989) 的独立友好逻辑，另请参阅 Hintikka 和 Sandu (1997) 以及 Mann、Sandu 和 Sevenster (2011)。

论证博弈和图论博弈 另一个与逻辑相关的博弈分析分支是论证网络研究 (Dung 1995; Caminada & Gabbay 2009)，及其在人工智能和哲学中的应用（Grossi 2013；Shi 2018）

计算逻辑 本节内容与计算逻辑中的博弈论密切相关，博弈论用于分析语言的表达能力。相关成果及其与自动机理论的联系，请参阅 Grädel、Thomas 和 Wilke (2002) 以及 van Benthem (2014)。

博弈论与机制设计 博弈设计是博弈论领域的一个著名分支 (Rouse 2000)。同样，机制设计也是博弈论中的一个成熟课题 (Nisan & Ronen 2001；Osborne & Rubinstein 1994)。有关逻辑、博弈设计和规划之间的联系，请参阅 (Löwe、Pacuit & Witzel 2011；Löwe 2008)。

7. 讨论与未来方向

本条目概述了逻辑与博弈论交叉领域的当前研究成果。所调查的主题涵盖多个方面，包括当前广义上的博弈逻辑分析、逻辑与经典博弈论的联系、与概率和计算的联系，以及逻辑本身的博弈论内容。

所有这些，在与博弈的交汇处，或许产生了令人眼花缭乱的逻辑系统。然而，本文也展现了方法上的某种统一性，因为同一种（模态）逻辑最终适用于处理博弈结构和博弈玩法的不同方面。此外，如果我们稍微退一步，就能看到涵盖本文所调查具体系统的更广阔视角。

一个值得注意的现象是存在两种不同的逻辑分析风格。有些逻辑系统“聚焦”于活动或推理实践的特定方面，提供比标准数学或哲学分析中通常发现的更多细节。而另一些逻辑系统则相反，并“缩小”到在原始实践的更详细层面上可能不可见的一般模式。

本文中的大多数逻辑系统都属于细粒度的“放大”类型。即便如此，“缩小”类型的粗粒度逻辑也很有趣，因为它们可能突显出社会行为中超越博弈论和博弈论所关注细节的规律或一般模式。一个例子是当前人们对依赖性抽象概念的逻辑研究（Väänänen 2007；Baltag 2016）。各种形式的依赖性和独立性渗透到社会生活中。Baltag 和 van Benthem（2021）提出了一种符合这一视角的简单的函数依赖性和独立性模态基础逻辑，建议将扩展博弈中的策略分析为在参与者之间建立依赖关系的动态机制。陈、施和王（2022，其他互联网资源）随后将应用于战略博弈的框架与上文讨论的模态偏好逻辑相结合，以找到竞争博弈和合作博弈的共同逻辑结构。另一个在博弈中寻求普遍性的逻辑探索的例子是胡和金子（2012）对约翰森（1982）所著《社会互动的普遍假设》进行的证明论分析。

逻辑与博弈的交界领域仍处于萌芽状态。相应地，在逻辑方面存在明显的差距和需求，这在本条目的材料中有所体现。

特别是，博弈论推理的句法视角是一个基本主题。de Bruin（2005）的文章中可以找到博弈的证明论分析示例。更具体地说，Zvesper (2010) 分析了认知博弈论中的经典结果（参见 Tan & Werlang 1988；Aumann 1999），就信念和最优性的抽象模态而言，展示了模态μ演算中的一些简单证明规则如何能够捕捉认知博弈论中著名结果的精髓。迄今为止，逻辑的证明论方面一直被语义分析所掩盖，尽管这种情况正在缓慢改变（Artemov 2014；Kaneko 2002；Kaneko & Suzuki 2003）。基于模型的推理提供了关于博弈的抽象语义视角，有助于概念澄清和普遍规律的发现。但最终，或许是证明理论支配了语义学中使用的具体推理，并可能在确立博弈的普遍事实时指导论证的语境。

本文忽略了博弈与描述集理论之间丰富的接口（Woodin 2010；Kanamori 2003）。

需要再次强调的是，逻辑并非唯一阐明博弈的正式学科。定量概率以多种方式进入博弈论研究，无论是在古典博弈论还是演化博弈论中。逻辑与博弈的交汇点或许可以受益于逻辑与概率之间众多新旧联系（Leitgeb 2017；Lin & Kelly 2012；Harrison-Trainor, Holliday & Icard 2016）。

本文中另一个未被充分提及的联系是计算方面。游戏、玩法和玩家的研究与计算机科学和人工智能中的计算和主体性有着天然的联系（Grädel, Thomas & Wilke 2002；Abramsky 2008；Halpern 2013；Perea 2012；Brandenburger 2014）。本文所呈现内容的正确视角或许是逻辑、博弈和计算之间交汇点的三角关系。

至于更广泛的联系，我们并未充分阐述逻辑、游戏和哲学之间的所有联系，更多相关内容可参见 Stalnaker (1996, 1999)。语言学和心理学之间的联系也同样如此（Clark 2012）。在这种以语言为导向的联系中，还应提及 Bjorndahl、Halpern 和 Pass (2017) 等人关于用于描述游戏和推理的自然语言的研究，这些研究使得游戏分析更加依赖描述。

最后，本条目的主旨是理论性和基础性的。然而，逻辑和游戏也具有更实用的一面。逻辑在认知心理学和实验博弈论中发挥着作用，即使仅仅是为了识别与心智理论或战略推理相关的可检验假设（Ghosh、Meijering 和 Verbrugge 2014；Ghosh 和 Verbrugge 2018；Bicchieri 1993；Fagin、Halpern 等人 1995）。最后，一些关于逻辑与游戏交汇的研究，表明可以拓展到实际的室内游戏世界（van Ditmarsch & Kooi 2015；van Benthem & Liu 2019）。

总而言之，本文的主张较为保守。逻辑与游戏是自然的结合，如果深入探究，或许能发现一些有趣的东西。即便如此，过多的逻辑可能会引入过多的形式化机制，最终扼杀游戏的视角：逻辑系统是无限的机器，很容易淹没一个具体的、有趣的游戏。简而言之，这种联系必须谨慎处理。