博弈分析逻辑（五）

3.10 专题

道义推理 偏好与义务和许可密切相关。这在形式方面尤为明显，其中静态和动态变体的偏好逻辑（Hansson，1990；van Benthem、Grossi 和 Liu，2014）与道义逻辑有着明显的相似之处。此外，道义论和博弈论视角已经催生了许多富有成果的联系。一方面，道义概念可以被视为在给定主体信息和义务的情况下对最优行动的高级描述 (Kooi & Tamminga 2008; Anglberger, Gratzl & Roy 2015)。相反，主体的目标和意图可以从其义务中推导出来 (Klein & Marra 2020)。更普遍地说，博弈论解决程序可以丰富道义概念的解释 (Başkent, Loohuis and Parikh 2012; Horty 2018)。博弈论与道义推理之间的联系也可能引发新的议题，例如个体偏好与集体偏好之间的关系 (Duijf, Tamminga & Van De Putte 2021)。最后，在人工智能领域，道义视角出现在追踪分布式系统与其目标相关的行为时 (Ågotnes & Wooldridge 2010)。

数学基础：引入玩家引发了关于博弈等价性的新问题。当代理权很重要时，充分的等价概念不能止步于保留底层博弈形式的属性。相反，依赖于玩家的等价关系还需要保留玩家的信念、偏好或推理类型。引入这些额外的参数会使两个博弈更难等价，因为新的变异空间将会出现。另一方面，代理限制也可能创造出新的更简单的博弈等价关系，这些关系可以通过本文的工具进行研究。

4. 分析博弈

“博弈论”一词表明，所有感兴趣的事物都以博弈的形式体现，包括其行动和结果。本文重新整合了这一视角，并考虑了额外的结构。第三部分提供了第一个扩展，将玩家的性质作为一个独立的主题来处理。本节将重点关注第二个主题，即更广泛意义上的博弈。

逻辑和博弈文献中的许多主题都分为与博弈相关的三个阶段。某些活动可以在实际博弈之前进行。例如，评估对手或制定计划。然而，大多数相关的选择和决策都是在游戏过程中发生的——至少除非我们将玩家视为盲目遵循预设策略的自动机。最后，游戏结束后也会出现一些重要的活动。这些活动包括了解对手类型、识别关键错误或合理化已采取的行动。下文将分别介绍每个阶段的示例。

4.1 游戏解决方案和游戏前审议

当将游戏视为静态结构时，理性可以根据玩家信念、偏好和选择或意图之间的一致性来定义（Elster 1988）。然而，理性也描述了一种行为的特质，与玩家在博弈中的行为方式或他们利用的优势有关。将博弈解决程序解读为博弈前审议的风格时，可以具体化这两种视角之间的关系。接下来是对逆向归纳法（参见3.3节）的动态分析，它在概念上与表征定理不同，其静态属性（例如共同知识或共同信念）有所不同。在动态分析中，这些群体属性并非作为前提条件。相反，它们是通过审议逻辑产生的。

4.1.1 通过公开声明进行逆向归纳法

逆向归纳法算法通常在定量环境中呈现，其中每个结果都与所有玩家的效用值相关联。(Leyton-Brown and Shoham 2008)。然而，同样的算法也适用于定性环境，其中态度由结果之间的偏好关系表达。

逆向归纳法 逆向归纳法计算玩家的最优移动。更具体地说，在扩展形式博弈的每个选择节点上，一个或多个可用走法被标记为最优走法。对于每个玩家而言，这组最优走法通常构成一个通常博弈论意义上的策略，即一个函数，用于选择在每个选择节点采取的唯一行动。然而，也存在一些退化的情况，在这些情况下，逆向归纳法仅仅创建了一种关系策略，限制了可用的走法，同时仍然为玩家留下了一些选择。

驱动逆向归纳法算法的原则是，任何玩家都不应该选择被同一时刻其他可用走法所支配的走法。这里的支配性以递归的方式起作用。如果相应的棋手偏好从 a 步通过后向归纳法得出的每个最终结果，以及从 b 步通过后向归纳法得出的每个结果，则 a 步优于 b 步。

理性的公开宣告 从某种角度来看，后向归纳法可以理解为一种由思维协调的棋手执行的赛前审议过程。审议步骤是重复公开宣告 (!rat) 节点理性：

rat

没有棋手通过严格受支配的棋步到达当前节点

此处的主导性是指某一步棋完成后可获得结果之间的关系。一种解释是，如果 a 步之后剩余可获得的每个结果都优于 b 步之后可获得的任何结果，则 a 步优于 b 步。然而，这其中存在一个动态的转折：至关重要的是，在审议过程中，所考虑的博弈树，以及因此可获得的结果，都会发生变化。

