博弈分析逻辑（二）

示例：双人战略形式博弈。

E

a b

A c O1 O2

d O3 O4

扩展形式和战略形式在侧重点上有所不同。前者强调博弈的连续时间结构，而后者则强调游戏前的策略选择。玩家可以根据当前目标自由地在两者之间切换。除了这两个形式之外，还有其他自然维度，例如强调玩家影响结果的能力（参见第 2.5 节）或玩家关于博弈的信息（参见第 3.6 节）。

备注：虽然到目前为止所有示例都涉及双人博弈，但无需进行这样的限制。扩展形式博弈和战略形式博弈都适用于任意数量的玩家，尽管偶尔可能会出现一些细微差别。下文将提到一些。此外，随着参与者数量的增加，潜在的联盟也会加入其中，而本文不会探讨这个话题。最后，某些自主性因素有时可能会通过后门介入。现实生活中的许多场景都包含任何参与者无法控制的外部偶然事件，例如掷骰子、天气状况或技术故障。通常可以通过将自然因素纳入逻辑分析中，从而将这些因素纳入其中。

2.2 博弈之间的不变性关系

由于对博弈的表示方式不同，因此自然会产生一个关于等价性的后续问题。给定两种博弈结构，它们何时表示同一个底层博弈？答案是，这很大程度上取决于参与者感兴趣的方面。示例：同一个游戏，还是不同？

本例包含两张博弈树图来说明示例。扩展描述（链接见图注）将对树进行详细描述。

图 4. ⓘ

考虑上述两种博弈形式。如果关注的是确切的移动顺序或玩家在过程中做出的选择，那么这些博弈是不同的。左侧博弈中，A 先行，而右侧博弈中，E 先行。在右侧博弈中，A 可能面临 p 和 q 之间的选择。这在左侧博弈中不会发生。

像本文这样关注确切的移动构成了对博弈的细粒度视角。还有其他视角。例如，当关注玩家实现特定结果的能力时，分析方法就会发生变化。在左侧博弈中，A 的策略（左手策略）确保博弈最终结果满足 p，而策略（右手策略）将可能的结果限制在满足 q∨r 的范围内。在第二种策略下，qorr 的进一步实现取决于玩家 E。同样，第二个玩家 E 在左侧博弈中有两种策略，一种（左手策略）确保结果满足 p∨q，另一种（右手策略）确保结果满足 p∨r。

对右侧博弈进行同样的计算，几乎会出现相同的玩家力量。更准确地说，A 的统一策略“左-左”和“右-右”分别产生 p 和 q∨r，与左侧博弈中的力量完全相同。剩下的两种策略“左-右”和“右-左”分别产生 p∨q 和 p∨r，这两者都只是 A 实现 p 的力量的削弱。因此，在玩家力量的层面上，上述两种博弈形式应该被视为相同。

正如本例所示，比较博弈有几种合理的方法。当深入研究博弈的内部结构时，互模拟的概念自然而然地成为一种候选（参见 Blackburn、de Rijke 和 Venema 2001）。互模拟 Z⊆G1×G2 将两个博弈形式 G1 和 G2 的状态关联起来，但需满足四个条件：状态 m 和 n 仅在以下情况下才可关联：(i) 同一个博弈者在 m 和 n 中移动；(ii) m 和 n 的基本局部属性相同；(iiia) 每当 G1 中存在一个可匹配的 a 类移动导致状态 m′ 时，G2 中也存在一个匹配的 a 类移动导致状态 n′，且 m′Zn′ 为 m′Zn′；反之亦然；(iiib) 每当 G2 中存在一个可匹配的 a 类移动导致状态 n′ 时，G1 中也存在一个可匹配的 a 类移动导致状态 m′，且 m′Zn′ 为 m′Zn′。

示例：博弈之间的互模拟。

这幅图包含两张博弈树图来说明示例。扩展描述（链接见图题）将对树进行详细描述。

图 5. ⓘ

这种特殊​​的互模拟概念并非唯一对博弈有意义的不变性。例如，从更粗粒度的角度来看，可能不会根据特定的动作类型来区分动作，而仅仅根据由哪个玩家执行这些动作来区分。相应的互模拟可以通过省略上述条件 (iiia) 和 (iiib) 中对特定动作类型的引用来定义。

进一步的互模拟概念对博弈的移动结构采取了更粗粒度的视角，例如，允许收缩同一玩家连续多次移动的区域。最后，丢弃所有关于玩家及其选择的信息，可以通过允许的移动序列来比较博弈。然而，这种纯粹的观察性概念，在计算中被称为迹等价性，在博弈的语境中可能不那么重要。另一种粗化方法侧重于玩家控制结果的能力，参见第 2.5 节以及 van Benthem、Bezhanishvili 和 Enqvist (2019a) 的文章。

