博弈分析逻辑（三）

其他著名的并行行动逻辑方法采用STIT逻辑（Horty & Belnap 1995；Broersen 2009）和时间逻辑，例如ATL（Alur、Henzinger & Kupferman 2002）或其认知变体ATEL（van der Hoek & Wooldridge 2003）。

2.9 博弈代数与动态计算逻辑

到目前为止，博弈被视为由代理整体推理的单一实体。这可能与现实生活中代理对博弈的概念化方式相矛盾。为了便于推理，博弈通常被分解成更容易单独处理的较小任务。例如，一位国际象棋棋手可能知道如何解决不同的残局。她不会对每一种可能的情况进行推理直至其结束，而是会在游戏中评估不同的选择，思考这些选择最有可能导致哪种残局。从这个角度来看，复杂的博弈是由一些简单的博弈构建而成的，而这些简单的博弈或许可以从单独的分析中获益。然后，博弈构成一个代数，其运算将简单的博弈构建成复杂的博弈。当博弈被视为交互式计算的场景时，这种思维方式会得到强化，而代数方法在交互式计算中也得到了广泛的应用（Bergstra、Ponse & Smolka 2001）。

以下是这种方法的一个例子。为简单起见，仅考虑两个玩家，A 和 E，后者先开始游戏。一个颇具影响力的博弈代数具有以下运算，参见 Parikh (1985)。G∪G′ 代理E可以在G和G′之间进行选择，即用一个具有两个结果G和G′的选择节点表示。

G;G′ 先玩G，然后玩G′。

(⋅)d 玩家A和E的角色互换。

?φ 测试博弈中某些性质φ是否成立。

例如，假设一位棋手正在进行中局推理。为简单起见，将可能的残局限制为GF1和GF2。然后，该棋手可以将中局概念化为一个博弈Gmid，其末端节点分别标记为命题p1或p2，分别描述接下来的残局。完整的剩余棋局树如下：

Gcomplete=Gmid;((?p1;GF1)∪(?p2;GF2))

该博弈代数的方程公理化可以在Goranko (2003)和Venema (2003)中找到。然而，类似于程序代数的命题动态逻辑，也存在一个适用于该游戏代数的动态博弈逻辑 (Parikh 1985)。它为每个博弈 G 添加一个模态 {G}φ，其中 {G}φ 表示在博弈 G 中，第一个玩家 E 拥有强制 φ 为真的策略。对于非确定博弈的情况，该语言将进一步扩展，包含单独的模态 {G,i}φ，每个玩家 i 对应一个。动态博弈逻辑以清晰的方式展示了复杂博弈的策略能力如何超越简单博弈的能力。这是通过诸如以下归约律来实现的：

{G;G′}φ↔{G}{G′}φ,{G∪G′}φ↔{G}φ∨{G′}φ

有关归约律的完整列表以及该动态博弈逻辑中的未解决问题，请参阅 Pauly (2001) 和 van Benthem (2014)。关于博弈代数的其他类型，包括并行组合的形式，参见 Abramsky (1997)。

应该说，不完全信息对这种博弈代数方法提出了挑战。例如，人们可能需要将一个较大的博弈分解成更小的子博弈，其中代理无需知道自己处于哪个子博弈中。不完全信息博弈代数已在布尔博弈的背景下得到研究（Harrenstein 等人，2001）。van Benthem、Bezhanishvili 和 Enqvist (2019b) 提出了一种基于权力的博弈代数，其运算对不完全信息进行编码，与 IF 逻辑 (Mann、Sandu 和 Sevenster，2011) 有一些相似之处。

2.10 专题

联盟与网络 目前为止，还没有关于玩家之间社会或结构关系的讨论：他们独立行动，并与所有其他玩家互动。然而，在许多博弈中，玩家群体可以组队共同追求目标，并可能与其他群体竞争。联盟是本文介绍的逻辑框架的自然延伸，但意义非凡，因为群体的战略能力可能超过所有成员的总和，参见Peleg (1997)、Van de Putte & Klein (2021, 2022) 以及关于博弈中联盟力量的条目。在其他社会现象研究中，参与者集合配备了额外的网络结构。因此，代理的结果或行为将取决于网络邻居的行为 (Baltag et al. 2019; Christoff 2016)。最后，网络博弈与社交网络中的信息流密切相关，正如刘、塞利格曼和吉拉德 (2014) 以及塞利格曼和汤普森 (2015) 从逻辑角度深入研究的那样。