公告更新的语义通过修剪模型来实现。 !φ 将模型 M 转换为子模型 M|φ，该子模型由 M 中所有满足 φ 的点组成，同时删除所有 ¬φ 节点。M|φ 上的关系是从 M 继承而来。至关重要的是，删除可能会改变公式的真值：宣布 !φ 后，M|φ 中的某些节点可能满足 ¬φ。具体而言，当 M 是博弈树中的点集时，随着连续宣布，可用历史记录集可能会不断缩小。因此，重复宣布 !rat 是合理的。在有限博弈中，这个过程总会达到一个极限，即一个最小的子博弈，其中没有任何一步会被其他一步所支配。

示例：通过迭代理性断言来解决博弈。

考虑以下博弈，该博弈已在 1.1 节中介绍过。!rat 的迭代声明会移除那些只能通过劣势走法才能到达的节点，前提是这些节点能够到达。此过程的轨迹如下：

此示例包含三个博弈树图。扩展描述（链接见图题）将对这棵树进行详细描述。

图 15. ⓘ

这里，逆向归纳法逐步显现。该过程的第一阶段排除了标记为 (2,2) 的叶子节点，因为这是 rat 失败的唯一点。第二阶段排除了 E 的选择节点，因为 rat 会失败。在最终的博弈树中，rat 始终成立。

更一般地，设 (!φ,M)# 为在反复声明 φ 且 φ 仍然成立的情况下，M 的极限（即第一个不动点）。在任何博弈树中，不动点 (!rat,M)# 始终使 rat 成立。其节点包含由逆向归纳法 (van Benthem 2014) 计算出的实际走法。

极限行为理性在极限情况下是“自我实现”的：如果玩家在足够长的时间内深思熟虑地致力于此，他们会剔除所有非理性的举动，更不用说所有与理性的共同信念不相容的举动。最终的结果是一个在每一点都体现理性的模型，一种理性的共同认知。然而，反复的声明也可能产生另一种类型的极限行为：自我反驳。一个典型的例子是经典的“泥泞儿童”谜题（Gierasimczuk & Szymanik 2011），在这个谜题中，反复传达无知最终会获得知识。同样，在博弈论中，也存在许多情况，其中（可信的）未来非理性声明可以使某些玩家比逆向归纳法（Leyton-Brown & Shoham 2008）的收益更高。Baltag 的研究研究了无限游戏中声明的极限行为，Bezhanishvili & Fernández-Duque (2022)，与经典拓扑中的康托导数相联系。

4.1.2 通过信念修正进行逆向归纳

迭代信念修正。赛前审议的另一种视角是用信念而非知识来表达的。这里的驱动力是信念中的理性：

rat∗

玩家从不根据他们对游戏后续进程的信念来选择任何被其他玩家主导的举动。

在这种情况下，博弈树本身在审议过程中保持不变：不会删除或排除任何历史。改变的可能是玩家分配给终端节点或（在无限博弈中）历史的相对似真性。

在似真性语义学（在第 3.6 节中简要介绍）中，代理相信在其似真性顺序中最大的所有认知可达世界中都成立的命题。相应的审议动态并非通过点删除进行，而是通过软更新修改代理的可信度排序。对于逆向归纳法，只需进行“彻底升级”⇑φ即可，将所有φ世界移至所有¬φ世界状态之上，同时保持这两个集合内的顺序 (Baltag & Smets 2008)。

该机制在博弈环境中的运作方式如下。首先，所有终端节点对所有玩家而言均等可信。由于升级是通过公开宣布进行的，因此所有玩家将始终保持相同的信念。在接下来的过程中，如果在代理的可信度排序中，y之后可到达的最可信终端节点都比与移动x兼容的每个最可信终端节点更优，则移动x在信念上受同一选择节点的移动y支配。现在执行以下类型的彻底升级：

⇑rat∗

如果y在信念上受x支配，使 x 之后的所有终端节点比 y 之后的终端节点更可信。

示例：逆向归纳法，软版本。

以下是上例中新程序的各个阶段，其中字母 x、y、z 代表终端节点或博弈历史：

本例包含三个博弈树图来说明该示例。扩展描述（链接见图题）将对这棵树进行详细描述。

图 16. ⓘ

在最左侧树的顶部节点中，对于玩家 A 来说，向右走并不比向左走更占主导地位。因此，rat∗ 仅影响 E 的回合，而使用 ⇑rat∗ 进行激进升级会使 (0,3) 比 (2,2) 更可信。在此变化之后，向右走已成为顶部节点的主导，因此发生了新的升级，使 A 的向左走成为最可信的。

