人工基础智能及逻辑 5

第10章博弈逻辑10.1从囚徒博弈到博弈的一般结构10.2逻辑中的博弈语义10.3博弈结构与博弈逻辑10.3.1扩展式博弈10.3.2博弈等价10.3.3获胜策略、确定性与逆向归纳法10.3.4从算法到博弈：以蓄意破坏博弈为例10.4认知博弈及其动态化10.4.1偏好、最佳回应与理性10.4.2知识、信念与不完美信息10.5结语博弈逻辑概述什么是博弈逻辑博弈逻辑（GameLogic）作为逻辑学与博弈论的交叉学科，通过模态逻辑、动态逻辑等形式系统，揭示玩家在博弈中如何基于知识、信念与偏好进行推理和决策。核心特征将策略行为、信息流动、角色互动等动态博弈特征转化为可计算的逻辑结构加深了对玩家理性行为的逻辑刻画推动了逻辑体系本身的发展，使逻辑成为处理互动与推理过程的动态框架博弈逻辑的研究方法方法论视角"显微镜式"的精细分析通过模态逻辑刻画扩展式博弈树"望远镜式"的宏观把握在策略博弈中对理性行为的建构主要分析工具逆向归纳法知识动态演算模态逻辑框架当前研究范式复杂互动场景拓展向更加复杂的互动场景拓展不完美信息博弈不完美信息博弈中的认知问题动态变化刻画刻画认知博弈中知识与信念的动态变化博弈逻辑的双向视角从逻辑到博弈将传统的逻辑问题转化为博弈中的策略选择问题论辩博弈赋值博弈抽象的逻辑有效性具象化为玩家的获胜策略从博弈到逻辑将博弈中的基本运算抽象为逻辑算子行动选择角色转换序列复合推动动态博弈逻辑与认知博弈逻辑的发展本章学习目标主要内容基本博弈示例介绍基本的博弈示例与逻辑博弈逻辑转化博弈展示如何将传统逻辑问题转化为博弈问题博弈一般性定义深入讨论博弈的一般性定义博弈结构与逻辑探讨博弈结构及其相关联的逻辑理论框架勾勒勾勒博弈论与逻辑学交叉研究的理论框架10.1从囚徒博弈到博弈的一般结构引言囚徒困境（Prisoner'sDilemma）是博弈论中的经典示例，常用于展示非合作博弈中理性行为与社会最优之间的冲突。囚徒困境的场景设定博弈背景两名嫌疑犯（A和B）被警察分别关押，他们面临着以下选择：双方合作：如果两人都选择合作（保持沉默），他们将因为轻微罪行各自被判1年监禁一方背叛：如果一方选择背叛（出卖对方），而另一方选择合作，背叛方将被释放，而合作方将被判10年监禁双方背叛：如果两人都选择背叛（互相出卖对方），他们都将各自服5年监禁囚徒困境的收益矩阵矩阵描述B合作B背叛A合作(-1,-1)(-10,0)A背叛(0,-10)(-5,-5)各种情况分析双方合作（A合作，B合作）两人都选择合作，每人获得最轻的惩罚（-1），这是社会最优的结果一方背叛背叛方获得最优结果（0），而合作方遭受重罚（-10）双方背叛（A背叛，B背叛）两人都选择背叛，结果较为中等（-5），尽管比"合作-背叛"时的惩罚要轻，但依然是次优结果囚徒困境的均衡分析理性困境尽管双方合作是社会最优选择，但在理性自利的驱动下，背叛始终是占优策略。纳什均衡每个玩家在追求个人最优时选择背叛，最终陷入"背叛-背叛"的纳什均衡状态，这导致比合作时的结果更糟。核心机制"背叛-背叛"的均衡结果，揭示了非合作博弈的核心机制。这一结果并非偶然，而是源于博弈结构的系统性特征。背叛始终是占优策略，即使双方合作才是社会最优选择。博弈的基本构成要素博弈的形式化定义$$G=⟨N,(S_i)_{i∈N},(u_i)_{i∈N},τ⟩$$各要素说明$$N$$：玩家集合定义了玩家的类型，在囚徒困境中，$$N={A,B}$$$$S_i$$：策略空间玩家$$i$$的策略空间，提供了玩家可行的行动，在囚徒困境中，$$S_i={合作,背叛}$$$$u_i$$：效用函数玩家$$i$$的效用函数，量化了玩家对于不同效用的偏好关系，在囚徒困境中，就个人而言，背叛优于合作$$τ$$：信息结构包括知识（如完美信息）与信念（对他人行为的预期）等，在囚徒困境中，每个玩家不仅知道自己的收益矩阵，也相信对方拥有相同的认知从静态结构到动态决策认知决策机制上述四个基本要素构成了博弈的静态框架，而要理解均衡结果的形成过程，需要考查玩家在既定框架下的认知决策机制。影响策略选择的路径当玩家类型$$Γ$$（如合作倾向或竞争倾向）与信息结构$$τ$$相结合时，会通过以下路径影响最终策略选择：信息结构$$τ$$决定知识的分布，如玩家明确知道背叛是占优策略策略空间$$S_i$$通过信念映射为对他人行为的预期，如预期对方会选择背叛效用函数$$u_i$$转化为偏好关系，使得短期个人利益优先于集体利益静态框架→动态决策信息结构$$τ$$决定知识分布策略空间$$S_i$$映射行为预期效用函数$$u_i$$转化偏好关系"理性"行为的形成机制图10-1"理性"行为关键符号说明$$κ_iφ$$玩家i知道命题φ$$p_iφ$$玩家i偏好命题φ$$Γ$$玩家类型，如合作型/竞争型等$$u_j∼_iu_k$$玩家i认为效用uj与效用uk相当$$σ_i^*∈BR_i(σ_-i)$$$$σ_i^*$$是玩家i对其他玩家联合策略的最佳回应博弈结构的认知依赖核心发现从图10-1可以看出，囚徒困境的博弈结构不仅依赖玩家的理性行为，还受限于他们的认知过程，而这些认知要素共同推动了"背叛"成为占优策略。动态演化单次博弈这一机制表现为静态均衡重复博弈当博弈重复进行时，系统将演化为动态交互过程，此时策略选择会随博弈轮次产生适应性变化理论意义这一分析为我们提供了从囚徒困境过渡到博弈的一般结构的关键视角。10.2逻辑中的博弈语义博弈语义的理论价值博弈语义作为一种重要的形式化方法论，在当代逻辑学研究领域具有广泛的理论价值和应用前景。该方法通过构建逻辑系统与策略博弈之间的精确对应关系，为多个逻辑学核心问题提供了统一的动态解释范式。博弈语义的主要应用领域三大应用方向真值定义方面Hintikka（1973）提出的博弈语义（GameSemantics）为经典逻辑公式提供了博弈论解释模型比较领域Fraïssé（1954）与Ehrenfeucht（1961）提出的Ehrenfeucht-Fraïssé博弈，为结构等价性提供了辨别标准证明论研究Lorenzen（1955）提出的对话逻辑（DialogueLogic）将逻辑证明转化为规范的论辩过程赋值博弈的基本概念赋值博弈（ValuationGame）将逻辑公式转化为双人博弈过程，并通过玩家的策略互动判定公式的真值。博弈双方针对命题$$φ$$：证实者V声称$$φ$$是真的证伪者F声称$$φ$$是假的定义70.赋值博弈给定一阶模型$$M$$和赋值$$s$$，任意公式$$φ$$的博弈语义可通过赋值博弈$$G(φ,M,s)$$严格定义。该博弈的行动规则按公式的递归结构定义如表10-1所示。赋值博弈的行动规则表10-1递归结构公式玩家的行动原子命题$$Pd,Rde,···$$若原子命题为真则V获胜，反之则F获胜析取式$$φ∨ψ$$V选择一个析取肢进行博弈合取式$$φ∧ψ$$F选择一个合取肢进行博弈否定式$$¬φ$$两个玩家互换彼此的角色，继续针对$$φ$$进行博弈存在式$$∃xφ(x)$$V选择$$M$$中的一个对象$$d$$，并继续用$$φ(d)$$进行博弈全称式$$∀xφ(x)$$F选择$$M$$中的一个对象$$d$$，并继续用$$φ(d)$$进行博弈博弈语义的核心定理事实16.真值与获胜策略的等价性对于所有模型、赋值和公式，以下两个断言等价：断言(i)$$M,s⊨φ$$断言(ii)V在赋值博弈$$G(M,φ,s)$$中有一个获胜策略核心意义逻辑联结词被具体解释为博弈中的行动规则，而公式的真值则与证实者是否存在获胜策略直接相关。例25：赋值博弈示例（1）问题设定考虑原子命题p、q、r及其构成的公式$$φ:=p∨(q∧¬r)$$，并给定赋值$$v(p)=1,v(q)=1,v(r)=1$$，即这三个命题在赋值$$v$$下都为真。博弈过程（1）初始状态V面对公式$$φ$$，目标是证明其在赋值$$v$$下为真。例25：赋值博弈示例（2）（2）第一轮（析取式）根据博弈规则，V需选择$$p$$或$$q∧¬r$$：选择$$p$$立即获胜（因为$$v(p)=1$$，所以$$φ$$为真）选择$$q∧¬r$$进入更复杂的子博弈不妨假设，V选择右析取肢$$q∧¬r$$，从而进入第二轮。例25：赋值博弈示例（3）（3）第二轮（合取式）F面对$$q∧¬r$$，目标是证伪：选择$$q$$若$$v(q)=0$$可直接获胜选择$$¬r$$将触发角色互换（角色互换意味着由V验证$$r$$为真）不妨假设，F选择了左合取肢$$q$$。（4）终止状态到达原子命题$$q$$后，由于$$v(q)=1$$，从而当前玩家V的主张成立，博弈终止且V获胜。博弈语义的关键特征策略存在性与真值判定值得注意的是，尽管在例25中证实者并未选择最优路径（直接选择$$p$$即可立即获胜），但由于赋值条件的保障，证实者最终依然能够获胜。核心发现判定逻辑真值的关键在于获胜策略的存在性，而非具体的策略选择。理论意义这种"博弈化"视角将传统的静态逻辑关系转化为动态的策略互动过程。10.3博弈结构与博弈逻辑研究范围本节重点讨论博弈结构的狭义概念，其中的博弈形式忽略了玩家及其认知状态，如偏好或信念等。研究价值即便如此，博弈中仍然包含了大量可通过逻辑技术进行研究的结构。10.3.1扩展式博弈博弈的本质特征博弈作为一种具有进程性和动态演化特征的系统，其本质是一个由多主体参与、多层次交互构成的复杂过程。动态特性这种兼具时态演进和策略互动的特性，使其不仅能够刻画传统经济行为中的竞争与合作，还成为研究分布式计算、复杂计算机系统协同以及网络协议优化等前沿领域的理想模型。扩展式博弈的树状表示基本结构扩展式博弈作为博弈中的经典结构，它通常以树状图的形式表示。结构元素决策节点每个节点代表一个玩家的选择时刻分支行动节点的分支表示该玩家在决策时可选择的行动叶子节点树的最终叶子节点对应博弈的结果，通常用来表示玩家的收益或惩罚简单的扩展式博弈示例图10-2简单的扩展式博弈图示说明图10-2展示了一个简单的扩展式博弈树结构，清晰呈现了玩家的决策节点、可选行动分支以及最终博弈结果。扩展式博弈通过树状图直观地描述了博弈的动态过程与玩家的决策顺序。扩展式博弈的形式化描述博弈的谓词表示$$G=(nodes,moves,turn,end,VAL)$$各元素对应各个元素分别对应博弈树的不同部分：节点（nodes）代表博弈中的决策节点。例如，节点A、B分别表示玩家A、B在此处进行选择行动（moves）玩家在每个决策节点可以选择的行动。例如，在A的节点上，玩家A可以选择"合作"或"背叛"；而在左右两处的B节点上，玩家B也有"合作"或"背叛"两种选择扩展式博弈的其他要素轮次（turn）描述了当前由哪位玩家进行决策。例如，玩家A首先在根节点做出决策，然后玩家B在A做出选择后再做出相应的决策最终节点（end）代表博弈的最终状态。在该节点上，所有玩家的决策已完成，博弈的结果也因此得以确定。例如，$$p$$所在的位置就是其中一个最终节点赋值（VAL）解释节点处的命题，例如，给出玩家的效用值由此，扩展式博弈通过博弈树清晰地描述了博弈的过程、玩家轮次及最终结果。加标转换系统的逻辑建模形式化视角从逻辑学和计算理论的视角看，这类具有可选行动的树状结构在形式化方法中被建模为"加标转换系统"，可以用具有如下形式的标准模态逻辑模型表示：$$M=(S,{R_a}_a∈A,V)$$模型要素$$S$$一个由一些状态或一些世界构成的论域$$R_a⊆S×S$$对于行动集合$$A$$中的每个原子行动$$a$$，都对应有一个状态转换关系赋值$$V$$为每个原子性质$$p$$指派了一集合使得它成立的状态进程树的完整表征计算逻辑视角在计算逻辑领域，这些树状结构通常被视为进程行为的完整表征。每个分支路径精确对应系统的一个可能执行轨迹，从而完整刻画了其潜在的行动空间。接下来，我们将探讨这些进程树之间的等价关系。10.3.2博弈等价核心问题在博弈逻辑的研究中，一个重要的问题是关于等价性：给定两个博弈结构，它们何时表示的是同一个博弈？这一问题可以通过计算机科学中的经典模型对比来说明。例26：进程等价性问题考虑图10-3的两个进程，它们是等价的吗？图10-3进程例26的分析：外部行为视角迹等价（TraceEquivalence）从外部行为看，这两个进程的行动序列完全一致，它们都能产生$${ab,ac}$$这两种可能路径。这种基于可观测行为的一致性，在进程代数中被称为"迹等价"（TraceEquivalence）。结论因此在这个层面上，它们可以被视为等价的。例26的分析：内部结构视角结构性差异若深入考察其内部机制，则会发现当中的本质差异：左图：后置的非确定性在执行行动$$a$$后才出现分支选择，这是一种后置的非确定性右图：前置的非确定性在初始阶段就隐含了选择分支，属于一种前置的非确定性互模拟关系这种结构性的差异使得二者无法建立"互模拟"关系——这种更严格的等价关系要求这两个进程不仅产生相同的行动序列，还需要满足结构上的等价性条件。（关于"互模拟"的概念参见本书5.3节，而其在博弈逻辑中的更多应用参见vanBenthem(2014)与FuandZhao(2025)）博弈等价的核心要素观察粒度的重要性例26展现了"博弈等价"的一个核心要素：等价性取决于观察的粒度。层次化的判定标准"博弈等价"存在层次化的判定标准：粗粒度仅考察外部行为一致性的迹等价细粒度要求内部决策结构完全对应的互模拟互模拟关系的可调节性灵活的判定体系在博弈逻辑的理论框架下，互模拟关系展现出丰富的可调节性。多种调节方式研究者可以根据具体需求：简化条件如仅区分行动主体而忽略具体行动类型，来获得更宽松的判定标准构建更广义的等价关系例如，允许合并连续决策的阶段，抑或将焦点转向玩家对结果的控制能力等理论价值这种多层次的判定体系为博弈分析提供了灵活而严谨的形式化工具。10.3.3获胜策略、确定性与逆向归纳法例27：扩展式博弈树考虑以下扩展式博弈树（图10-4），它标记出了玩家A、B的获胜位置。图10-4扩展式博弈树图示说明图10-4展示了一个完整的扩展式博弈树，其中标注了玩家A与玩家B各自的获胜节点，为后续分析获胜策略提供了直观基础。通过博弈树可以直观判断哪位玩家拥有获胜策略。获胜策略的模态刻画玩家B的获胜策略显然，玩家B拥有一个获胜策略，即存在一个策略能确保无论玩家A采取何种行动，B都能做出相应决策最终获胜。动态模态公式这一策略性质可通过以下动态模态公式精确刻画：$$[move_A]⟨move_B⟩win_B$$符号说明$$[move_A]$$全称模态词，表示"对于玩家A而言所有可能的行动"$$⟨move_B⟩$$存在模态词，表示"存在玩家B的某个应对行动"$$win_B$$在最终节点处的谓词，表达了"玩家B获胜"博弈的确定性基础性质在上述博弈中，观察到一个基础而关键的性质：对于任何给定的博弈，两位玩家中必有一方拥有获胜策略。形式化表达这一性质可以通过引入深度为$$k$$的模态算子交替序列$$□