追踪本节包含各种关于博弈的观点。这些观点在不变关系和匹配语言方面有所不同，从而提供了不同的焦点，例如结果、权力或博弈的详细时间演化。毫无疑问，还会有更多更深刻的观点不断涌现。这种多样性似乎令人难以抗拒，使得该领域显得相当分散。但逻辑的另一个作用在于，它不仅能丰富系统，还能连接它们。所涉及的语言和层级之间存在着各种逻辑翻译。通常，某个逻辑层级上的博弈推理，在翻译成另一个逻辑层级时可以精确地反映出来。此外，这些翻译通常可以跟踪信息更新操作下博弈的变化，这将在第3节中讨论。van Benthem (2016) 和 Cinà (2017) 以一般逻辑术语定义和研究了此类跟踪，Ye (2022) 则以范畴论术语对其进行了研究。

无限博弈 到目前为止，博弈的长度被默认为有限。这种假设对于许多现实生活场景来说并无害，但也存在明显的例外。一个突出的例子是安全博弈，其中一名博弈者，即守卫，必须确保系统永远不会离开某个状态，而对手则试图偏离该状态。许多用于有限博弈的技术工具也适用于无限博弈。然而，存在一些概念和逻辑上的不连续性。例如，由于无限博弈没有最后时刻，结果必须与博弈的完整历史联系起来，而不是像树叶一样。因此，对博弈进行推理不仅需要特定历史的时间模态，还需要涵盖所有开放未来历史的时间模态。因此，为了分析权力，需要强制模态的时间版本。即使经过这些修改，逻辑分析风格仍然适用。例如，众所周知，无限博弈不具备确定性（Jech 2003）。然而，适用于所有博弈的是“弱确定性”定律，该定律指出：如果i没有策略来强制一组满足φ的历史，那么她的对手j可以确保i在未来永远不会获得这样的φ策略。标准确定性与弱确定性之间的区别可以用以下两个公式来概括，它们完全符合本节的分析风格：{i}φ∨{j}¬φ（确定性）与{i}φ∨{j}G¬{i}φ（弱确定性），其中G是“在当前历史中总是在未来”的时间模态。在余代数中发现了无限博弈的更激进的用法（Abramsky 1997；Jacobs 2016），其中无限过程的模型只能从外部观察，而不能从基本元素有限地构建。

3. 玩家的本质

博弈形式可以看作是玩家可以操作的空间。然而，博弈本身并非完全由其博弈形式决定。相反，参与的玩家可能会引入与游戏玩法相关的额外特征。例如，玩家的观察能力可能会受到游戏结构或认知限制的限制。然而，最引人注目的附加特征是玩家拥有偏好。代理不仅观察世界并在其中行动。虽然这些仅仅描述了游戏的运动学，但代理还会评估当前状态和各种可能的未来。受偏好驱动，正是这些评估才是玩家选择背后的驱动力。因此，偏好在真正的游戏动态中发挥着重要的解释作用。

本节重点关注玩家的偏好和认知维度。这些因素对于理性概念至关重要，因为信息、行动和偏好往往相互交织。在博弈论中，人们通常在策略配置的均衡概念中寻求这两者之间的和谐。

3.1 偏好与均衡

博弈树和博弈矩阵指定了博弈者在不同时刻可用的行动。它们也表示所有可能的结果，这些结果要么作为矩阵中的单元，要么作为扩展博弈中的叶节点。然而，要研究博弈者在博弈中应该或将会做什么，还需要一个进一步的要素：博弈者的偏好。这些偏好不仅需要反映物质收益或结果状态的其他特征，还可能与博弈过程本身以及哪些行动会导致特定结果相关。此外，偏好可能包含不可简化的主观因素。即使在博弈中扮演相同的角色，不同的博弈者也可能对某些结果的相对可取性持有不同意见（Fehr & Schmidt 1999）。

在静态的、以结果为导向的博弈视角中，均衡是一个重点：所有博弈者都根据自己的偏好和对手的策略尽力而为的策略组合。另一种动态视角则侧重于此类均衡与个体博弈者根据其信念和愿望进行逐步局部推理之间的关系。第四节将探讨这一视角。

3.2 博弈的偏好逻辑

要推理偏好，首先必须明确主体的偏好适用于哪些方面。正统的解释认为偏好仅涵盖可能的结果（Osborne & Rubinstein 1994）。然而，逻辑文献中一种日益增长的趋势是，主体更关心一般命题的真值，而不是能够同时描述博弈的进展或结果。虽然这两种视角并不等同，但它们是兼容的。本节将对两者进行讨论。

在经典的图景中，博弈树上玩家 i 的偏好用偏好关系 ≺i 表示，该关系涵盖结果集。这种关系通常被认为是传递性和自反性的，但不必是完全的。

示例：带有偏好的博弈树。

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

图 8. ⓘ