使用 rat∗ 进行迭代升级始终稳定在一个固定的可信度顺序，该顺序对所有玩家都相同。将博弈的每个历史与其结束节点联系起来，可以进行逆向归纳法 (van Benthem & Gheerbrant 2010) 的信念分析。在有限树上，当所有参与者都采用其逆向归纳法策略时出现的历史，恰好对应于通过基于信念理性的迭代激进升级所生成的最合理的结束节点。Baltag、Smets 和 Zvesper (2009) 提出了一种逆向归纳法的动态认知表征，它以不同的方式融合了类似的思想。

稳定性不能被视为理所当然。对于其他断言φ，迭代升级⇑φ可能导致似真性顺序振荡或发散。然而，这种发散是有限的。虽然条件信念可能会出现循环，但每一个真实的迭代激进升级序列最终都会稳定所有命题信念 (Baltag & Smets 2009)。

不动点逻辑 从更技术的角度来看，逆向归纳策略可以定义为总移动关系中最大的子关系，该子关系在每个非终端节点至少有一个后继，同时满足行动和偏好之间的汇合性质：

CF(s)

∀x∀y((turni(x)∧xsy)→∀z(xmovez→∃u∃v(end(u)∧end(v)∧ys∗v∧zs∗u∧u≤iv)))

这一事实是证明逆向归纳在一阶不动点逻辑LFP(FFO)中可定义的基础 (van Benthem & Gheerbrant 2010)。该研究方向的结果将博弈解和博弈论均衡与计算不动点逻辑联系起来。在简单的设置中，例如前面提到的策梅洛定理，类似于μ演算的模态不动点逻辑就足够了。

4.1.3 严格支配策略的迭代移除

进一步的博弈解概念可以用迭代更新的逻辑来分析。具体来说，迭代更新不仅限于扩展型博弈，也能为战略型博弈提供洞见。一个典型的算法是严格支配策略的迭代移除 (SD∞)。在这种情况下，如果存在另一个策略能够相对于对手的任何行动产生严格更高的收益，则该策略被认为是支配策略。

示例：严格支配策略的迭代移除 (SD∞)。

考虑以下矩阵。照例，每对矩阵首先列出 A 的效用，然后列出 E 的效用。

E

a b c

A d 2, 3 2, 2 1, 1

e 0, 2 4, 1 1, 0

f 0, 1 1, 4 2, 0

首先移除右侧列，即 E 的行动 c，该行动由 a 或 b 中的任一个支配。随着 c 被移除，A 的行为 f 变为严格支配状态。移除 c 之后，E 的行为 b 变为严格支配状态，之后 A 的行为 e 也变为严格支配状态。在这个过程的最后，迭代移除只剩下 (d,a) 状态，即博弈中唯一的纳什均衡。一般来说，所有移除操作后得到的博弈矩阵保证包含原始博弈的所有纳什均衡，但也可能包含其他策略组合。

在这种情况下，形式动态装置包含适用于第二节矩阵博弈的断言。事实上，在矩阵博弈的逻辑中可以定义各种不同类型的理性。以下是一个双人博弈的例子，涉及“弱理性”的声明：

WR

每个博弈者认为，与她所有可用的备选行动相比，她当前的行动可能至少对她来说同样有利。

对于每个博弈者来说，这个声明是对她当前行动被强支配的否定。当然，这个属性可以用合适的认知行动模态来形式化地表达。然而，即使就目前情况而言，显然可以通过迭代的方式声明“弱理性”来修剪策略配置。每次宣布弱理性时，战略博弈都会发生变化，从而启动一个类似于早期逆向归纳法中理性的迭代宣布的逐步过程。正如之前所观察到的，由于模型只会变得越来越小，公开宣布的极限最终总会达到。对于弱理性的宣布，这些极限与 SD∞ 的结果完全匹配 (van Benthem 2007)。

类似的分析方式可以扩展到其他理性概念。例如，取 Bi 代表“玩家 i 的当前行动相对于对手的所有行动而言对她来说都是最优的”，则以下公式可以称为强理性 SR

⟨E⟩BE∧⟨A⟩BA

简而言之，该公式表示双方都有合理的希望取得好成绩。从这个意义上讲，强理性与博弈解决方案的可合理化程序（Pearce 1964；de Bruin 2005）相关，即如果在所有情况下都存在更好的响应，则放弃某些行动。强理性也驱动着博弈方法。

示例：通过迭代宣布强理性 (SR) 进行更新。

考虑上例的一个细微变化。以下是强理性 (SRω) 迭代声明的更新序列：

2, 3 2, 2 1, 1

0, 2 4, 1 1, 0

1, 1 3, 4 2, 0

2, 3 2, 2

0, 2 4, 1

1, 1 3, 4

2, 3 2, 2

0, 2 4, 1

2, 3

0, 2

2, 3