□

···$$来形式化表达（其中的省略号用来表示博弈树的深度）。排中律的博弈论意义考虑以下排中律时：可以发现，标准逻辑中的定律马上就有了博弈论的意义。确定性（Determinacy）的定义赋值博弈中的确定性结合上一节的赋值博弈，它本质上反映了有穷博弈的"确定性"（Determinacy）特征：给定一个公式$$ϕ$$，证实者V要么在针对$$ϕ$$的博弈中拥有获胜策略，要么在针对$$¬ϕ$$的博弈中拥有获胜策略。等价表述对于后一种情况，可以将V的角色转换为证伪者F，从而等价地表示为F在针对$$ϕ$$的博弈中拥有获胜策略。理论基础这种在双人博弈中总有一方拥有获胜策略的性质，被称为"确定性"。该理论结果可以追溯至Zermelo（1913）的研究。定理45.有穷博弈的确定性所有具有固定有穷回合数的零和双人博弈都是确定的。确定性定理的证明（1）证明思路假定玩家分别为A和B。此处给出一个简单的算法，用于确定在任意博弈树节点处哪位玩家拥有获胜策略。该算法从博弈树的最终节点处向上执行。初始化首先，对最终节点进行染色，将A获胜的那些节点染成黑色，而B获胜的那些节点染成白色。确定性定理的证明（2）递归染色规则然后，按照如下步骤逐步扩展这个染色方法，如果节点$$n$$的所有子节点都已经被染色，执行以下操作之一：（1）轮到玩家A行动如果至少有一个子节点是黑色的，则将节点$$n$$染为黑色如果所有子节点都是白色的，则将节点$$n$$染为白色（2）轮到玩家B行动如果至少有一个子节点是白色的，则将节点$$n$$染为白色如果所有子节点都是黑色的，则将节点$$n$$染为黑色确定性定理的证明（3）算法的正确性这个过程最终会将所有玩家A拥有获胜策略的节点染为黑色，将玩家B拥有获胜策略的节点染为白色。原因分析当轮到玩家进行决策时，如果他有获胜策略，他至少能选择一个子节点，使得他在该子节点中也能获胜。归纳证明通过归纳可证，一个玩家在某一轮具有获胜策略，当且仅当，该玩家在下一轮至少能选择一个子节点仍然具有获胜策略。逆向归纳法算法的交叉性上述算法恰好处在博弈论与计算机科学的交汇点，它指向了博弈逻辑中的一个重要算法——逆向归纳法。逆向归纳法的原理假设轮到玩家B行动，并且所有子节点的值都是已知的。此时：玩家B的取值是所有子节点中B-值的最大值对于A的值，他会取在所有B-最佳子节点上的A-值的最小值当轮到A行动时，情况也完全类似。术语说明"B-最佳子节点"表示：在某个决策点上，玩家B的行动能够最大化其自身的效用或收益的子节点。例28：逆向归纳法示例问题设定逆向归纳法：具有两个B-最佳子节点情况。图10-5是以（A-值，B-值）的顺序来标记玩家的收益。图10-5逆向归纳法图示说明图10-5展示了逆向归纳法在具有两个B-最佳子节点情况下的应用，以（A-值，B-值）的顺序标记各节点的收益，直观呈现了玩家的决策推理过程。逆向归纳法从叶子节点向根节点逐步推算最优策略。例28的推理过程玩家A的预见根据逆向归纳法，玩家A会预见到：对于玩家B而言，他有两个同等的最佳选择：$$（0,99）$$和$$（98,99）$$。玩家B的选择由于前一种情况下玩家A的获益更小，由此玩家B会选择$$（0,99）$$。玩家A的最终决策依据以上推理，玩家A会在一开始就选择L-行动，以期获得更大收益$$（3,0）$$。经典求解算法逆向归纳法作为经典的博弈求解算法，它不仅已经被应用到诸如跳棋等现实博弈问题中，更在人工智能的决策规划与策略生成等核心领域有广泛应用。（更多细节参考文献SchaefferandvandenHerik(2002)）10.3.4从算法到博弈：以蓄意破坏博弈为例计算与博弈的深层联系计算任务与博弈论之间存在着深刻的内在关联，这种联系不仅体现在理论层面，更在算法实践中展现出强大的建模能力。路径可达性问题的博弈化基础问题以图论中的路径可达性问题为例：给定有向图$$G=(V,E)$$和节点$$s,t∈V$$，搜索是否从$$s$$到$$t$$存在有向路径。传统视角在传统计算框架下属于P类问题，并可以在多项式时间内高效解决对抗性视角当引入对抗性的干扰因素（如删除路径链接）时，该问题转化为典型的博弈问题，其中搜索方与干扰方形成策略互动蓄意破坏博弈的理论意义案例研究正如vanBenthem(2014)在其经典研究中通过交通网络案例所展示的，这类情形需要通过博弈论模型来完整刻画决策过程。深层统一性这种从纯算法问题到博弈模型的转化，揭示了计算理论与博弈论在解决现实复杂问题时的深层统一性。例29：蓄意破坏博弈场景设定图10-6中，不同线型用以区分连接欧洲两个逻辑与计算中心的不同交通方式。图10-6逻辑与计算中心的连接方式示意图图示说明图10-6展示了欧洲两个逻辑与计算中心之间的多种交通连接方式，不同线型代表不同的交通路径，为蓄意破坏博弈的分析提供了直观的网络结构。不同线型区分了不同的交通连接方式，构成了博弈的基础网络结构。蓄意破坏博弈的问题描述核心节点让我们聚焦于图中的两个核心节点：阿姆斯特丹和萨尔布吕肯。常规情况无论选择何种路径都能顺利抵达目的地。对抗情况如果交通系统突然崩溃，或者有个恶魔开始逐步删除节点间的连接，我们还能顺利到达目的地吗？博弈规则假设在我们旅行的每一个阶段，恶魔都会首先破坏一条连接。这样，问题就变成了：在这种博弈中，谁能获胜？从萨尔布吕肯到阿姆斯特丹玩家的获胜策略从萨尔布吕肯到阿姆斯特丹，由德国出发的玩家拥有一个获胜策略。策略分析如果恶魔的第一步行动是切断去布鲁塞尔或科布伦茨的连接：玩家仍然可以在第一轮到达卢森堡接着在下一轮顺利到达阿姆斯特丹鲁棒性虽然恶魔有可能切断阿姆斯特丹与三个中间城市之一的连接，但玩家依然有两条可靠的路径可以到达目的地。从阿姆斯特丹到萨尔布吕肯恶魔的获胜策略如果恶魔从阿姆斯特丹出发，他就能有获胜策略。策略步骤恶魔首先切断萨尔布吕肯与卢森堡之间的连接如果玩家到达中间的任何城市，恶魔将在下一轮切断通往萨尔布吕肯的最后一条路径蓄意破坏博弈的应用问题转化基于这个问题的研究，可以将任何算法任务转化为一个带有破坏者玩家的"蓄意破坏博弈"。复杂度变化通常情况下，这种转化会导致求解方法的复杂度增加。应用领域如今，蓄意破坏博弈已经被应用于各类任务的研究中，尤其是在计算机科学中的学习场景。双向研究此外，现代计算机科学不仅为博弈分析提供了理论概念和工具，还开始将博弈本身作为研究交互计算的模型。10.4认知博弈及其动态化研究拓展本节将在前文博弈结构分析的基础上，进一步引入玩家的认知和偏好，以此来构建更为全面的博弈逻辑框架。两个关键要素观察能力玩家的观察能力构成了其决策的基础，这种能力既受到博弈本身信息结构的制约，也受到玩家认知水平的限制偏好关系玩家的偏好关系通过影响其对不同结果的评价，从根本上决定了其策略选择的方向相互作用这两个关键要素相互影响、共同作用，最终塑造了博弈的真实动态过程。10.4.1偏好、最佳回应与理性背景回顾第7章已经介绍了偏好逻辑的基本概念，现在引入两类经典的偏好提升规则。定义71（偏好提升规则）对于玩家i，结果集$$X,Y$$间的偏好关系可以通过个体元素间的偏好关系来定义。∀∃-提升规则$$X⪯_i^∀∃Y⟺∀x∈X∃y∈Y(x≤_iy)$$∀∀-提升规则$$X≅_i^∀∀Y⟺∀x∈X∀y∈Y(x≤_iy)$$偏好提升规则的直观理解$$∀∃$$-提升规则的含义集合$$X$$弱偏好于集合$$Y$$，当且仅当，对于$$X$$中的每个元素$$x$$，在$$Y$$中都至少存在一个不劣于$$x$$的元素$$y$$。$$∀∀$$-提升规则的含义集合$$X$$弱偏好于集合$$Y$$，当且仅当，$$Y$$中的每个元素都至少和$$X$$中的所有元素一样好。博弈场景中的偏好提升∀∀-提升规则的应用当玩家在可通达的结果集之间进行选择时，他们可能更倾向于选择那些最小效用值超过其他结果集最大效用值的集合，而这恰好符合了∀∀-提升规则。潜在问题但这种选择方式可能导致不可比较的情况出现。∀∃-提升规则的应用如果将偏好定义为玩家选择的结果集中的最大效用值都大于其他结果集中的最大效用值，这同样是合理的。而这种选择方式可以通过∀∃-提升规则进行形式化描述。例30：偏好提升规则的比较（1）问题设定考虑以下针对行动$$L$$和$$R$$之间的选择（图10-7省略了玩家）：对于行动$$L$$来说，它会使得结果落在$$\{2,3\}$$这个集合中而$$R$$使得结果集落在$$\{1,4\}$$图10-7$$L$$和$$R$$之间的选择图示说明图10-7展示了行动$$L$$与$$R$$之间的选择结构，其中$$L$$对应结果集$$\{2,3\}$$，$$R$$对应结果集$$\{1,4\}$$，为两种偏好提升规则的比较提供了直观基础。两种提升规则对同一选择情境给出了不同的判断结果。例30：偏好提升规则的比较（2）按∀∃-提升规则$$R$$因其最大效用值在所有可能的比较中均大于$$L$$，所以应该选择$$R$$。按∀∀-提升规则会发现$$L$$和$$R$$是无法比较的。逆向归纳法的解释∀∀-提升规则也可以用逆向归纳法理解：玩家$$i$$偏好集合$$Y$$而不是$$X$$，那是因为对于$$i$$而言，$$Y$$中$$i$$的最小效用值更大些。不可比较性问题问题呈现正如例30所示，玩家可能出现两个结果集均不满足∀∀-可比性的情形。解决方案此时就需要借助偏好，引入策略式博弈的形式化定义。不可比较性问题的出现，促使我们进一步完善博弈的形式化框架，为后续认知博弈的动态化分析奠定基础。定义72（策略式博弈）形式化定义任取一个玩家集合$$N$$，策略式博弈$$G$$是一个三元组：$$(N,{A_i}_{i∈N},{≤_i}_{i∈N})$$各要素说明对于每一个$$i∈N$$都有：一个非空的行动集合$$A_i$$每个玩家对策略组合集的一个偏好序$$≤_i$$（策略组合集就是每个玩家的行动序组）符号约定给定一个策略组合$$σ=(σ_1,σ_2,⋯,σ_n)$$：$$σ_i$$表示第$$i$$个人在此组合中的对应行动$$σ_{-i}$$表示其余玩家的联合行动偏好关系与最佳回应偏好关系上述定义中包含了玩家$$i$$的偏好关系：$$σ≤_iσ'$$，当且仅当玩家$$i$$偏好策略组合$$σ'$$至少同偏好$$σ$$一样。最佳回应如果玩家$$i$$没有任何候选行动能令其获得更偏好的结果，那么$$σ_i$$对于玩家$$i$$而言，就是针对其余玩家的联合行动$$σ_{-i}$$的最佳回应。事实17：最佳回应与纳什均衡的模态定义事实17.模态语言定义可以用模态语言定义这样的最佳回应与纳什均衡。最佳回应的模态定义$$BR_i$$定义是$$¬⟨<_i⟩⊤∧¬⟨≈_i⟩⁻⊤$$其中：$$<_i$$表示严格偏好关系$$≈_i$$为不可比较关系纳什均衡纳什均衡是满足公式$$⋀_{i∈N}BR_i$$的那些策略组合。理性（RAT）的定义理性的形式化对于玩家$$i$$，并不存在任何替代行动使得在整个博弈树上通过执行$$σ$$所导致的结果，都严格优于从当前行动开始然后一直执行$$σ$$所导致的结果。理论意义这个定义为博弈中的理性决策提供了清晰的标准，它揭示了理性行为的核心特征：在给定的决策框架内，玩家无法找到任何能产生更好结果的选择。定理46：逆向归纳法策略的刻画定理46内容在一个有穷的扩展式博弈中，逆向归纳法策略是整个行动关系中的最大子关系$$σ$$，它满足：每个节点都至少存在一个后继，并且所有玩家$$i$$均符合RAT属性。理论价值特别地，可通过此定理建立理性（RAT）与逆向归纳法的形式化关联。逆向归纳法从博弈树的叶节点出发，逐步向根节点回溯，在每个节点处确定理性玩家的最优选择，最终刻画出满足RAT属性的最大子关系。10.4.2知识、信念与不完美信息博弈的动态本质博弈的动态本质不仅体现在行动与结果的对应上，更关键的是在其执行过程中玩家的认知变化。研究必要性因此，对于博弈的研究很自然地会涉及玩家的知识和信念。尤其在不完美信息博弈中（如纸牌游戏或麻将等），玩家并不能确切地知道他们处于博弈的哪个阶段。不确定性的根源观察限制如隐藏信息，玩家无法观察到对手的私有信息或已发生的隐蔽行动。认知限制如记忆局限，玩家可能无法完整记忆博弈历史中的所有信息。计算限制如信息处理能力，玩家在有限时间内无法穷举所有可能的策略组合。不确定性的放大随着博弈的推进，这些初始的信息缺陷会通过行动选择的不可观测性、知识与信念的更新以及对手策略的不确定性等因素被不断放大，导致玩家在博弈树中的不确定性不断增长。完整分析的要求因此，完整的博弈分析还需同时考察信息获取的动态过程，以及基于知识与信念的认知状态。例31：完美信息与不完美信息博弈完美信息博弈树图10-8完美信息博弈树不完美信息博弈树图10-9不完美信息博弈树完美信息博弈的策略分析模态公式表示在根节点A上，模态公式：$$[c∪d]⟨a∪b⟩p$$表示：玩家B存在一个策略，使得无论玩家A如何选择（选择$$c$$或$$d$$），B均可以通过后续行动（$$a$$或$$b$$）实现结果$$p$$。不完美信息的表示虚线的含义为了表示出不完美信息，我们在两个B节点处增添虚线。认知变化由此导致了一个认知变化，即玩家B不确定玩家A的初始行动究竟是选择了$$c$$还是$$d$$。直觉理解直觉上，尽管B知道原来实现$$p$$的策略仍然存在，但是因为他并不知道自己所处的确切位置，因此对于选择向左还是向右是无法确定的。认知逻辑框架的应用理论基础根据第6章所介绍的认知逻辑框架，其模型结构的普遍适应性为分析不完美信息博弈中的认知动态提供了理想的形式化工具。知识的定义回顾给定模型$$𝔐$$和状态$$s∈S$$后：$$𝔐,s⊨K_iφ$$，当且仅当$$𝔐,t⊨φ$$对于所有满足$$s~_it$$的$$t$$都成立。应用价值这种认知逻辑的定义可以应用到不完美信息博弈的分析中。例32（例31续）：对于初始行动的无知在博弈树的根节点处，假定玩家A实际上已选择行动$$c$$（图中以黑色圆点标记）。知识公式此时，玩家B知道行动$$a$$或$$b$$都可以导致$$p$$，由此可以得出以下认知公式：$$K_B(⟨a⟩p∨⟨b⟩p)$$例32：对初始行动的无知（2）无知公式但因为B并不知道A的实际选择，从而使他无法区分具体是哪个行动可以保证出现结果$$p$$，因此也可以得出以下公式：$$¬K_B⟨a⟩p∧¬K_B⟨b⟩p$$哲学意义这两个公式恰好就展示了哲学上著名的"从言"（dedicto）与"从物"（dere）的区分。知识更新与博弈动态理论基础8.1节已经详细介绍了"公开宣告逻辑"以及其他的知识更新方式。结合本章概念结合本章定义的理性与逆向归纳法概念，通过以下示例展示这些概念在博弈动态中的具体表现。例33：动态版本的逆向归纳法（1）例28