虽然迄今为止讨论的大多数不变性概念都与扩展形式博弈有关，但类似的分析方法也适用于战略形式博弈。Van Benthem、Pacuit 和 Roy (2011) 定义了模态互模拟，将不同矩阵的结果状态连接起来，并将互模拟的来回条件应用于玩家的选择、自由和偏好的相关关系。

再次强调，本节仅关注博弈形式，忽略了任何与玩家相关的方面，例如结果之间的偏好。添加这些方面后，识别合适的不变性概念将变得更具挑战性，这将在下文第 3 节中讨论。

2.3 匹配不变性关系的语言

不变性关系的选择反映了在给定的博弈视角下，哪种结构被认为是相关的。阐明这些相关方面的核心工具是存在一种与某种不变性关系相匹配的逻辑语言。一般来说，不变性视角越细粒度，匹配语言就越能做出区分。

首先，如果对玩家通过移动可以带来的属性感兴趣，那么一个好的语言选择是基于模态⟨movei⟩φ，表示i的至少一个可用移动会导致满足φ的下一阶段。以下示例说明了该语言在给定扩展形式博弈中的工作方式。

模态博弈语言示例。

这是一个展示示例的博弈树图。扩展描述（链接见图标题）将对这棵树进行描述。

图6。ⓘ

模态公式 [moveA]⟨moveE⟩winE 在根节点 r 处为真，表示 E 有一个确保自己两步获胜的策略：无论 A 做什么，E 都能做出反应，最终到达一个自己获胜的节点。从更细粒度的角度来看，模态语言可以为特定的走法类型 a、b、… 添加表达式 [a],[b]…。在这种语言中，粗粒度模态函数 ⟨movei⟩φ 可以通过析取“⋁a 是 i⟨a⟩φ 的走法”来定义，这使得新语言成为旧语言的改进。

这样，模态逻辑的一般结果就适用于博弈论。例如，以带有当前时刻指标的博弈树等尖点模型为例。每当两个这样的尖点模型 G,m 和 G′,m′ 在上述第一个意义上互相似时，等价关系 G,m⊨φ 当且仅当 G′,m′⊨φ 对于所有公式 φ 都成立，且在一个足够丰富的模态语言中，每个着法标签都有模态[a]。因此，人们可以根据给定博弈视角的便利性，在句法、基于语言的视角和语义不变关系之间切换。对于力量视角或战略形式博弈的互模拟和模态语言，完全类似的观点也成立。

最后，模态语言并非独占。如果需要更细粒度的视角，更具表达力的一阶或高阶语言将成为描述博弈的有力竞争者。

2.4 扩展博弈的模态逻辑

博弈语言既可以定义博弈的属性，也可以对其进行推理。例如，正如上文所讨论的，两步扩展博弈中玩家的制胜策略就是一个例子。更一般地，对于任何有限的广泛博弈，对于每个代理 j，存在公式 φj，当且仅当 j 有一个获胜策略时，该公式才成立：

φj:=[movei]⟨movej⟩[movei]…winj

其中，公式中运算符的数量与树的深度相对应。

因此，运用此类公式进行推理的逻辑定律获得了博弈论的内容。例如，否定“一方玩家 A 拥有制胜策略”这一命题，可证明地等同于说另一方玩家 E 拥有制胜策略，至少在 A 获胜当且仅当 E 不获胜的情况下是如此：

¬φA =¬⟨moveA⟩[moveE]⟨moveE⟩…winA

↔[moveA]⟨moveE⟩[moveE]…¬winA

↔[moveA]⟨moveE⟩[moveE]…winE=φE

因此，模态形式的排中律对应于策梅洛定理，该定理阐明了有限博弈的确定性。

然而，用逻辑定律来描述博弈论性质存在局限性。由于模态算子的数量取决于博弈树的大小，因此描述某个玩家是否拥有制胜策略的公式在不同模型中有所不同。事实上，在基本模态语言中，没有统一的公式来表达玩家 i 可以在任意有限扩展形式博弈中获胜。这样的公式只能在模态 μ 演算 (Venema 2008) 中找到，其中“i 拥有获胜策略”的命题可以用不动点公式表示：