与早期用于博弈形式的模态逻辑一样，相对简单的逻辑形式主义已经可以表达博弈中主体的相关方面。它提供了一种低复杂度的语言来陈述行动和信息的基本特征，而无需深入探讨底层的量化机制。更准确地说，带有偏好的博弈自然支持一种逻辑，其模态算子 [⪯i] 的解释如下：

[⪯i]φ

φ 在所有状态下至少与主体 i 的当前状态一样有效。

此类逻辑可以表达与博弈相关的各种属性。例如，他们可以说所有比当前状态更好的状态都是φ状态，这使得向φ状态迈进成为最大化效用的必要条件。他​​们也可以用公式表示所有最佳状态都是φ状态

⟨⪯i⟩[⪯i]φ

有关模态偏好逻辑的更多信息，请参阅Hansson (1990, 2001)、Girard (2008) 和 van der Torre (1997)。

模态偏好逻辑有进一步的扩展，与博弈有着天然的联系。例如，从更精细的角度来看，偏好可能源于各种主体想要实现的原因，例如标准或目标。这导致了结果状态之间的偏好关系与公式上的优先级顺序之间的二元性，描述了主体的目标。最后，动态账户追踪偏好在各种输入事件下如何变化。有关这两个问题的更多信息，请参阅Liu (2011)。

然而，无论如何理解，模态偏好逻辑都还不足以表达博弈论的一个基本概念。需要进一步扩展来处理最佳应对，即表示玩家当前的行动是其根据对手的行动所能做出的最佳选择。

最佳应对行动是博弈均衡的主要构成要素。形式上，纳什均衡是一种策略配置，为每个玩家设定一个独特的选择，当其他所有玩家都维持原有策略时，没有人能够通过单方面改变策略来提升策略。在扩展的模态偏好语言中，有几种方法可以定义此属性。一种可能是简单地引入一个新的原子bi，表示当前世界是玩家i根据对手的行动所能达到的最佳状态。在这种语言中，纳什均衡的特征是

⋀

i∈玩家

bi。

基于范·本瑟姆、吉拉德和罗伊（2009）的严格偏好模态，存在更明确的定义。然而，或许最简单的阐释方法是使用混合逻辑中的一种交叉模态（Areces and ten Cate 2007），将代理的偏好关系与其对对手行动的不确定性相结合，以表征最佳响应和纳什均衡（参见第2.6节）：

⋀

i∈玩家

[≺i∩≡i]⊥

纳什均衡的表达已成为战略博弈逻辑的基准（van der Hoek & Pauly 2007）。然而，还有其他一些需求，通常与分析博弈论的标准解概念相关。这些需求通常旨在寻找纳什均衡，或至少将策略范围缩小到符合某些理性要求的范围。这类方法的著名方法是针对扩展型博弈的逆向归纳法和针对战略型博弈的严格支配策略迭代移除法（Osborne & Rubinstein 1994）。由于它们提出了一些更深入的逻辑问题，因此我们将在下文进行讨论。

3.3 扩展型博弈中的逆向归纳法

以下是对逆向归纳法的高级描述。在扩展型博弈中，其目标是引入一种新的基于偏好的关系 besti，表示某个走子是博弈者在特定状态下能够做出的最佳选择。因此，besti 是博弈者 i 总体走子关系的一个子集，需要以合适的方式定义。

对于最终走子，标准决策理论认为，如果没有其他走子能够带来更好的结果，那么某个选择对主动博弈者而言是最佳选择。当将分析扩展到博弈的早期位置时，事情的关键取决于博弈者对对手未来行为的预期。根据博弈者的类型，存在几种可能的策略。认知博弈论中一个普遍的假设是普遍相信理性，即所有参与的玩家都是理性的，相信他们的对手是理性的，相信他们的对手相信对手是理性的，等等。根据这一假设，以下算法将最佳关系递归地扩展到非终端节点：

每当玩家i在状态s移动时，通过比较如果在此之后每个人都遵循各自的最佳关系会发生什么来评估可能的选择。如果在s状态下的某个可能移动，所有玩家重复执行此移动后的最佳结果至少与i在s状态下可以采取的所有其他移动（所有玩家重复执行此移动后的最佳结果）一样好，则该移动被包含在i的最佳关系中。

以下是这种自下而上的程序在实践中的运作方式。逆向归纳法示例。

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

图 9. ⓘ

此过程是经典博弈论中逆向归纳法的定性版本，它基于效用值而非偏好关系 (Leyton-Brown & Shoham 2008)。

逆向归纳法及其得出的最佳关系是偏好、信息和行动之间复杂纠缠的典型例子。van Benthem、van Otterloo 和 Roy (2006) 提出了一个支配这种关系的关键模态公理。此处的 best∗ 表示所有 besti 关系并集的传递闭包。