如前所述，每个方框都可以被视为一个认知博弈模型。同样，每一步声明都会增加玩家的知识，直到达到一个固定点，构成一个均衡点，每个玩家都尽可能多地了解信息。

强理性比弱理性要求更高。虽然 SR 蕴含 WR，但有些动作可能满足弱理性，但不满足强理性。这体现在当前示例和上一个示例之间的差异中。在当前矩阵中，弱理性声明在第一步消除行动 c 后停止。原因是，在第二个矩阵中，行玩家的底部行动并非严格受其他行动支配，因此在重新宣布弱理性后，该行仍然存在。然而，在任何情况下，行玩家的底部行动都不是对其自身最佳的。这与强理性相矛盾，因此该行将在下一次弱理性声明时被消除。更一般地说，由 (SR)∞ 产生的博弈矩阵是 (WR)∞ 产生的博弈矩阵的子矩阵。值得注意的是，这并不完全显而易见，因为两个更新序列可能会产生满足不同公式的不同认知模型。证明可见于范·本瑟姆 (van Benthem, 2014)。

与逆向归纳法类似，迭代声明与不动点逻辑之间存在联系。在强理性迭代声明后仍能幸存的策略组合可以在模态 μ 演算中定义 (Kozen, 1983; Venema, 2008)。如果将声明推广到任意公式，则需要所谓的紧缩不动点逻辑来研究极限行为 (Ebbinghaus & Flum, 1995; Dawar, Grädel & Kreutzer, 2004)。

其他博弈解概念也以类似的动态更新方式进行了分析。例如，Halpern 和 Pass (2012) 提出的迭代遗憾最小化方法已被用迭代声明 (Cui & Luo, 2013) 来描述。

值得注意的是，对于解概念，也存在更多演绎性的观点，其中连续推理承担了上述语义更新的角色。 de Bruin (2005) 的著作中，系统性地提出了一种基于证明论的视角，用于探讨博弈论推理的解法。最后，Apt (2005) 以计算逻辑的抽象重写形式，对强理性、弱理性以及其他博弈解概念进行了另类分析。

题外话：跨表征层次比较 不同的迭代声明程序会导致不同的博弈分析。此外，在比较不同框架中的各种程序时，可能会出现意想不到的结果。例如，以逆向归纳法为例。它的动态分析在扩展形式博弈中产生了新的“最佳行动”关系或似真性顺序。由此产生的策略概况可能与相关战略形式博弈的纳什均衡分析不同：

逆向归纳法与纳什均衡示例。

考虑以下博弈。E 对任何结果都没有偏好，但 A 有，这由效用值决定。

这是一个博弈树图，用于说明该示例。扩展描述（链接见图题）将对这棵树进行详细描述。

图 17. ⓘ

在之前的 BI 分析中，A 的任何一步都不会在信念上压倒另一步，因此没有一步会被排除。现在考虑每个玩家的两种可能的策略配置，并计算纳什均衡：

(左，右) 不是纳什均衡，因为 A 走右路会更好，但 (左，左) 是。

这说明了策略型博弈和扩展型博弈在逻辑视角上的差异。前者的原始元素，即策略，在后者的博弈树中是复杂的对象，无法仅在单个节点的层面上完全识别。经典博弈论中连接不同视角的相关观点催生了子博弈精炼纳什均衡的概念（Selten，1975）。

进一步的场景：以协商的方式制定博弈方案，使其成为一个内部的心理过程：通常情况下，对手不会提前坐下来讨论他们的博弈策略，而是会推理对手可能采取的行动和考虑。然而，上面介绍的协商技巧也适用于真实的对话场景。一个与博弈论相关的示例是“分歧”主题，它首次在认知环境中被引入，是由奥曼（Aumann）在1976年提出的开创性的“求同存异”结果。Dégremont 和 Roy（2012）运用动态逻辑技术，以 Geanakoplos 和 Polemarchakis（1982）的经典成果为基础，研究了这一主题。在这个框架下，任何主体不断陈述他们是否相信某个公式φ的对话，在极限模型中都会达成一致，此时更新不再有效。简而言之，代理不可能永远意见不合，至少在初始信息不同且共享一个合理的似然性顺序的情况下是如此。

4.2 游戏过程中的信息流、知识和信念

游戏是一个动态过程，玩家会反复获取关于其他玩家的新信息。信息收集的某些方面根植于游戏结构之中，例如观察动作，或者在不完美观察的情况下，从一个信息状态切换到另一个信息状态。其他更新可能是无关的，例如关于对手类型的信号。目前，还没有一个涵盖所有这些现象的通用逻辑理论。然而，有一些具有指导意义的案例。首先要讨论的主题是玩家的知识，其次是他们的信念。