μp.(wini∨(turni∧⟨i⟩p)∨

⋀

j≠i

(turnj∧[j]p)

这里更普遍的观点是，博弈论均衡和解概念的递归性质自然地反映在具有不动点算子进行归纳和递归的逻辑中。

在这种情况下，模态逻辑的已知结果获得了新的意义。例如，在有限模型领域，在两个状态下具有相同的模态公式成立，等价于存在一个连接这两个状态的互模拟（参见 Blackburn、de Rijke 和 Venema 2001）。因此，只要两个有限博弈在其各自的根中满足相同的模态命题，它们在互模拟的意义上就是等价的。对于无限模型，这样的结果不那么直接。例如，互模拟与满足相同公式之间的完全等价性，仅对具有无限合取和析取的扩展模态语言成立。其他相关结果包括存在一些模态公式，这些公式定义了直到互模拟的给定尖点模型。这样的公式有时存在于基本模态语言中，有时存在于 μ 演算中，并且总是存在于无限模态语言中。应用于具体博弈 G，这些模态定义可以被视为 G 在相关不变性水平上所有属性的完整描述。

最后，模态逻辑拥有许多完整的证明系统，用于捕捉各类模型的有效后果 (Blackburn, de Rijke, & Venema 2001)。这些推理演算也适用于博弈论，它们可以捕捉特定博弈论论证的各个方面。证明论视角并非本文的重点，但会在适当的情况下提及一些相关线索。

2.5 权力视角的模态邻域逻辑

除了扩展形式博弈论之外，标准模态逻辑也适用于博弈结构的权力视角。有时，人们会完全忽略博弈论的内部机制，仅仅将其视为一个黑箱社会机制，玩家在一定程度上控制着结果。从这个角度来看，如果玩家采取一种策略，无论其他玩家如何操作，都能确保游戏最终结果为 X，那么她就可以强制游戏结果落入集合 X (van der Hoek & Pauly 2007)。类似地，如果玩家有能力强制游戏以 φ 状态结束，那么她就可以强制某个命题 φ 成立。代理能够强制执行的所有结果集合的集合通常被称为其强制执行能力。在古典博弈论中，这些强制执行能力有时被称为有效性函数 (Peleg 1997)，这些函数也经常用于研究玩家联盟（参见 Pauly 2001；Goranko、Jamroga & Turrini 2013；以及用于分析标准形式博弈中权力的逻辑条目）。

扩展博弈中权力的示例。

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

图 7. ⓘ

值得注意的是，强制执行能力在合取下不闭合。在上面的博弈中，代理 A 可以分别强制 p 和 q，但不能强制 p∧q。用模态逻辑的术语来说，强制力引申出邻域逻辑 (Pacuit 2017)，其中邻域函数列出了玩家在给定状态下可以强制执行的结果集合。然后，对强制力进行推理可以使用一种逻辑语言，其强制模态为 {i}，每个玩家的强制模态为：

{i}φ：代理 i 可以强制博弈结果满足φ。

这些模态可以用上述具有邻域函数的扩展博弈形式来解释。在语义方面，上述邻域模型的泛化支持一种广义的权力互模拟概念，参见 van Benthem、Pacuit 和 Roy (2011)。

权力的模态逻辑允许在全局描述层面对博弈进行推理。邻域模型的模态逻辑验证了标准模态单调性原理

{i}φ→{i}(φ∨ψ)，

正如强制模态的真值定义所示。然而，由于强制力在交集下不闭合，因此聚合律失效：

({i}φ∧{i}ψ)↛{i}(φ∧ψ)。

相反，该逻辑包含新的有效原理，这些原理与不同参与者的强制模态相关。例如，如果i可以强制φ为真，那么其他参与者j也不能强制φ为假。因此，

{i}φ→¬{j}¬φ

是强制力逻辑中“力一致性”的有效原理。对于有两个参与者i,j的博弈，该原理的逆则

¬{j}¬φ→{i}φ

表达了上一节中的确定性概念。该公式并非普遍有效，但它是一类特殊确定博弈的公理。

最后，还有一种更具代数性的关于力量的替代视角，它假设了前面提到的逻辑博弈的视角。2.2 节核心示例中描述的两个博弈可以看作是命题公式 p∧(q∨r) 和 (p∧q)∨(p∧r) 的评估博弈。

它们作为力量的等价性（如前所述）符合标准命题分布律。这种代数视角将在 2.9 节中再次讨论。

关于强制和力量的较新观点将上述定义中使用的结果集合 X 重新解释为指代两个参与者：一个参与者限制了结果的集合，而另一个参与者可以实现该集合内的所有结果。约束与自由之间的这种平衡显著影响了相应的博弈等价概念以及所使用的模态语言 (van Benthem, Bezhanishvili, & Enqvist 2019b)。

2.6 战略博弈的模态逻辑

从战略视角来看，玩家同时选择行动，而无需了解对手的行动选择。这需要更高层次的分析。除了各种可能的行动之外，一个充分的表征还必须追踪玩家对对手可能如何行动的不确定性。

就匹配逻辑语言而言，这表明了一种多模态方法，其中[≈i]涵盖i的可能选择，[≡i]表示她对对手的不确定性，参见van Benthem、Pacuit和Roy (2011)。此外，当考虑博弈而非博弈形式时，这幅图景需要补充第三个特征，即偏好模态[⪯i]，参见第三节。

战略形式的博弈可以自然地被视为选择和不确定性模态语言的模型，其中每个状态m由一个策略概况组成，即一个列出每个玩家行动选择的序列(m1,m2…)。为方便起见，我们引入了偏好模态：

G,m⊨[≈i]φ 给定对手的行动，φ 满足 i 的任何行动。

G,m⊨[≡i]φ 给定 i 的选择，φ 满足对手的任何行动。

G,m⊨[⪯i]φ φ 在所有状态下至少与当前状态一样好。

这种多模态语言可以表达关于策略型博弈的各种陈述，例如：

⟨≈i⟩⟨≡i⟩φ φ 是博弈的一个可能结果

[≈i][≡i]φ 博弈的所有结果都满足 φ

[⪯i]⟨⪯i⟩φ 玩家 i 的某些最优状态满足 φ

在双玩家的情况下，一个智能体的选择对应于另一个智能体的不确定性，反之亦然。这体现在以下原则的有效性上：

[≡i]φ↔[≈j]φ

更一般地说，矩阵博弈的逻辑不仅包含[≈i]和[≡i]的S5公理，还包含交换律

[≈i][≡i]φ↔[≡i][≈i]φ

表达了矩阵博弈的网格状结构。这种逻辑与STIT类型的行为逻辑（Herzig & Lorini 2010）有些相似。从技术上讲，模型中的网格结构允许对不可判定的计算问题进行编码（Blackburn、de Rijke & Venema 2001），这使得博弈矩阵的表达模态逻辑是否可判定成为一个悬而未决的问题。

从两人到多人的转变，在认知逻辑中通常是常规操作，但在矩阵博弈的逻辑中却可能非常微妙。[≈i]型可及性关系，被解释为除i坐标外轮廓的同一性，产生了一种类似于一阶逻辑三变量片段的乘积逻辑，已知该逻辑是不可判定的（Bezhanishvili 2006）。然而，如果仅在 i 坐标上存在恒等关系，即 [≡i]，则逻辑仍然是可判定的 (Venema 1998; Van De Putte, Tamminga & Duijf 2017; Lomuscio, van der Meyden & Ryan 2000)。

2.7 策略作为逻辑对象

在扩展博弈中，除了简单的移动之外，还有更深层次的结构。在博弈树中，玩家的策略指定了每一轮的行动，无论是否最终会到达这一轮。越来越多的研究探讨了此类策略及其底层格式，请参阅 van Benthem、Ghosh 和 Verbrugge (2015) 中关于各种用于推理策略的逻辑框架的概述。

从一个具体的角度来看，策略类似于一个指导代理如何在博弈树中导航的程序。因此，策略的自然逻辑使用程序的命题动态逻辑 (PDL) 语言，这种方法稍后会再次讨论。由于程序通常是非确定性的，因此此类逻辑允许策略推荐代理在每个回合应该采取的一个或多个行动。从这个角度来看，策略类似于可能保留部分的计划。

在程序格式中，策略始于基本动作，代表博弈树中的各个步骤。由此，可以使用包括顺序组合π1；π2（执行π1后执行π2）或选择π1∪iπ2（代理i在动作π1和π2之间进行选择）在内的操作来创建复杂的程序π。此外，用于检查φ是否成立的测试操作?φ使策略能够对状态属性或对手的过去动作做出反应。最后，为了描述策略沿博弈树的连续执行，有必要设置一个程序迭代操作π∗，表示π可以任意频繁地执行。

PDL语言为每个程序π都提供了模态运算符[π]，这些程序π可以通过基本动作和上述操作来定义。一个简单的此类策略建议玩家i在轮到自己时执行a。以下公式表明，该策略确保φ始终成立：

[((?turni;a)∪(?turnj;movej))∗]φ

此处给出的策略程序定义与计算机科学和博弈论中使用有限自动机定义策略密切相关（Osborne & Rubinstein 1994；Grädel, Thomas, & Wilke 2002；Ramanujam & Simon 2008）。

2.8 同时移动和不完全信息

在第2.1节的扩展形式博弈中，博弈者按顺序移动，并可以根据迄今为止发生的全部信息做出决策。另一个极端是策略形式的博弈，其中代理并行移动，或者，从策略选择的解释来看，在实际博弈过程中无法获取信息。在这两个极端之间还有很多其他场景。例如，对不合作者可选择惩罚的公共物品博弈（Andrighetto等人，2013），将部分或所有玩家同时行动的时刻与沿途的信息收集结合起来。这种并行行动可以在序贯博弈中通过限制博弈者在各个阶段可获得的信息来模拟。由此产生的不完全信息博弈将在第3节与其他不完全信息来源一起讨论。