(turni∧⟨best⟩[best∗](end→p))→[movei]⟨best∗⟩(end∧⟨⪯i⟩p)

该等式描述了具有静态性质的动态过程的极限，它体现了一系列特征化定理，这些定理在博弈的逻辑分析中起着至关重要的作用。其他动态视角可以用类似的逻辑方式进行分析 (Liu 2011)。

3.4 迭代移除劣势策略

类似于逆向归纳法的迭代推理策略也存在于策略形式的博弈中。然而，这些程序并非定义一个新的一元移动谓词 best，而是通过移除次优行动来实现。如果存在其他可用的行动 b，无论对手采取何种行动，都能保证比 a 更好的结果，则行动 a 被标记为次优或劣势。在这种情况下，理性的博弈者应该将 a 从其可接受行动空间中删除，因为她永远不会选择该行动。

与逆向归纳法一样，优势推理也具有迭代性。假设玩家普遍相信理性，那么他们可以预期对手也会放弃考虑被优势行动。这样做会降低游戏的胜率，并可能导致后续的策略被支配，如下例所示。在从左到右的时间序列中，被丢弃的策略会显示为灰色。玩家的偏好用数值表示，1 表示最佳，4 表示最差。

c d

a 1,1 4,3

b 2,2 3,4

c d

a 1,1 4,3

b 2,2 3,4

c d

a 1,1 4,3

b 2,2 3,4

由于后续策略可能被支配，因此建议重复该过程，将支配策略的移除过程转化为一个迭代过程。当博弈是有限的时，该过程保证在有限时间内收敛。在二元偏好关系上迭代移除支配策略是经典博弈论中采用的版本的定性变体，其中假设基数效用值 (Leyton-Brown & Shoham 2008)。

一个密切相关的过程是弱支配策略的迭代移除，其中如果存在一个策略 b，它在对手的某些步法上优于 a，而在其余步法上至少同样出色，则删除某些步法 a。与其严格的对应方法不同，弱支配策略的迭代移除存在许多技术和概念上的复杂性，例如迭代移除的顺序依赖性 (Samuelson 1992; Pacuit & Roy 2011)。

3.5 目标

概括输赢的概念，可以为代理分配它们在游戏中追求的目标。将每个代理限制为一个目标保留了二元视角：目标是否达成。然而，目标允许额外的灵活性。除了像输赢博弈中的纯粹竞争之外，这些博弈还可以表达纯粹的协调博弈，即每个人都追求相同的目标，或者混合动机博弈，即不同玩家的目标部分重叠。目标函数的概念在布尔博弈的逻辑框架中尤为突出（Harrenstein，2004）。在该框架中，每个代理都被赋予对一些原子命题的控制权，允许其自由决定这些命题的真值。然后，目标被表述为基于所有玩家原子集合的命题公式。至关重要的是，玩家的目标公式因此可能涉及不受其控制的原子。在迭代扩展布尔博弈中，目标公式也可能指代时序逻辑中定义的博弈历史的属性（Gutierrez、Harrenstein & Wooldridge，2015）。

3.6 知识、信念和信息的局限性

玩家可能拥有或缺乏各种类型的博弈信息。首先，也是最重要的，玩家可能不确定他们面对的对手类型：他们的偏好、他们对博弈的推理以及他们对博弈如何展开的预期。其次，代理的不确定性可以延伸到博弈本身。当然，在同时移动博弈中，玩家不会知道对手的选择。此外，智能体可能对过去的举动和事件掌握的信息有限。这种不确定性可能源于博弈结构回避了某些观察结果，也可能源于未能正确记录过去的信息。在更极端的情况下，智能体甚至可能不确定对手可以采取哪些行动。

鉴于自身知识的各种局限性，玩家可能会利用信念来构建不确定性。随着玩家交流或观察博弈的进展，这些信念自然会发生变化。Stalnaker（1998）强调了信念在博弈逻辑分析中的重要性，他首次强调了信念修正在分析博弈解决方案推理中的作用。

3.6.1 关于走棋的不确定性

从某种意义上讲，即使是高度理想化的智能体，对于迄今为止发生的事情，也可能掌握有限的信息。在某些情况下，游戏结构可能会限制某些玩家对对手走棋的观察能力。在其他情况下，智能体可能会受到认知限制的影响，从而限制其对游戏的视角。或者，有时，智能体可能只是没有记录自己或他人的某些走棋。

在信息不完全的扩展博弈中，所有这些情况都用状态 m,m′ 之间的不可区分关系 −−−−A 来表示，表示智能体 A 无法区分自己处于 m 还是 m′。值得注意的是，这并不妨碍玩家在游戏后期了解自己处于 m 还是 m′。

示例：信息不完全的博弈。

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

图 10. ⓘ