Multi-Agent AI

Posted on Edited on

引言

多智能体强化学习系统特点

智能体数量非单个

智能体之间存在一定联系：合作、对抗、合作+对抗（多智能体多动机）

智能体不仅需要考虑到环境，还需要考虑到其他智能体的行动

学习环境动态变化

博弈论

minmax

nash equilibrium

1
1-2
1-3

上图说明了制定出合理的策略需要智能体之间communication

1-4

局部最优并不代表全局最优

1-5
1-6

对彼此的最佳对策被称为纳什均衡

1-7

纳什均衡可以有多个

1-8

博弈定义

1-9

占优策略：对于一个玩家来说，拥有一个策略a，不论其他玩家选择任何策略，选择策略a都会使得他的效用u最大，这个策略a就被称为占优策略

1-10

n-玩家纳什均衡定义

q2：是不是所有博弈情况都存在纳什均衡？

  1. 混合策略纳什均衡

    1-11

博弈类型

重复博弈

2-1

  • 为什么要研究重复博弈？

    生活中我们参与的许多战略互动都是持续进行的，比如，我们会与相同的人重复互动等。重复博弈理论提供了一个框架用以研究这种重复行为

2-2
  • 重复博弈定义：同一个基础博弈（阶段博弈）被相同的参与者多次重复进行。换句话说，在重复博弈中，一个标准式博弈被同样的参与者反复进行。
2-3

  • 惩罚的威胁：

    惩罚的威胁是理解重复博弈引入折扣因子的关键概念。基本思想是参与者可能会因为“惩罚”的“威胁”而被阻止利用其短期优势，这种威胁的直观效果就是会降低其长期收益。

    通过未来惩罚的威胁来维持合作。参与者在做决策时不仅要考虑当前收益，还要考虑背叛行为可能招致的未来惩罚，从而在长期利益考量下选择合作而非短期的机会主义行为。

2-4

  • 重复博弈：囚徒困境

    在单次博弈中，背叛是占优策略，但在重复博弈中，未来惩罚的威胁可能使合作成为可能。这为分析现实中的长期合作关系提供了理论基础。

2-5

  • 囚徒困境有一个唯一的纳什均衡：每个参与者都选D（背叛）

  • 现在引入冷酷触发策略：

    • 只要对方参与者选择C，就选择C；

    • 如果在任何时期对方参与者选择D，那么在此后的每个时期都选择D

  • 另一个参与者应该怎么做？

    • 只要她对未来收益的重视程度与当前收益相比不是太小，她最好在每个时期都选择C

  • 冷酷触发策略的工作原理：通过”一旦背叛，永远惩罚”的威胁来维持合作。关键在于参与者对未来收益的重视程度（贴现因子）必须足够高，使得长期合作的收益超过短期背叛的收益。

2-6
  • 每次都选择C的策略是应对冷酷触发策略最好的策略
  • 为什么？
    • 如果她在每个时期都选择C，那么每个时期的结果都是(C,C)，她在每个时期获得收益2
    • 如果她在某个时期转向D，那么她在该时期获得收益3，在此后的每个时期获得收益1
    • 然而，只要她对未来收益的重视程度与当前收益相比不是太小，收益流(3,1,1,…)对她来说比收益流(2,2,2,…)更差 • 因此她最好在每个时期都选择C
  • 为什么冷酷触发策略能够维持合作：虽然背叛能带来一次性的更高收益（3 vs 2），但随后的永久惩罚（每期收益1）使得总体收益低于持续合作（每期收益2）。关键条件是参与者必须足够重视未来收益。
2-7
  • 这张幻灯片指出了重复博弈中的多重均衡问题。除了通过冷酷触发策略维持的合作均衡外，还存在”总是背叛”的均衡。在这种均衡中，由于对方无论如何都会背叛，自己也最好选择背叛，这与单次囚徒困境的结果相同。这说明重复博弈可能存在多个纳什均衡，既有合作的也有非合作的。
2-8

  • 两个关键问题：

    • 耐心程度的量化：要维持合作均衡，参与者需要多重视未来收益？这涉及贴现因子的临界值计算。

    • 均衡结果的多样性：除了完全合作(C,C)和完全背叛(D,D)之外，还有哪些策略组合和结果可以构成纳什均衡？

2-9
2-10
  • 通过冷酷触发策略结合折扣因子来解释折扣因子的边界取值。分别是一直选择合作（C）以及中途换选择（D），分别计算其策略收益，最后比较收益值，即可计算出折扣因子的边界值。
  • 当δ < 1/2时，“一直背叛”是纳什均衡：
    • 无论δ值如何，“一直背叛”策略总是纳什均衡：
      • 如果玩家1总是背叛，玩家2的最佳响应是总是背叛（因为如果玩家2合作，支付为0；如果背叛，支付为1）。
      • 同样，如果玩家2总是背叛，玩家1的最佳响应也是总是背叛。
      • 支付为每期(1,1)，现值为11−δ1−δ1。
      • 没有玩家能通过单方面改变策略（如尝试合作）获得更高支付，因为合作会被立即剥削（支付0），且未来收益折现后不足以补偿。
    • 这个均衡总是存在，但它导致帕累托低效的结果（支付(1,1)低于合作时的(2,2)）。
2-11
2-12
  • 有限步惩罚策略与“以牙还牙”策略计算折扣因子边界值思想与冷酷触发策略计算类似，这里不再详细解释。

扩展形式博弈

2-13
  • 上述内容对比了策略型博弈和扩展式博弈的核心区别，并定义了一种特定类型的扩展式博弈（多阶段可观测行动博弈）。以下是我对关键点的理解：
    1. 核心区别 (Sequentiality & Information):
      • 策略型博弈 (战略式博弈): 强调同时决策。玩家在不知道对手选择的情况下做出一次性决策（如石头剪刀布、静态 Cournot 模型）。收益矩阵是其主要表示形式。
      • 扩展式博弈 (扩展式): 强调行动的先后顺序 (序列性) 和信息结构。玩家在不同时间点行动，并且后行动的玩家可能（但不一定）能观察到先行动玩家的选择（如象棋、动态 Stackelberg 模型、序贯议价）。博弈树是其核心表示工具。
    2. 关注类型 (Multi-stage with Observed Actions):
      • 多阶段 (Multi-stage): 博弈过程被划分为不同的阶段。
      • 可观测行动 (Observed Actions): 这是定义中最关键的信息假设。它意味着在每个阶段开始时，所有玩家都完全知道之前所有阶段中所有玩家选择的所有行动。这被称为完美信息 (Perfect Information)，但PPT的表述更一般化，因为它允许同一阶段内的玩家同时行动 (Simultaneous Moves)。
      • 完美信息 vs. 可观测行动： “完美信息”通常指在每个决策点，玩家确切知道之前发生的所有行动（即知道整个历史，知道当前处于哪个决策节点）。PPT定义的“具有可观测行动的多阶段博弈”在阶段之间是完美信息的（玩家知道之前所有阶段的所有行动），但在一个阶段内部，如果存在同时行动，则在该阶段内行动时，玩家可能不知道同阶段其他玩家的即时选择（但在下一阶段开始前，这些行动会被揭示）。这比严格的“完美信息”博弈（要求每个决策点都无同时行动且完全知晓历史）范围更广。
    3. 表示工具 (Game Trees):
      • 博弈树是表示扩展式博弈最直观的方式。树根代表起点，树枝代表玩家可能的行动，树节点代表决策点（轮到哪个或哪些玩家行动），树叶代表终点（对应收益/结果）。
      • 它天然地刻画了行动顺序和可能的路径 (历史)。
    4. 关键概念 (Histories):
      • 历史记录 (Histories) 是扩展式博弈模型中的基础构件。一个历史就是一个从博弈开始到某个时间点为止，所有玩家按顺序采取的行动的序列。
      • 每个决策点（博弈树节点）都对应一个唯一的历史，该历史描述了到达该节点所经过的路径。
      • 玩家的信息集 (Information Sets) 通常由其无法区分的一组历史（节点）来定义。但在PPT定义的“具有可观测行动的多阶段博弈”中，由于行动完全可观测，每个信息集通常只包含一个节点（即玩家总是确切知道自己处于哪个决策点），除非在同一个阶段内存在同时行动（此时玩家可能不知道同阶段对手的即时选择）。
2-14
  • 玩家角色：
    • 玩家1 - 进入者 (Entrant): 考虑是否进入一个新市场（通常是一个已有在位企业的市场）。
    • 玩家2 - 在位者 (Incumbent): 是市场现有的主导企业，对进入者的行动做出反应。
  • 行动顺序与信息：
    • 这是一个序贯博弈：玩家1先行动，玩家2后行动。
    • 关键信息假设： 玩家2在做出决策（容纳还是斗争）之前，完全观察到了玩家1的选择（进入或不进入）。这意味着玩家2知道博弈进行到了哪个决策点（即玩家1选了哪个行动）。
    • 这符合之前定义的“具有可观测行动”的多阶段博弈。在这里，只有一个阶段玩家1行动，紧接着一个阶段玩家2行动，且玩家2的行动是基于完全知晓玩家1行动的情况下做出的。
  • 博弈树表示：
    • 这个例子非常适合用博弈树来表示：
      • 根节点 (Root): 玩家1的决策点（进入 / 不进入）。
      • 中间节点 (Decision Nodes): 玩家1选择“进入”后，会到达玩家2的决策点（容纳 / 斗争）。玩家1选择“不进入”后，博弈直接结束。
      • 叶节点 / 终点节点 (Terminal Nodes / Leaves): 代表博弈结束的点，标有收益向量 ((x, y))。每个叶节点对应一个完整的历史（行动序列）和最终的收益结果。
  • 收益：
    • 收益 ((x, y)) 的具体数值决定了博弈的结果和均衡。虽然没有给出具体数字，但典型的设定可能是：
      • (不进入): 进入者收益为0（无成本无收入），在位者收益较高（维持垄断利润）。
      • (进入, 容纳): 进入者获得正利润（但低于垄断利润），在位者利润下降（但仍为正，因为共享市场）。
      • (进入, 斗争): 进入者亏损（因在位者发起价格战等），在位者也亏损（价格战成本）。虽然进入者损失可能更大，但斗争通常对双方都不利，是两败俱伤的结果。
    • 玩家2（在位者）的决策取决于哪种行动（容纳或斗争）在给定玩家1已进入的前提下，能给他带来更高的收益 (y)。
  • 要分析这个博弈的均衡（例如，子博弈精炼纳什均衡），就需要具体设定收益值，并逆向归纳求解玩家2在观察到“进入”后的最优反应，以及玩家1预测到玩家2的最优反应后，最初是否选择“进入”。
2-15
  • 扩展型博弈的一些基本符号定义
2-16
  • 纯策略 (Pure Strategy):
    • 在扩展式博弈中，纯策略不仅仅是玩家在博弈开始时的一个单一选择。它是一个完整的行动计划。
    • 策略必须规定玩家在博弈的每一个可能阶段 (k)，面对每一个可能到达该阶段的历史路径 (hᵏ ∈ Hᵏ) 时，他会选择哪个可用的行动 (sᵢᵏ(hᵏ) ∈ Sᵢ(hᵏ)。
    • 为什么需要这么复杂？
      • 因为博弈是序贯的，并且玩家在决策时可能面临不同的局面（由不同的历史 hᵏ 描述）。一个完整的策略必须说明玩家在 所有可能遇到的情况 下会怎么做，即使某些情况在博弈实际进行中可能不会发生（如果玩家遵循这个策略的话）。
    • 形式上，玩家 i 的策略 sᵢ 是一个函数集合 {sᵢ⁰, sᵢ¹, …, sᵢᴷ}，其中每个函数 sᵢᵏ 将阶段 k 的历史集合 Hᵏ 映射到该玩家在该历史下可用的行动集合 Sᵢ(Hᵏ) 中的一个具体行动。
  • 策略组合生成博弈路径:
    • 当所有玩家都选定他们的纯策略 (s₁, s₂, …, sₗ) 后，博弈的实际进行路径就被唯一确定了。
    • 路径是通过递归应用所有玩家的策略函数来生成的：
      • 阶段 0: 从初始历史 h⁰ = ∅ 开始。所有玩家根据他们的策略 sᵢ⁰(∅) 选择行动，形成行动组合 a⁰ = (s₁⁰(∅), s₂⁰(∅), …, sₗ⁰(∅))。阶段 0 后的历史变为 h¹ = a⁰。
      • 阶段 1: 面对历史 h¹ = a⁰。所有玩家根据他们的策略 sᵢ¹(a⁰) 选择行动，形成行动组合 a¹ = (s₁¹(a⁰), s₂¹(a⁰), …, sₗ¹(a⁰))。阶段 1 后的历史变为 h² = (a⁰, a¹)。
      • 后续阶段: 以此类推，直到最终阶段 K。阶段 K 后的历史 hᴷ⁺¹ = (a⁰, a¹, …, aᴷ) 就是终端历史。
    • 策略组合 s 完全决定了终端历史 hᴷ⁺¹。
  • 收益 (Payoffs):
    • 玩家的收益取决于博弈的最终结果 (outcome)，即终端历史 hᴷ⁺¹。
    • 每个玩家 i 有一个效用函数 (utility function) uᵢ，该函数将每个可能的终端历史 hᴷ⁺¹ 映射到一个实数，表示玩家 i 在该结果下获得的收益（或效用）。
    • 由于策略组合 s 决定了终端历史 hᴷ⁺¹，因此我们也可以说策略组合 s 决定了每个玩家的收益，记作 uᵢ(s)。uᵢ(s) 本质上是 uᵢ 在由 s 决定的那个特定终端历史 hᴷ⁺¹ 上的取值。
  • 扩展式博弈中的核心概念：
    • 纯策略: 是玩家针对所有可能历史制定的完整应变计划，表现为一组映射函数 {sᵢᵏ}，每个函数为特定阶段 k 的每个可能历史 hᵏ 指定一个行动。
    • 策略组合决定路径: 当所有玩家选定策略后，博弈的路径（行动序列 a⁰, a¹, …, aᴷ）和最终的终端历史 hᴷ⁺¹ 就被策略函数递归地、确定性地生成。
    • 收益定义在结果上: 玩家的收益由终端历史（博弈的最终结果）决定。效用函数 uᵢ 量化了玩家对每个可能结果的偏好。策略组合 s 通过决定终端历史 hᴷ⁺¹ 来间接决定每个玩家的收益 uᵢ(s)。
  • 理解纯策略的这种“完备应变计划”性质对于分析扩展式博弈的均衡（如子博弈精炼纳什均衡）至关重要，因为它要求玩家即使在“偏离均衡路径”的历史下（即如果博弈意外地到达了那里），也要指定一个行动。
2-17
  • 关键总结 (PPT最后一句):

一个玩家的策略规定了该玩家在其轮到行动的每一个历史（例如，玩家2在{C}之后或{D}之后）处所选择的行动。

  • 玩家 1 的策略只需要规定在唯一的历史 ∅ 处选择 C 或 D。
  • 玩家 2 的策略必须规定在 两个 可能的历史 {C} 和 {D} 处分别选择什么行动（E/F 和 G/H 的组合）。
2-18

  • 在给定的扩展式博弈及其转换后的标准式（策略型）博弈中，策略组合（L, RL）不是纳什均衡（Nash equilibrium）。以下基于提供的收益矩阵和纳什均衡的定义，逐步解释原因。

  • 博弈的收益矩阵：

    玩家1  玩家2 LL LR RL RR
    L 3,2 3,2 2,3 2,3
    R 4,1 0,1 4,1 0,1

  • 玩家2的策略含义（RL策略）：

    • RL = 如果玩家1选择L，则玩家2选择R；如果玩家1选择R，则玩家2选择L。

  • 策略组合（L, RL）的含义：

    • 玩家1选择L。
    • 玩家2选择RL策略（因此，当玩家1选L时，玩家2选R）。
    • 实际发生的行动路径：玩家1选L → 玩家2选R。

  • 对应收益：从收益矩阵中，行L、列RL的单元格为（2,3），即玩家1收益为2，玩家2收益为3。

  • 纳什均衡的定义

    • 纳什均衡要求：在给定其他玩家的策略下，没有任何一个玩家能通过单方面改变自己的策略而获得更高的收益。也就是说：
    • 玩家1的策略必须是对玩家2策略的最优响应（best response）。
    • 玩家2的策略必须是对玩家1策略的最优响应。 如果任何一个玩家有激励偏离当前策略，则该组合不是纳什均衡。

  • 为什么（L, RL）不是纳什均衡？

    在策略组合（L, RL）下，玩家1有激励单方面改变策略。具体分析如下：

  1. 给定玩家2的策略RL，玩家1的收益比较：
    • 如果玩家1保持选择L（当前策略）：
      • 玩家2的RL策略规定：当玩家1选L时，玩家2选R。
      • 因此，收益为（2,3），玩家1获得收益2。
    • 如果玩家1单方面改为选择R：
      • 玩家2的RL策略规定：当玩家1选R时，玩家2选L（因为RL策略在玩家1选R时对应选L）。
      • 因此，行动路径为（R, L），收益为（4,1）（从收益矩阵的行R、列RL单元格可得）。
      • 玩家1获得收益4。
  2. 玩家1的激励分析：
    • 玩家1的收益从2（选L）变为4（选R），收益增加（4 > 2）。
    • 因此，玩家1有严格激励（strict incentive）偏离策略L，改为选择R。因为收益更高，且这是单方面改变（玩家2的策略RL保持不变）。
  3. 玩家2的响应（虽不必要，但完整性分析）：
    • 在（L, RL）下，玩家2的收益为3（给定玩家1选L，玩家2选R）。
    • 如果玩家1保持选L，玩家2改变策略（如改为LL、LR或RR）：
      • 例如，改为LL：当玩家1选L时，玩家2选L，收益为2（行L、列LL单元格为（3,2），玩家2收益2 < 3）。
      • 改为LR：当玩家1选L时，玩家2选L，收益为2（行L、列LR单元格为（3,2），玩家2收益2 < 3）。
      • 改为RR：当玩家1选L时，玩家2选R，收益为3（与当前相同）。
      • 因此，玩家2无严格激励偏离RL（因为改变策略要么收益降低，要么不变），但这不是关键，因为玩家1的偏离已足够破坏均衡。
  • 为什么PPT中列出的（R, RL）是纳什均衡，而（L, RL）不是？
    • （R, RL）是纳什均衡（如PPT所列）：
      • 玩家1选R，玩家2选RL（当玩家1选R时，玩家2选L）。
      • 收益为（4,1）。
      • 给定玩家2的RL策略，玩家1：选R收益4，选L收益2（因为如果玩家1选L，玩家2选R，收益2），4 > 2，因此玩家1无激励偏离。
      • 给定玩家1选R，玩家2：任何改变（如改为LL、LR或RR），在玩家1选R时收益均为1（无严格增加），因此玩家2无激励偏离。
      • 所以（R, RL）满足纳什均衡条件（弱均衡）。
    • （L, RL）不是纳什均衡：
      • 如上所述，玩家1有严格激励偏离L到R，因此不满足“无玩家有激励偏离”的条件。
  • 总结
    • （L, RL）不是纳什均衡，因为玩家1可以通过单方面改变策略（从L到R）将收益从2提高到4。 给定玩家2的RL策略，玩家1选择L不是最优响应。
    • 这体现了纳什均衡的核心要求：每个玩家的策略必须是对其他玩家策略的最优响应。在扩展式博弈中，这种分析也揭示了为什么有些策略组合在标准式中看似可行，但因动态不一致而被排除（如这里玩家1的偏离激励）。
2-19

这张PPT探讨了进入博弈的均衡合理性，通过扩展式和标准式表示揭示了纳什均衡的局限性。以下是详细分析：

博弈结构与收益

扩展式表示（博弈树）：

  • 玩家1（进入者）：先行动，选择：
    • In（进入市场）
    • Out（不进入市场）→ 收益 (1,2)
  • 玩家2（在位者）：观察到进入者行动后选择：
    • A（容纳）→ 收益 (2,1)
    • F（斗争）→ 收益 (0,0)

标准式表示（收益矩阵）：

进入者  在位者 容纳 (A) 斗争 (F)
进入 (In) (2,1) (0,0)
不进入 (Out) (1,2) (1,2)

纳什均衡分析

  1. (In, A)：
    • 进入者收益：2（若改为Out，收益1<2）→ 无偏离激励
    • 在位者收益：1（若改为F，收益0<1）→ 无偏离激励
      ✅ 是纳什均衡
  2. (Out, F)：
    • 进入者收益：1（若改为In，在位者选F则收益0<1）→ 无偏离激励
    • 在位者收益：2（无论选A或F，收益均为2）→ 无偏离激励
      ✅ 是纳什均衡（弱均衡）

均衡合理性检验

为什么 (Out, F)不合理？

尽管 (Out, F) 是纳什均衡，但它在动态博弈中不可信（缺乏子博弈精炼性）： 1. 在位者的空威胁： - 在位者声称“若你进入，我会斗争（F）”，但若进入者真的选择 In： - 在位者选 A 收益为 1 - 在位者选 F 收益为 0（更差） → 理性在位者实际会选择 A，而非 F。

  1. 进入者的理性决策：
    • 进入者知道在位者的威胁不可信（一旦进入，在位者必选 A）。
    • 因此进入者应选择 In（收益2 > 选Out的收益1）。

逆向归纳验证：

  1. 若进入者选 In，在位者在子博弈中：
    • 选 A → 收益 1
    • 选 F → 收益 0
      → 最优选择是 A。
  2. 进入者预判：
    • 选 In → 收益 2（因在位者会选A）
    • 选 Out → 收益 1
      → 最优选择是 In。

结论

均衡 合理性 原因
(In, A) ✅ 合理 威胁可信，符合序贯理性
(Out, F) ❌ 不合理 依赖不可信的空威胁（动态不一致）
  • 核心问题：纳什均衡在扩展式博弈中可能包含不可信威胁，需通过子博弈精炼纳什均衡（逆向归纳法）剔除不合理的均衡。
  • 本例唯一合理均衡：(In, A)，即进入者进入，在位者容纳。
2-20
  • 回顾匹配硬币博弈（matching pennies game）的两阶段扩展式版本。
  • 在这个博弈中，存在两个真子博弈（proper subgames） 以及博弈本身（它也是一个子博弈），因此总共有三个子博弈。

定义： 在一个（完美信息）博弈树中，每一个节点，连同从该节点到达之后所剩余的博弈部分，被称为一个子博弈（subgame）。
即，每一个非终端历史（non-terminal history） ( h ) 都对应一个子博弈。

关键概念理解：

  1. 子博弈 (Subgame):

    • 子博弈是原博弈的一部分，它起始于博弈树中的某个单一决策节点（该节点代表一个特定的非终端历史 ( h^k )），并包含该节点之后的所有后续决策节点、行动分支和终端节点。
    • 它本身必须构成一个完整的、独立的博弈，拥有明确的起点（该决策节点）、后续行动规则和最终收益。
    • 子博弈继承了原博弈的所有规则（玩家、行动、信息、收益函数）。

  2. 非终端历史 (Non-terminal History):

    • 指那些不是博弈最终结果的历史 ( h^k )（即 ( k < K+1 )，其中 ( K+1 ) 是终端历史的索引）。
    • 每个这样的历史 ( h^k ) 都标志着博弈进行到了一个尚未结束的决策点。
    • 关键联系： 每个非终端历史 ( h^k ) 都唯一确定了一个子博弈的起始点。这个子博弈就是从历史 ( h^k ) 所对应的那个决策节点开始的剩余游戏部分。

  3. 子博弈的数量:

    • 在完美信息（perfect information） 博弈（即每个信息集只包含一个节点）中，子博弈的数量等于非终端决策节点的数量。
    • 示例中提到匹配硬币两阶段博弈有三个子博弈：
      • 子博弈 1： 起始于玩家1的第一个决策节点（对应初始历史 ( h^0 = )）。这就是整个博弈本身。
      • 子博弈 2： 起始于玩家2在玩家1选择“正面”之后的决策节点（对应历史 ( h^1 = (Heads) )）。
      • 子博弈 3： 起始于玩家2在玩家1选择“反面”之后的决策节点（对应历史 ( h^1 = (Tails) )）。
    • 后两个是真子博弈（proper subgames），因为它们严格包含在原博弈之内且不等于原博弈。

  4. 为什么子博弈概念重要？

    • 均衡精炼： 子博弈概念是定义子博弈精炼纳什均衡（Subgame Perfect Nash Equilibrium, SPNE） 的核心。SPNE 要求均衡策略不仅在原博弈上构成纳什均衡，而且在每一个可能的子博弈上也构成纳什均衡。这旨在剔除那些依赖不可信威胁或承诺的纳什均衡（例如之前进入博弈中的 (Out, F) 均衡）。
    • 分析工具： 子博弈结构使得我们可以使用逆向归纳法（backward induction） 来求解完美信息有限博弈的 SPNE。我们从最小的子博弈（最接近终点的）开始求解，将其解（收益或最优行动）代入其父节点，再逐步倒推回根节点。
    • 模块化分析： 允许将大型复杂博弈分解为更小的、可管理的子部分进行分析。

  5. 子博弈求解方法解析

    https://zhuanlan.zhihu.com/p/199055190

势博弈

2-21
  • 请注意，对于所有厂商 i 和所有 q−i>0 的情况：
    • ui(qi,q−i)−ui(qi′,q−i)>0 当且仅当 (iff) Φ(qi,q−i)−Φ(qi′,q−i)>0 ，此条件对于所有 qi,qi′>0 均成立。
    • 说明：
      • 这条关键的陈述指出，在其他厂商产量不变的情况下，厂商 i 从产量 qi′ 转换到 qi 能否增加自身利润，与这个转换能否增加函数 Φ 的值，两者是完全等价的。

这张PPT的核心思想是为古诺竞争模型引入一个称为“势函数”(Potential Function) 的概念，并证明此模型是一个“势博弈”(Potential Game)。

  1. 什么是古诺竞争？

    这是一个经典的经济学模型，描述了在一个寡占市场中，几家厂商如何进行产量竞争。每家厂商都假设其竞争对手的产量是固定的，然后选择能让自己利润最大化的产量。当所有厂商都达到一个状态，即没有任何一家厂商可以单方面改变产量来增加自己的利润时，市场就达到了纳什均衡 (Nash Equilibrium)。

  2. 为什么要引入奇怪的函数 Φ？

    支付函数 ui 非常直观，它就是厂商 i 的利润。然而，函数 Φ 看起来很抽象，它将“所有厂商产量的乘积”与“单位利润”相乘，并没有直接的经济学意义。

    它的真正价值在于其数学性质。投影片的最后一条结论揭示了这个性质：任何单一厂商 i 调整策略 (产量 qi) 所带来的自身利润变化方向，都和函数 Φ 的变化方向完全一致。

  3. 这意味着什么？(核心理解)

    这意味着，原本一个复杂的多人博弈问题（每个厂商都在最大化自己的 ui），可以被转化为一个相对简单的“寻找单一函数 Φ 最大值”的问题。

    • 简化分析：我们不再需要同时追踪 I 个不同厂商的利润函数，只需要分析一个共同的“势函数”Φ 即可。
    • 保证均衡存在：在势博弈中，势函数 Φ 的局部最大值点对应着该博弈的纳什均衡。因为一个有界的连续函数必然存在最大值，这就为证明古诺均衡的存在性提供了一条优雅的路径。
    • 收敛性：势博弈还有一个重要特性，即如果玩家们轮流进行“最优反应”（每次都选择当下能让自己利润最大化的策略），这个过程最终一定会收敛到一个纳什均衡。函数 Φ 就像一个山坡，玩家们的每一步调整都像是在爬坡，最终必然会走到一个山顶（均衡点）。
2-22

这两张PPT分别介绍了序数势博弈和精确势博弈。

  1. 与“序数势”的核心区别

    理解“精确势”的关键在于将其与上一张幻灯片中的“序数势”进行对比：

    • 序数势 (Ordinal Potential)：只要求参与者收益变化的方向与势函数变化的方向一致。
      • 通俗地说：“只要我换策略能多赚钱，Φ 的值就一定会变大。” 它不关心你多赚了1块钱还是100块钱。
    • 精确势 (Exact Potential)：要求参与者收益变化的确切数值与势函数变化的确切数值完全相等。
      • 通俗地说：“如果我换策略能多赚10块钱，Φ 的值就也必须不多不少，正好增加10。”

  2. 更严格的条件

    显然，“精确势”是一个比“序数势”严格得多的条件。如果一个博弈是精确势博弈，那么它必然也是一个序数势博弈（因为如果两个改变量的数值相等，它们的正负号必然相同）。但反过来不成立，很多序数势博弈并不能满足精确势的苛刻条件。

  3. 指正幻灯片中的笔误

    需要指出，幻灯片的最后一行存在一个明显的笔误。它写着 “G is called an exact potential game if it admits an ordinal potential.”（如果一个博弈拥有一个序数势，它就被称为一个精确势博弈）。这在逻辑上是错误的。

    • 正确表述应为：“如果一个博弈 G 拥有一个精确势函数 (exact potential)，那么它就被称为一个精确势博弈。”
2-23

这张幻灯片通过一个具体的2x2矩阵博弈（囚徒困境的一个变体）的例子，非常直观地展示了“势函数”是如何运作的。这张幻灯片的核心目的是让我们验证所给出的矩阵 P 是否真的是博弈 G 的一个势函数。

我们可以通过检验定义来验证。让我们看看当某个参与者单方面改变策略时，他个人收益的变化量是否与势函数 P 的变化量相匹配。

1. 验证过程

我们分别检查行参与者（玩家1）和列参与者（玩家2）的决策。

  • 检验玩家1（行选择者）

    • 当玩家2选择“左”时

      ：玩家1在“上”（收益1）和“下”（收益0）之间选择。

      • 收益变化: u1(上, 左)−u1(下, 左)=1−0=1
      • 势函数变化: P(上, 左)−P(下, 左)=4−3=1
      • 两者完全相等。

    • 当玩家2选择“右”时

      ：玩家1在“上”（收益9）和“下”（收益6）之间选择。

      • 收益变化: u1(上, 右)−u1(下, 右)=9−6=3
      • 势函数变化: P(上, 右)−P(下, 右)=3−0=3
      • 两者完全相等。

  • 检验玩家2（列选择者）

    • 当玩家1选择“上”时

      ：玩家2在“左”（收益1）和“右”（收益0）之间选择。

      • 收益变化: u2(上, 左)−u2(上, 右)=1−0=1
      • 势函数变化: P(上, 左)−P(上, 右)=4−3=1
      • 两者完全相等。

    • 当玩家1选择“下”时

      ：玩家2在“左”（收益9）和“右”（收益6）之间选择。

      • 收益变化: u2(下, 左)−u2(下, 右)=9−6=3
      • 势函数变化: P(下, 左)−P(下, 右)=3−0=3
      • 两者完全相等。

2. 结论

由于任何参与者单方面改变策略所带来的收益变化，都精确地等于势函数 P 中对应数值的变化，因此，矩阵 P 是博弈 G 的一个精确势函数 (exact potential function)。这个博弈 G 是一个精确势博弈。

3. 势函数的威力：寻找纳什均衡

这个例子的美妙之处在于，它展示了势函数如何简化均衡的寻找过程。寻找博弈 G 的纯策略纳什均衡，现在等价于寻找势函数矩阵 P 的“稳定点”。

观察势函数矩阵 P：

P=(4330)

矩阵中的最大值是4，位于（上，左）位置。让我们看看这个点是否稳定：

  • 如果从 P=4（上，左）出发，玩家1单方面移到“下”，P的值会从4变成3，他不会移动。
  • 如果从 P=4（上，左）出发，玩家2单方面移到“右”，P的值会从4变成3，他也不会移动。

因为没有任何一方有动机从（上，左）这个位置离开，所以它是一个纳什均衡。这对应于原博弈 G 中的（1,1）这个结果。这个例子清晰地表明，势函数的局部最大值（在此例中也是全局最大值）对应着博弈的一个纳什均衡。这正是势函数在博弈分析中的核心价值。

2-24

有限序数势博弈的结果是有限的，势函数会为每一个博弈策略赋予一个值，因此必然存在一个最大值，这个最大值就是纳什均衡点。

2-25

1. 核心结论

结论是最后一条：当厂商 i 单方面将自己的产量从 q'_i 变为 q_i 时，他个人利润的变化量，与我们构造的那个看起来很复杂的函数 Φ* 的变化量是完全相等的。这正是“精确势函数”的定义。

2. 数学证明（为什么这个结论成立？）

2-26

最后比较两个Δ即可

2-27

标题：有限序数势博弈中的简单动态 (Simple Dynamics in Finite Ordinal Potential Games)

定义 (Definition)

策略空间 S 中的一条路径 (path) 是一个策略向量序列 (s0,s1,⋯)，其中任意两个连续的策略只在一个坐标上不同（即，每一次恰好只有一名参与者改变了他的策略）。

一条改进路径 (improvement path) 是一条路径 (s0,s1,⋯)，它满足：

  • uik(sk)<uik(sk+1)，其中策略 sk 和 sk+1 在第 ik 个坐标上不同。换句话说，对于那个改变了策略的参与者来说，他的收益得到了改善。

一条改进路径可以被认为是“短视参与者” (myopic players) 动态生成的结果。

这张幻灯片将我们的视角从静态的“均衡分析”转向了动态的“演化过程分析”。它为我们描述“一个博弈是如何一步步演变的”提供了正式的语言。这对于理解系统如何达到稳定状态至关重要。

1. “路径”与“改进路径”的通俗解释

  • 路径 (Path)：你可以把它想象成一盘棋的“棋谱”或一个游戏的“回合记录”。它记录了博弈状态是如何一步步变化的，其核心规则是“一次只动一个”。在 sk 这一步，只有一名参与者会改变他的行动，从而进入 sk+1 状态。这是一种分析动态过程的合理简化。
  • 改进路径 (Improvement Path)：这是一种特殊的、由理性驱动的路径。它不仅记录了系统的演变，还说明了为什么会这样演变。每一步的发生，都是因为某个参与者发现“如果我单方面改变策略，我的收益会立刻增加”，于是他就这么做了。这完美地描述了那些只顾眼前利益的参与者的行为。

2. “短视参与者” (Myopic Players) 的概念

这是理解“改进路径”背后行为动机的关键。

  • “短视”意味着参与者们并不深谋远虑，他们不会去预测对手的对手的反应。
  • 他们的决策逻辑非常简单：“在当前这个局面下，我有没有一个别的选择能让我马上赚得更多？”
  • 如果答案是“有”，那么某个参与者就会采取行动，从而推动整个系统沿着“改进路径”向前走一步。这个过程可以被看作是一系列“更优反应 (better response)”的链式反应。

3. 为什么要在势博弈中讨论这个？（核心洞见）

定义这些概念的最终目的，是为了引出势博弈最强大的性质之一：动态收敛性。

我们可以设想一下：

  1. 在普通博弈中：一条“改进路径”可能会没完没了地走下去，甚至可能陷入一个循环（比如A动、B动、C动，结果又回到了A动之前的局面），永远无法达到一个稳定的纳什均衡。
  2. 但在势博弈中：奇迹发生了。我们知道，在势博弈中，只要某个参与者 i 的收益 uᵢ 增加了，全局的势函数 Φ 的值也必须增加。
  3. 因此，在势博弈里，每一条“改进路径”都必然是一条“势函数 Φ 值不断增加的路径”。
  4. 在一个有限博弈中，势函数 Φ 的可能取值是有限的，它必然有一个最大值。Φ 的值不可能无限地增加下去。

结论：在有限势博弈中，任何“改进路径”走不了几步就必然会停止。它会在哪里停下呢？它会停在一个任何人都无法再单方面改善自己收益的地方——而这个地方，根据定义，就是一个纯策略纳什均衡。

2-28

标题：有限精确势博弈的特征描述 (Characterization of Finite Exact Potential Games)

  • 对于一条有限路径 γ=(s0,s1,…,sN)，我们令：

    I(γ)=i=1∑N(umi(si)−umi(si−1))

    其中，mi 指代在路径的第 i 步改变其策略的参与者。

  • 如果 s0=sN，则路径 γ=(s0,…,sN) 是闭合的 (closed)。如果在此外对于每一个 0≤l<k≤N−1 都有 sl\=sk，那么它就是一条简单闭合路径 (simple closed path)。

定理 (Theorem)

一个博弈 G 是一个精确势博弈，当且仅当对于所有有限简单闭合路径 γ，都有 I(γ) = 0。此外，只检验长度为4的简单闭合路径就足够了。

这个数学定理，它为我们提供了一个“试金石”，用来检验任何一个有限博弈到底是不是一个“精确势博弈”，而无需我们去猜测或构造那个势函数 Φ。

2-29

标题：网络拥堵博弈 (Network Congestion Games)

  • 一个包含 n 个用户的有向图 (directed graph) G=(V,E)，
  • 图 G 中的每一条边 (edge) e 都有一个延迟函数 (delay function) fₑ，
  • 用户 i 的策略 (Strategy) 是选择一条从起点 (source) sᵢ 到终点 (destination) tᵢ 的路径 (path) Aᵢ，
  • 一条路径的延迟是该路径上所有边的延迟之和，
  • 每个用户都想通过选择最佳路径来最小化 (minimize) 其自身的延迟。

这张幻灯片介绍了一类在现实世界中应用极其广泛的博弈模型——网络拥堵博弈。这是理解交通堵塞、互联网数据包路由、供应链物流等众多问题的核心理论框架。

1. 博弈的核心要素

这个模型非常直观，它完美地捕捉了“拥堵”现象的本质：

  • 参与者 (Players)：n 个用户（比如，n 位司机）。
  • 策略 (Strategies)：每个司机可以选择的路线（例如，从家 sᵢ 到公司 tᵢ 的不同路径）。
  • 成本 (Cost)：每个司机在路上花费的时间，即“延迟”。

这个博弈最关键、最有趣的地方在于成本（延迟）的计算方式。一条路（边 e）的延迟fₑ不是一个固定的数，而是一个函数。它的值取决于有多少人同时在使用这条路。

2. 博弈的内在冲突

每个司机都想自私地选择一条“最快”的路。但正是因为所有人都这么想，才导致了问题的产生：

  • 如果有一条近路看起来最快，所有司机可能都会涌向这条路。
  • 结果，这条路变得极度拥堵，它的延迟函数 fₑ(x) 因为 x（用户数）变得很大而给出一个非常高的延迟值。
  • 这条所谓的“最快”的路，实际上可能比其他更长但无人问津的路要慢得多。

每个人的最优选择都依赖于其他所有人的选择。我的决策影响你的成本，你的决策也影响我的成本。这就是博弈的核心所在。

3. 与“势博弈”的深刻联系（核心洞见）

这个模型最惊人的特性是，网络拥堵博弈是“精确势博弈”的经典范例。这是由学者 Rosenthal 在1973年发现的里程碑式成果。

存在一个全局的势函数 Φ（通常称为罗森塔尔势函数），它能够完美地刻画整个系统的动态。这个势函数的定义方式非常巧妙：

2-30

其中，xe 是当前选择了边 e 的总用户数。这个公式的含义是，把网络中每一条边的“从第1个用户到第 xe 个用户的延迟依次加起来”，然后再把所有边的这个值汇总。

可以被严格证明：当任何一个用户 i 单方面改变自己的路径时，他个人延迟的变化量，与这个全局势函数 Φ 的变化量是完全相等的！

4. 重要推论

既然拥堵博弈是精确势博弈，那么我们之前讨论过的所有优美性质就都可以应用在这里：

  1. 均衡必然存在：任何一个网络拥堵博弈都至少存在一个纯策略纳什均衡。在交通模型里，这被称为“瓦德罗普均衡 (Wardrop equilibrium)”。这意味着，总会存在一种稳定的交通分配格局，在这种格局下，没有单个司机可以通过单方面改变路线来缩短自己的通勤时间。
  2. 动态必然收敛：如果司机们是“短视的”（例如，每天根据昨天的路况尝试寻找更快的路），这个不断调整、学习的过程必然会收敛到一个稳定的均衡状态，而不会永久地混乱或振荡下去。

纳什均衡求解

零和博弈及纳什均衡计算

3-1

练习：斯塔克尔伯格双寡头模型 (Exercise: The Stackelberg model of Duopoly)

  • 斯塔克尔伯格双寡头模型 (1934):
    • 一个参与者，被称为主导者或领导者 (leader)，首先行动，并且该参与者的选择结果在另一位参与者（跟随者, follower）做出选择之前就已告知对方。
    • 例如，通用汽车公司（General Motors）在美国历史上的某些时期，就曾在汽车行业中扮演了如此主导的角色。

（来源：Game Theory, Second Edition, 2014. Thomas S. Ferguson）

标题：练习：斯塔克尔伯格双寡头模型

  • 厂商1首先选择一个生产数量 q1，其单位成本为 c。
  • 这个数量会被告知厂商2，然后厂商2再选择自己的生产数量 q2，其单位成本同样为 c。
  • 之后，市场的单位价格 P 由以下公式决定： P(Q)={a−Q0if 0≤Q≤aif Q>a=(a−Q)+ 其中 Q=q1+q2，并且 a 是一个常数。
  • 参与者们获得如下支付（利润）： u1(q1,q2)=q1P(q1+q2)−cq1=q1(a−q1−q2)+−cq1 u2(q1,q2)=q2P(q1+q2)−cq2=q2(a−q1−q2)+−cq2 其中单位成本 c<a。

斯塔克尔伯格模型是产业组织理论中一个基石性的模型。它与我们之前讨论的古诺模型（Cournot model）最大的不同在于，它将“同时行动”改为了“序贯行动” (Sequential Moves)，从而引入了先手优势 (First-mover Advantage) 的概念。

1. 与古诺模型的根本区别

  • 古诺模型：两家厂商同时决定产量，谁也不知道对方会生产多少，是一个静态的、猜对手心思的博弈。
  • 斯塔克尔伯格模型：两家厂商有明确的行动顺序。一家是“领导者”（先动），另一家是“跟随者”（后动）。领导者率先公布自己的产量，跟随者在观察到领导者的产量后再决定自己的最优产量。这是一个动态博弈。

2. 如何求解？—— 逆向归纳法 (Backward Induction)

对于这种有先后顺序的博弈，标准的解法是“逆向归纳”，即从后往前推。

第一步：求解跟随者（厂商2）的问题

我们先站在厂商2的角度。此时，厂商1的产量 q1 已经确定，是一个已知的数字。厂商2的目标是选择自己的产量 q2 来最大化自身利润 u2。

q2max u2(q1,q2)=q2(a−q1−q2)−cq2

为了求最大值，我们对 q2 求导并令其为0：

∂q2∂u2=a−q1−2q2−c=0

解出 q2，我们就得到了厂商2的反应函数 (Reaction Function)：

q2∗(q1)=2a−c−q1

这个函数告诉我们：不论领导者厂商1生产多少 (q1)，跟随者厂商2的最优应对策略是什么。

第二步：求解领导者（厂商1）的问题

厂商1非常“聪明”，它完全知道厂商2会如何根据它的 q1 来做出反应。因此，厂商1在做决策时，会把厂商2的反应函数直接代入自己的利润公式中，以此来预测自己选择不同 q1 的最终后果。

厂商1的利润函数变为：

u1(q1)=q1(a−q1−q2∗(q1))−cq1=q1(a−q1−2a−c−q1)−cq1

化简括号内的部分：

u1(q1)=q1(2a−c−q1)−cq1=2aq1−cq1−q12−cq1

厂商1的目标是选择 q1 来最大化这个新的利润函数。我们对 q1 求导并令其为0：

∂q1∂u1=2a−c−2q1=0⟹a−c−2q1=0

解出领导者厂商1的最优产量：

q1∗=2a−c

第三步：得出最终均衡结果

将厂商1的最优产量代入厂商2的反应函数，得到厂商2的产量：

q2∗=2a−c−q1∗=2a−c−(a−c)/2=2(a−c)/2=4a−c

斯塔克尔伯格均衡解为：(领导者产量 q1∗=2a−c， 跟随者产量 q2∗=4a−c)

3. 先手优势

  • 在斯塔克尔伯格均衡中，领导者产量(2a−c)是跟随者(4a−c)的两倍。
  • 我们可以对比一下古诺均衡的结果：在古诺模型中，两家厂商的产量相同，均为 3a−c。
  • 比较可知：q1Stackelberg(2a−c)>qCournot(3a−c)>q2Stackelberg(4a−c)。
  • 这意味着，通过率先行动并承诺一个较高的产量，领导者可以有效地“挤压”跟随者的市场空间，迫使跟随者选择一个较低的产量，从而为自己攫取更高的市场份额和利润。这就是先手优势的体现。
3-2

零和博弈 (Zero-Sum Games)

极小化极大定理 (Minimax Theorem) (约翰·冯·诺伊曼, 1928):

对于每一个具有有限个纯策略的两人零和博弈，都存在一个适用于各方参与者的混合策略和一个价值 V，使得：

  • 给定参与者2的策略，参与者1可能获得的最佳支付为 V。
  • 给定参与者1的策略，参与者2可能获得的最佳支付为 -V。

策略存在的部分是纳什定理的一个特例，也是其先驱。

这基本上是说，参与者1可以保证自己获得至少 V 的支付，而参与者2可以保证自己获得至少 -V 的支付。如果双方都采取最优策略，这恰好就是他们将得到的结果。

它之所以被称为“极小化极大 (minimax)”，是因为参与者是通过一种试图最小化 (minimize) 对手可能获得的最大 (maximum) 支付的策略来获得这个价值的。我们稍后会再回到这一点。

定义：价值 V 被称为该博弈的价值 (value)（或回报、支付）。

例如：石头剪刀布的价值是0；假设参与者2采取最优策略（以1/3的概率出每一种手势），参与者1能期望获得的最好结果是0的支付。

这张幻灯片介绍了博弈论的奠基性概念之一——两人零和博弈，以及该领域第一个里程碑式的定理——冯·诺伊曼的极小化极大定理。

1. 什么是零和博弈？

首先，零和博弈指的是在一个博弈中，所有参与者的收益（或亏损）加起来永远等于零。这意味着，一方的所得，必然是另一方的所失。这是一个纯粹冲突、完全竞争的模型，没有任何合作共赢的可能。经典的例子包括：

  • 棋类游戏：如象棋、围棋，一方赢就是另一方输。
  • 石头剪刀布：一方赢一分，另一方就输一分。
  • 竞技体育：大多数只有两方对阵的比赛。

2. “极小化极大”定理的通俗解释

这个定理解决了一个核心问题：在这样你死我活的纯冲突中，“理性”的策略是什么？冯·诺伊曼给出了一个天才的答案，其思考逻辑如下：

从参与者1（P1）的角度（最大化最小值, Maximin）：

  1. P1必须假设P2是完全理性的，并且会尽一切努力损害P1的利益。
  2. P1会思考：“对于我可能采取的每一个策略，P2都会用对我最不利的方式来回应。我先列出每一种策略下，我最坏会得到什么结果（我的最小收益）。”
  3. “然后，在所有这些‘最坏结果’中，我选择那个能让我得到最好结果的策略。”
  4. 这个过程，就是最大化自己的最小保证收益 (Maximize a minimum payoff)，简称 Maximin。

从参与者2（P2）的角度（极小化极大, Minimax）：

  1. P2同样假设P1会尽全力损害自己。
  2. P2会思考：“对于P1的每一个策略，我最坏会损失多少（即P1能获得的最大收益）？”
  3. “然后，我选择一个策略，能让P1可能获得的最大收益变得最小。”
  4. 这个过程，就是最小化自己的最大可能损失 (Minimize a maximum loss)，简称 Minimax。

定理的“奇迹”：冯·诺伊曼证明，对于任何两人零和博弈，P1通过“最大化最小值”策略能保证得到的收益 V，与P2通过“极小化极大”策略能保证让P1得到的收益 V，是完全同一个数值！这个 V 就是该博弈的“价值”。

这意味着，这类纯冲突博弈存在一个绝对理性的、稳定的解。双方的最佳策略将会在这个点上交汇。

3. 混合策略的重要性

这个定理的成立，往往需要混合策略的引入，即以一定的概率随机地选择不同的行动。

  • 以“石头剪刀布”为例，如果你只出“石头”（一个纯策略），对手会立刻发现并一直出“布”来打败你。
  • 你唯一能保证自己不输的策略，就是完全随机地出招（石头、剪刀、布各1/3概率）。
  • 当你的对手也采取这种最优的混合策略时，你期望的平均收益就是0。因此，这个博弈的价值 V=0。
3-3

计算纳什均衡：两人零和博弈 (Computing Nash Equilibria: 2-person, Zero-Sum Games)

  • 这个博弈没有纯策略纳什均衡。
  • 根据纳什定理，它必然拥有一个混合策略纳什均衡。
  • 我们该如何找到它呢？

(注：这是一个两人零和博弈)

这张幻灯片提出了一个核心问题：对于一个没有纯策略均衡的博弈，我们如何具体计算出它的混合策略纳什均衡？

下面是详细的计算步骤：

第一步：验证不存在纯策略纳什均衡

我们可以通过“划线法”或“最优反应法”来快速验证。

  1. 如果参与者2选择“列1”，参与者1的最优选择是“行2”（因为收益 +3 > -2）。
  2. 如果参与者2选择“列2”，参与者1的最优选择是“行1”（因为收益 +3 > -4）。
  3. 如果参与者1选择“行1”，参与者2的最优选择是“列1”（因为收益 +2 > -3）。
  4. 如果参与者1选择“行2”，参与者2的最优选择是“列2”（因为收益 +4 > -3）。

我们发现，没有任何一个单元格是双方共同的最优选择，因此该博弈确实没有纯策略纳什均衡。

第二步：设定混合策略

在混合策略均衡中，核心思想是“无差异原则” (Indifference Principle)：每个参与者选择自己的混合策略（即概率），目的是让对方在自己的几个纯策略选择之间感到无所谓/无差异（即期望收益完全相等）。

  • 我们假设参与者1以概率 p 选择“行1”，以概率 (1-p) 选择“行2”。
  • 我们假设参与者2以概率 q 选择“列1”，以概率 (1-q) 选择“列2”。

第三步：计算参与者1的混合策略 p

为了让参与者2感到无差异，参与者2选择“列1”的期望收益必须等于他选择“列2”的期望收益。

  • 参与者2选择“列1”的期望收益 E(列1) = p(+2)+(1−p)(−3)
  • 参与者2选择“列2”的期望收益 E(列2) = p(−3)+(1−p)(+4)

令 E(列1) = E(列2):

可得p=7/12

所以，参与者1的最优策略是：以 7/12 的概率选择“行1”，以 5/12 的概率选择“行2”。

第四步：计算参与者2的混合策略 q

同样，为了让参与者1感到无差异，参与者1选择“行1”的期望收益必须等于他选择“行2”的期望收益。

  • 参与者1选择“行1”的期望收益 E(行1) = q(−2)+(1−q)(+3)
  • 参与者1选择“行2”的期望收益 E(行2) = q(+3)+(1−q)(−4)

令 E(行1) = E(行2):

q=7/12

所以，参与者2的最优策略是：以 7/12 的概率选择“列1”，以 5/12 的概率选择“列2”。

第五步：结论与博弈的价值

  1. 混合策略纳什均衡：该博弈的唯一纳什均衡是：参与者1采取混合策略 ( 7/12 ,5/12)，参与者2采取混合策略 (7/12 ,5/12)。

  2. 博弈的价值 (Value of the Game)：在均衡状态下，参与者1的期望收益是多少？我们可以把 q = 7/12 代入 E(行1) 的公式中计算：

    E(P1) = 1/12

    因此，这个博弈对参与者1的价值是 +1/12，对参与者2的价值是 -1/12。这意味着，如果双方都采取最优的随机策略，长期来看，参与者1平均每次能赢1/12。

为什么目的是让对方在自己的几个纯策略选择之间感到无所谓/无差异？

简单来说，让对方“无差异”并不是我们的最终目的，而是我们为了实现自身利益最大化，所必须达到的一个“结果”或“条件”。

这是一种非常高明的策略思想，我们可以从三个层面来理解它：

1. 核心思想：消除对方的确定性最优解

在一个博弈中，如果你采取的策略让你的对手有一个明确的、唯一的“最优选择”，那你就输了一半。因为：

  1. 一个理性的对手，一定会采取那个对他来说最优的选择。
  2. 这样一来，对手的行动就变得完全可以预测了。
  3. 一旦对手的行动是可预测的，你就可以反过来调整自己的策略，去专门“克制”他那个可预测的行动，从而让自己获利更多。
  4. 但这就产生了一个矛盾：如果你能调整策略获利更多，说明你最初的策略就不是最优的。

这个矛盾循环说明，一个稳定的均衡状态，不应该让任何一方有“唯一的、确定的”最优解。而要做到这一点，你唯一的方法就是调整自己的策略组合（即概率 p），直到你的对手觉得“选A或选B，反正期望收益都一样，我无所谓了”。

当你让对手“无所谓”时，你就消除了他行动的确定性，他才不得不也用一种随机的方式来对抗你。这才是对自己最有利的局面。

2. 反向思考：如果不让对方无差异会怎样？

我们用上一张幻灯片的例子来思考：

  • 你的策略是：以概率 p 出“行1”，概率 (1-p) 出“行2”。
  • 假设你选择的 p 没有让对手无差异，而是让对手觉得“出‘列1’比出‘列2’的期望收益更高”。

接下来会发生什么？

  1. 对手的反应：理性的对手会想：“既然出‘列1’更好，我为什么还要费事去随机出‘列2’呢？” 于是，他会100%地出“列1”。他的策略就不再是混合策略了。
  2. 你的反应：你看到对手只会出“列1”，那你还会坚持你原来的概率 p 吗？当然不会！你会看支付矩阵的“列1”那一栏，发现你出“行1”收益是-2，出“行2”收益是+3。你显然会100%地出“行2”来应对他。

结论：你最初那个让对手“有差异”的策略 p，最终导致了你自己也想改变策略。这就说明，那个初始状态根本不稳定，因此不是纳什均衡。

唯一的稳定状态，就是你选择的概率 p，正好让对手觉得“出‘列1’和出‘列2’没差”，他没有理由偏向任何一方，所以他才愿意继续以一定概率 q 来混合他的策略。

3. 一个直观的例子：点球大战

想象一下足球比赛中的点球大战：

  • 你的角色：踢球手。你可以选择踢左边或右边。
  • 对手的角色：守门员。他可以选择扑左边或右边。

你的目标是什么？是让守门员对于“扑左还是扑右”感到无差异。

  • 为什么？ 如果你总喜欢踢左边（比如70%的概率），守门员就会发现这个规律，然后更倾向于扑向左边，这样你的进球率就会下降。你的行为变得“可预测”了。
  • 你的最优策略：你必须调整自己踢左边和右边的概率（比如各50%），使得守门员觉得“反正我扑左扑右，猜对的概率都一样，期望丢球数也一样，我无所谓了，只能瞎猜”。
  • 最终结果：只有当你成功地让守门员陷入“无所谓”的境地时，他才无法预测你的行动，你才能最大化你的进球率。

总结：

在混合策略中，让对方“无所谓”，并不是一种善意的妥协，而是一种最顶级的进攻策略。它本质上是：

  • 为了防止自己被预测和被针对。
  • 为了迫使对方也必须采取不确定的、随机的策略来应对。
  • 为了最终能在一个充满不确定性的稳定均衡中，保障自己获得最大化的期望收益。

所以，“让对方无差异”是你实现最优策略的必要条件，而不是你的目的本身。

极大极小博弈

3-4

这张幻灯片用一个政治竞选的例子，构建了一个经典的两人零和博弈。它给出了问题设定，但没有给出解。核心任务就是根据这些信息，计算出这场博弈的均衡解以及博弈的价值。

第一步：检查是否存在纯策略均衡

我们首先检查是否存在一个稳定的单元格，使得任何一方都不想单方面改变策略。

  1. 如果列玩家（候选人2）选择“道德”，行玩家（候选人1）会选择“经济”（因为收益3 > -2）。
  2. 如果列玩家选择“减税”，行玩家会选择“社会”（因为收益1 > -1）。
  3. 如果行玩家选择“经济”，列玩家会选择“减税”（因为收益1 > -3）。
  4. 如果行玩家选择“社会”，列玩家会选择“道德”（因为收益2 > -1）。

我们发现，不存在任何一个稳定的策略组合。例如，在（经济, 道德）这个组合，行玩家很满意，但列玩家会想换到“减税”策略以获得更好的收益。因此，该博弈没有纯策略纳什均衡。我们必须寻找混合策略均衡。

第二步：计算混合策略纳什均衡

我们将使用无差异原则来求解。

  • 设行玩家（候选人1）以概率 x 选择“经济”，以概率 (1-x) 选择“社会”。
  • 设列玩家（候选人2）以概率 y 选择“道德”，以概率 (1-y) 选择“减税”。

A. 计算行玩家的策略 x

行玩家需要选择一个概率 x，使得列玩家对于选择“道德”还是“减税”感到无差异（期望收益相等）。

  • 列玩家选择“道德”的期望收益 = x⋅(−3)+(1−x)⋅(2)
  • 列玩家选择“减税”的期望收益 = x⋅(1)+(1−x)⋅(−1)

令二者相等：

$$-3x + 2 - 2x =  - 1 + x$$$$2 - 5x = 2x - 1$$$$3 = 7x$$x=73

所以，候选人1的最优策略是：以 3/7 的概率主打“经济”议题，以 4/7 的概率主打“社会”议题。

B. 计算列玩家的策略 y

同样，列玩家需要选择一个概率 y，使得行玩家对于选择“经济”还是“社会”感到无差异。

  • 行玩家选择“经济”的期望收益 = y⋅(3)+(1−y)⋅(−1)
  • 行玩家选择“社会”的期望收益 = y⋅(−2)+(1−y)⋅(1)

令二者相等：

3y − 1 + y = −2y + 1 − y4y − 1 = 1 − 3y7y = 2y=72

所以，候选人2的最优策略是：以 2/7 的概率主打“道德”议题，以 5/7 的概率主打“减税”议题。

第三步：计算博弈的价值

博弈的价值（Value）就是指在双方都采取最优策略时，行玩家的期望收益。我们可以将 y = 2/7 代入行玩家的任一期望收益公式：

V=3y−1+y=4y−1=4⋅(72)−1=78−1=71

结论

  • 纳什均衡：该博弈的唯一纳什均衡是，候选人1采取混合策略 (73,74)，候选人2采取混合策略 (72,75)。这意味着两位候选人都应该以特定的概率随机选择自己的竞选焦点，让对手无法预测。
  • 博弈价值：该博弈对行玩家（候选人1）的价值是 +1/7。在竞选这个议题上，如果双方都采取最理性的策略，候选人1平均可以期望净赚 1/7 百万（约14万）的选民。这表明在这个特定的战略矩阵中，候选人1拥有微弱的优势。
3-5

备注：下面这段话有提到“这代表了列玩家的理性反应。由于这是一个零和博弈，列玩家的目标是让行玩家的收益尽可能小。”，结合上面一张PPT的最后一个恒等式，可知，由于这是零和博弈，行玩家收益最少等价于列玩家收益最大。

这张幻灯片从一个更形式化、更根本的角度，展示了作为“领导者”（被迫先宣布策略的一方）应该如何思考，并将这个问题转化为了一个标准的数学优化问题。最终，它揭示了一个关于零和博弈的深刻结论。

1. Maximin 公式解读：“在最坏的情况里做到最好”

幻灯片给出的第一个公式

maxmin(3x1−2x2,−x1+x2)

是“最大化最小值 (Maximin)”思想的完美数学体现。我们来拆解它：

  • 内部的两个表达式：
    • 3x1−2x2：这是当列玩家选择“道德”时，行玩家的期望收益。
    • −x1+x2：这是当列玩家选择“减税”时，行玩家的期望收益。
  • min(…) 部分：这代表了列玩家的理性反应。由于这是一个零和博弈，列玩家的目标是让行玩家的收益尽可能小。所以，当行玩家宣布了一个策略 (x1,x2) 后，列玩家会审视这两个可能的收益，并选择那个能让行玩家收益更小 (min) 的策略来应对。这代表了行玩家在宣布策略 (x1,x2) 后，所能得到的最坏结果保证。
  • max(…) 部分：这代表了行玩家的决策。行玩家知道对手会这样针对他。所以，他在选择自己的策略 (x1,x2) 时，目标就是让这个“最坏的结果保证”变得尽可能好。也就是要最大化 (max) 那个最小的收益。

这整个公式的逻辑就是：“我（行玩家）要选择一个策略 (x1,x2)，来最大化‘在我宣布这个策略后，对手尽最大努力打压我，我能得到的那个保底收益’”。

2. 线性规划的转换：从博弈论到标准数学优化

Max-min 问题在数学上直接求解不方便，但可以非常巧妙地转化为一个标准的线性规划 (Linear Programming, LP) 问题。

  • 我们引入一个新变量 z，让它代表那个“保底收益”。
  • 我们的目标是 最大化 z。
  • 约束条件是什么？z 必须小于等于所有可能的结果。所以：
    • z≤3x1−2x2 (保底收益不能超过对手选“道德”时我的收益)
    • z≤−x1+x2 (保底收益不能超过对手选“减税”时我的收益)
  • 再加上概率本身的基本约束 x1+x2=1 和 x1,x2≥0。

这样，我们就把一个博弈问题，变成了一个可以用标准算法（如单纯形法）求解的数学问题。

3. 最终结论：结果与之前完全相同！

幻灯片最后指出，解这个线性规划得到的结果是 x1=3/7，x2=4/7，并且最优的保底收益 z=1/7。

这正是我们之前用“无差异原则”为同时博弈计算出的纳什均衡解和博弈价值 V！

为什么会这样？

这并非巧合，而是冯·诺伊曼极小化极大定理 (Minimax Theorem) 的直接体现。该定理的核心是：

Maximin=Minimax

  • 我们这张幻灯片求解的“领导者-跟随者”问题，正是行玩家的 Maximin（最大化最小值） 问题。
  • 我们之前求解的“同时博弈”问题，得到的是Minimax（极小化极大值） 均衡解。

这个定理保证了，在任何两人零和博弈中，这两个值是相等的。这意味着，在两人零和博弈中，不存在先手优势或后手优势。你提前公布策略，虽然给了对方信息，但你也可以利用这一点来选择一个最稳妥的策略；对方虽然能看到你的策略，但也只能在你设定的框架内做出反应。最终双方的力量会完美抵消，达到同一个均衡结果。

纳什均衡的线性规划解法

3-6

这张幻灯片介绍了一个在线性规划乃至整个优化理论中，都极具美感和威力的核心概念——对偶性。它揭示了每个优化问题都存在一个“影子问题”或“镜像问题”，而理解这个镜像能为我们提供关于原问题全新的、深刻的洞察。

1. 什么是对偶性？一个直观的例子

要理解对偶，与其陷入复杂的数学转换，不如看一个经济学例子：

  • 原问题 (Primal Problem)：
    • 想象你是一家工厂的老板，你要决定生产多少桌子和椅子，来最大化你的总利润。
    • 你面临一些约束：你拥有的木材、劳动力、设备时间都是有限的。
    • 这就是一个典型的线性规划问题：最大化一个目标（利润），同时满足一系列约束（资源）。
  • 对偶问题 (Dual Problem)：
    • 现在，想象一个商人想来收购你所有的资源（木材、劳动力、设备）。他想最小化他的收购总成本。
    • 但他面临一个约束：他为每种资源开出的“影子价格”组合，必须能让你觉得“卖掉资源比我自己生产产品更划算”。例如，生产一张桌子需要消耗的资源，他打包收购的价格，必须不能低于你自己生产这张桌子能获得的利润。
    • 这个商人的问题——在一定约束下最小化成本——就是你那个最大化利润问题的“对偶问题”。

2. 对偶性的“魔力”：原问题与对偶问题的关系

对偶理论中有两个核心定理，它们揭示了原问题和对偶问题之间的奇妙关系：

  1. 弱对偶定理 (Weak Duality)：对偶问题的最优解，永远是原问题最优解的一个“界限”。在上面的例子里，就是说：商人收购资源的最小成本，必然大于等于工厂老板自己生产的最大利润。这很直观，因为如果收购成本低于你的利润，你肯定不会卖。

  2. 强对偶定理 (Strong Duality)：在绝大多数情况下，这个“大于等于”实际上是“完全等于”！也就是说：

    工厂能实现的最大利润=商人收购资源的最小成本

    这是一个非常深刻的结论。它意味着，你资源的内在价值，恰好等于你能用它们创造的最大利润。对偶问题中的变量（资源的“影子价格”），精确地量化了每一种稀缺资源的边际价值。

3. 对偶性与“零和博弈”的惊人联系

现在，我们可以把这个概念带回我们之前讨论的博弈论了。这正是引入对偶概念的关键所在。

  • 在前几张幻灯片中，我们把行玩家的问题构建成了一个线性规划：最大化他的保底收益 V。这可以看作是我们的原问题 (Primal)。
  • 那么，列玩家的问题是什么？列玩家的目标是最小化行玩家能获得的最大收益 W。我们同样可以把列玩家的这个问题也构建成一个线性规划。
  • 最关键的结论是：列玩家的“最小化极大值”线性规划问题，恰好就是行玩家“最大化最小值”线性规划问题的对偶问题！

因此，线性规划的“强对偶定理”（最大值 = 最小值），在零和博弈的语境下，就直接变成了冯·诺伊曼的“极小化极大定理”！

max(行玩家的保底收益)=min(列玩家的最大损失)Maximin=Minimax

总结：对偶性不仅是线性规划的强大工具，它还为博弈论的基石——极小化极大定理——提供了最坚实的数学证明。它优美地揭示了，一个参与者的最大化问题和其对手的最小化问题，实际上是同一个数学结构的两个不同侧面，如同一枚硬币的两面，其价值必然相等。

3-7

线性规划对偶性实例。

3-8

弱对偶性和强对偶性

线性互补问题

3-9

标题：计算两人一般和博弈的纳什均衡 (Computing Nash equilibria of two-player, general-sum games)

  • 不幸的是，寻找一个两人一般和博弈 (general-sum game) 的纳什均衡，无法被构建成一个线性规划问题。
    • — 两名参与者的利益不再是*完全*对立的 (completely opposed)。
    • — 然而，我们仍然可以将我们的问题表述为某种优化问题。

这张幻灯片标志着一个重要的转折点。从“零和博弈”进入了更普遍、也更复杂的“一般和博弈”（或称“非零和博弈”）的世界。幻灯片的核心信息是：之前强大而高效的线性规划（LP）工具，在这里失效了。

1. 什么是一般和博弈？

一般和博弈指的是，在任何一个结果下，所有参与者的收益之和不一定为零。这意味着博弈的结果可以是双赢、双输，或者一方赢多、一方输少。参与者的关系不再是“你死我活”的纯粹冲突，而是冲突与合作并存。

  • 经典例子1：囚徒困境

    如果两个囚犯都背叛对方，他们可能各判5年（总收益-10）。如果他们都保持沉默，可能各判1年（总收益-2）。这是一个双输的“负和”博弈。

  • 经典例子2：性别大战 (Battle of the Sexes)

    一对情侣都想待在一起（合作），但一人想看歌剧，另一人想看球赛（冲突）。如果他们去同一个地方，双方都能获得高收益（比如（5,2）或（2,5）），总收益为7。如果去不同地方，则两人都很不开心（0,0），总收益为0。这是一个“正和”博弈。

2. 为什么线性规划会失效？—— 对偶性的崩塌

这是理解这张幻灯片最关键的地方。线性规划之所以能在零和博弈中大显神威，是因为其背后优美的“对偶性”，而这种对偶性源于双方利益的完全对立。

  • 在零和博弈中：
    • 行玩家的目标是：最大化自己的收益 u₁。
    • 列玩家的目标是：最大化自己的收益 u₂。
    • 由于 u₂ = -u₁，所以列玩家“最大化u₂”就等价于“最小化u₁”。
    • 因此，行玩家的“最大化最小值 (Maximin)”问题和列玩家的“最小化极大值 (Minimax)”问题，形成了一对完美的数学对偶。它们就像一枚硬币的两面，可以用同一个线性规划框架来解决。
  • 在一般和博弈中：
    • u₂ 不再等于 -u₁。
    • 列玩家的目标——最大化他自己的 u₂——与行玩家的收益 u₁ 没有直接的、负相关的关系。
    • 列玩家不再是处心积虑地要让行玩家的收益最小化，他只关心自己的收益。
    • 这样一来，那种“我之所得即你之所失”的完美对偶关系就彻底崩塌了。我们无法再构建出一个单一的线性规划问题来同时描述双方的决策并找到那个共同的解。

3. 那问题变成了什么？

虽然不能用线性规划，但寻找纳什均衡依然是一个数学优化问题，只是变得更复杂了。

  • 寻找两人一般和博弈的纳什均衡，在数学上等价于求解一个线性互补问题 (Linear Complementarity Problem, LCP)。这是一个比线性规划更复杂的数学结构。
  • 从计算复杂性的角度看，求解两人零和博弈是“容易”的（属于 P 问题），而求解两人一般和博弈则被证明是PPAD-完全 (PPAD-complete) 问题。这通常被认为是一个“更难”的计算等级，意味着找到解需要更复杂的算法，计算效率也更低。

总结：从“零和”到“一般和”的转变，是博弈论中一次巨大的复杂性飞跃。它让我们失去了线性规划这个简洁高效的工具，迫使我们进入一个更困难的计算领域。这也反过来凸显了两人零和博弈及其“极小化极大定理”在理论上的简洁与优美。

3-10

标题：计算两人一般和博弈的纳什均衡

  • 我们首先考虑一个内部的 (inner) 或完全混合的 (totally mixed) 纳什均衡 (X∗,Y∗)，即对于所有的 i 和 j，都有 xi∗>0 以及 yj∗>0（所有的纯策略都以正概率被使用）。

  • 让 ai 表示行玩家的支付矩阵A的各行，让 bj 表示列玩家的支付矩阵B的各列。

  • 利用“在一个纳什均衡策略的支持集(support)中，所有纯策略都产生相同的支付”这一事实，并且该支付大于或等于支持集之外的策略的支付，我们得到：

    • aiy∗=aky∗,i,k=1,2,…,m.

    • (x∗)Tbj=(x∗)Tbk,j,k=1,2,…,n.

      (注：此处公式经过订正以符合标准表达)

      (绿色文字) 假设每个纯策略都以正概率被使用。

  • 上述构成了一个可以被高效求解的线性方程组。

下图内容

  • 然而，“每个策略都以正概率被使用”的假设是有限制性的。大多数博弈并不拥有完全混合的纳什均衡；对于它们而言：

  • 我们计算一个有限两人博弈的所有纳什均衡：

    一个混合策略组合 (x∗,y∗) 是一个具有支持集 S1,S2 的纳什均衡，当且仅当：

    • u=aiy∗,∀i∈S1 （对于支持集内的策略i，收益都等于均衡收益u）
    • u≥aiy∗,∀i∈/S1 （对于支持集外的策略i，收益不高于u）
    • v=(x∗)Tbj,∀j∈S2 （对于支持集内的策略j，收益都等于均衡收益v）
    • v≥(x∗)Tbj,∀j∈/S2 （对于支持集外的策略j，收益不高于v）
    • xi∗=0,∀i∈/S1, yj∗=0,∀j∈/S2 （u, v 是NE中的收益值）

  • 要让上述过程可行，我们需要找到正确的支持集 (supports)。我们需要遍历所有可能的支持集组合。由于存在 2n+2m 种不同的支持集，这会导致算法具有指数级的复杂度。

  • 备注 (Remark)：计算有限博弈的纳什均衡的计算复杂度，就在于找到正确的支持集。

这两张幻灯片讲述了一个关于“求解一般和博弈”的完整故事：从一个理想化的、简单的特例，到一个普遍的、困难的现实。

1. 理想情况：完全混合均衡（上图）

幻灯片的上半部分描绘了一种“完美”的均衡状态，即完全混合均衡。在这种均衡里，每一个参与者都认为对手的所有可选策略都值得提防，因此自己的最优策略是给自己的每一个选项都分配一个大于零的概率。

  • 为什么这种情况简单？

    因为它使得“无差异原则”可以应用到所有策略上。为了让对手混合他的所有策略，你必须让你的对手在选择他的任何一个策略时，期望收益都完全相等。

  • 如何求解？

    这就产生了一个完整的线性方程组（m-1个关于行玩家收益的等式，n-1个关于列玩家收益的等式，再加上两个概率和为1的等式）。这是一个标准的、可以用我们熟悉的方法高效求解的数学问题。

然而，这种所有策略都被用上的“雨露均沾”式的均衡，在现实中非常罕见。

2. 现实情况：寻找“支持集”（下图）

幻灯片的下半部分指出了残酷的现实：在绝大多数博弈中，通常都会有一些策略是“劣势策略”或“糟糕的选项”，一个理性的玩家是永远不会使用它们的（即使用概率为0）。

  • 支持集 (Support)：在一个混合策略中，那些真正以正概率被使用的纯策略的集合，被称为这个混合策略的“支持集”。
  • 核心困难：求解的关键困难在于，我们事先并不知道最终的均衡解中，到底哪些策略会是“优势策略”（在支持集里），哪些是“劣势策略”（在支持集外）。

这就引出了一个计算上的巨大难题，我喜欢称之为“寻找嫌疑人”的困境：

  • 无差异原则就像一个完美的“审讯工具”，只要你把正确的“嫌疑人”（支持集里的策略）找来，它就能告诉你每个人的详细“作案手法”（混合策略的精确概率）。
  • 但问题是，你不知道谁是真正的“嫌疑人”。你面对着所有可能的策略，不知道该把哪些策略纳入“无差异”的审讯中。

3. “暴力搜索”算法及其指数级复杂度

理论上，我们可以用一种“暴力”的方法来找到所有均衡：

  1. 猜测：我们先猜一个可能的支持集组合。例如，“我猜行玩家只会用策略1和3，而列玩家只会用策略2和4”。
  2. 求解：基于这个猜测，我们建立一个只包含这些策略的线性方程组（即只让这些策略满足无差异原则）并求解。
  3. 验证：检查解出的结果是否是一个合法的纳什均衡。这包括两部分：
    • 解出的概率值是否都在0和1之间？
    • 对于那些我们没猜的“局外”策略，它们的期望收益是否真的不优于我们算出的均衡收益？（这是最关键的验证，确保没人想把局外策略拉进局内）。
  4. 重复：如果验证失败，就回到第一步，换一种支持集的猜测，然后重复整个过程，直到遍历完所有可能的支持集组合。

这个方法的致命缺陷在于，支持集的组合数量是指数级增长的。如果一个博弈双方各有20个策略，那么可能的支持集组合数量会是一个天文数字。这就是幻灯片所说的“指数级复杂度”。

总结：寻找一般和博弈的纳什均衡，其计算上的困难不在于解方程，而在于找到应该用哪些策略来列方程。这个“寻找正确支持集”的组合搜索过程，是该问题计算复杂度（PPAD-complete）的根源，也使其与可以通过线性规划轻松求解的两人零和博弈产生了本质的区别。

多智能体强化学习

7.1 多智能体强化学习介绍及基本概念

7-1

这张幻灯片指出了从单智能体学习（比如我们熟知的AlphaGo下围棋的早期版本）迈向多智能体学习（比如王者荣耀或星际争霸中的AI）时，所遇到的一个根本性的、质的困难。

1. 核心困难：移动的靶心 (The Moving-Target Problem)

  • 在单智能体学习中：环境是静止的或有固定规律的。一个智能体（比如一个机器人）学习走路，它只需要掌握如何应对地板、墙壁等物理规律即可。这个“游戏规则”是不会变的。
  • 在多智能体学习中：情况发生了根本变化。对于任何一个智能体（我们称之为“我”）来说，其他的智能体也是环境的一部分。但问题是，这些“其他的智能体”本身也在学习、在进化、在改变他们的策略。
    • 一个生动的例子：你学习如何开车上班最快。如果只有你一个人在学习，而其他人的路线每天都固定不变，这就是一个简单的单智能体问题。但现实是，成千上万的司机（其他智能体）每天也都在尝试新的路线来优化他们自己的通勤时间。你今天发现的“最优路线”，明天可能因为有几百个和你一样的人也发现了它而变得极度拥堵。
    • 你试图瞄准的那个“最优策略”的靶心，因为他人的学习而不断地移动。这就是多智能体学习的核心困难，学术上称为“环境的非平稳性” (Non-stationarity)。

2. 为什么简单的Q学习会失效？

标准的单智能体强化学习算法（如Q学习）之所以能成功，是因为它们依赖于一个基本假设：马尔可夫决策过程 (MDP)，即环境是平稳的。这意味着，在同一个状态（State）下，采取同一个动作（Action），得到的奖励（Reward）和状态转移的概率应该是基本一致的。

但在多智能体环境中，这个假设被彻底打破了：

  • 今天：在路口（状态S），你选择直行（动作A），因为其他人都选择了右转，所以一路畅通，你获得了很高的奖励。你的Q表格会更新，认为(S, A)是个好选择。
  • 明天：在同一个路口（状态S），你根据昨天的经验再次选择直行（动作A）。但昨天和你一样选择直行的其他智能体也获得了高奖励，所以今天他们也选择直行。结果造成了交通堵塞，你得到了一个很低的奖励。你的Q表格又必须更新，认为(S, A)是个坏选择。

你的Q值会这样剧烈地来回震荡，可能永远无法收敛到一个稳定的策略，因为一个动作的“好”与“坏”不再是固定的，而是完全取决于其他智能体当前正在执行的策略。

3. 与博弈论的联系

这个学习过程中的“不稳定”问题，正是我们在前面博弈论部分看到的“均衡”问题的动态体现。

  • 多智能体学习的目标，往往就是让这群智能体通过学习和试错，最终能够收敛到整个博弈的纳什均衡。
  • 幻灯片中的螺旋图可以这样理解：中心点是博弈的纳什均衡点。这条螺旋线代表了所有智能体的联合策略随着时间演变的轨迹。如果学习算法设计得好（例如，在势博弈中），这条轨迹就会像图中一样稳定地收敛到中心。
  • 如果算法设计不当或者博弈本身就很“恶劣”（比如“石头剪刀布”），那么学习过程可能永远无法收敛，只会在策略空间中不停地“绕圈子”。

总结：多智能体学习的困难在于，每个智能体的学习过程都会改变其他智能体的学习环境，形成一个复杂且动态的“移动靶心”问题。简单地将单智能体算法直接套用，会因环境的“非平稳性”而失效。因此，现代多智能体学习研究的核心，就是设计出能够在这种动态博弈中稳定地学习、并最终收敛到纳什均衡等合理状态的算法。

7-2

我们可以通过两个关键问题来区分这些模型：

  1. 有几个决策者（智能体）？ 一个还是多个？
  2. 有多少种情况（状态）？ 一种还是多种？

1. 马尔可夫决策过程 (MDPs): 单人探索世界

  • 特征：一个智能体，多个状态。
  • 核心问题：一个独立的决策者，在一个可以变化的环境中，如何学习一系列的动作以最大化其长期回报。
  • 通俗例子：一个机器人学习走迷宫。机器人是唯一的智能体，迷宫中不同的位置就是不同的状态。机器人需要学习在每个位置（状态）下，应该朝哪个方向走（动作），才能最快找到出口（最大化回报）。
  • 地位：这是现代单智能体强化学习 (Single-Agent Reinforcement Learning) 的数学基石。我们熟知的AlphaGo下棋，本质上也可以看作是在一个极度复杂的MDP中寻找最优策略。

2. 重复博弈 (Repeated Games): 多人重复同一场游戏

  • 特征：多个智能体，一个状态。
  • 核心问题：多个决策者，反复地玩同一个博弈。
  • 通俗例子：两家寡头公司，每个月都要决定自己的产品定价。每个月的定价博弈，其本身的收益矩阵都是一样的，所以可以看作是单一状态。但因为博弈是重复的，今天的决策会影响声誉，从而影响对手明天的决策。这就引入了如“以牙还牙 (Tit-for-Tat)”这样的动态策略。我们之前讨论的各种矩阵博弈（如囚徒困境、零和博弈），如果将它们连续玩很多次，就构成了重复博弈。

3. 随机博弈 / 马尔可夫博弈 (Stochastic/Markov Games): 多人探索动态世界

  • 特征：多个智能体，多个状态。
  • 核心问题：多个决策者在一个动态变化的环境中共同决策，他们的联合行动会共同决定环境如何进入下一个状态。
  • 通俗例子：一场足球比赛。场上有多个智能体（双方队员）。球和所有队员在场上的位置，共同构成了一个状态。当大家做出动作（跑动、传球、射门）后，场上的局面会变成一个新的状态。在每个不同的状态下，球员们面临的“局部博弈”也是不同的。
  • 地位：这是最普适、最复杂的模型，它构成了多智能体强化学习 (Multi-Agent Reinforcement Learning, MARL) 的理论基础。

总结与联系：

这张图清晰地告诉我们，随机博弈是“集大成者”，它统一了另外两个模型：

  • 当随机博弈的智能体数量减少到1个时，它就退化成了MDP。
  • 当随机博弈的状态数量减少到1个时，它就退化成了重复博弈。

这与我们上一张幻灯片讨论的“多智能体学习的困难”完美地衔接了起来。我们所说的“环境的非平稳性”，正是因为我们身处随机博弈的框架中：对于“我”这个智能体而言，环境之所以看起来在不停变化，是因为环境的下一个状态不仅取决于我的行动，还取决于其他所有智能体的行动，而他们本身也在学习和改变。

7-3

这张幻灯片提出了一个非常经典的任务：为任意一个 2x2 零和博弈找到通用的解法，即用矩阵中的参数 a,b,c,d 来表达博弈的价值和双方的最优策略。

我们将遵循幻灯片给出的两步计划来完成这个推导。

步骤一：检验纯策略均衡（鞍点）

一个纯策略纳什均衡（在零和博弈中也称为“鞍点”）存在的条件是：某一个收益值，既是其所在行的最小值，又是其所在列的最大值。

我们可以通过比较行玩家的“最大化最小值（Maximin）”和列玩家的“最小化极大值（Minimax）”来判断：

  • 行玩家的保底收益（最大最小值）: max(min(a,b),min(d,c))
  • 列玩家的保底收益（最小极大值）: min(max(a,d),max(b,c))

如果这两个值相等，则存在纯策略均衡，该值就是博弈的价值。例如，如果 a <= b 并且 a >= d，那么 a 就是一个鞍点，（行1，列1）就是纯策略纳什均衡。

步骤二：求解混合策略均衡（假设不存在鞍点）

如果不存在鞍点，那么双方的最优策略必然是混合策略。我们将使用无差异原则来求解。

  • 策略设定:

    • 行玩家以概率 p 选择“行1”，以概率 (1-p) 选择“行2”。
    • 列玩家以概率 q 选择“列1”，以概率 (1-q) 选择“列2”。

  • 推导行玩家的策略 p:

    行玩家选择 p 的目的是让列玩家在“列1”和“列2”之间感到无差异。

    • 列玩家选择“列1”的期望收益（注意，要用列玩家的收益矩阵-A）：p(−a)+(1−p)(−d)

    • 列玩家选择“列2”的期望收益：p(−b)+(1−p)(−c)

      令二者相等：

      −ap − d(1 − p) = −bp − c(1 − p)−ap − d + dp = −bp − c + cpd − c = p(a − d − b + c) = p((a + c) − (b + d))

      解得行玩家的最优概率 p：

      p∗=(a+c)−(b+d)d−c

  • 推导列玩家的策略 q:

    列玩家选择 q 的目的是让行玩家在“行1”和“行2”之间感到无差异。

    • 行玩家选择“行1”的期望收益：q(a)+(1−q)(b)

    • 行玩家选择“行2”的期望收益：q(d)+(1−q)(c)

      令二者相等：

      aq + b(1 − q) = dq + c(1 − q)aq + b − bq = dq + c − cqb − c = q(d − a − c + b) = q((b + d) − (a + c))

      解得列玩家的最优概率 q：

      q∗=(b+d)−(a+c)b−c=(a+c)−(b+d)c−b

推导博弈的价值 V

博弈的价值 V 是在均衡状态下，行玩家的期望收益。我们可以将求得的 q* 代入行玩家的期望收益公式：

V=aq∗+b(1−q∗)=q∗(a−b)+bV=(a+c)−(b+d)c−b(a−b)+b

对上式进行通分并化简：

V=(a+c)−(b+d)(c−b)(a−b)+b((a+c)−(b+d))

$$V = \frac{ac - bc - ab + b^2 + ab + bc - b^2 - bd}{(a+c) - (b+d)}$$分子中的 -bc, +bc, -ab, +ab, +b², -b² 项都相互抵消了，最终得到一个非常优美的公式：

V=(a+c)−(b+d)ac−bd

最终通解

对于一个不存在纯策略均衡的 2x2 零和博弈矩阵 A=(adbc)，其通解为：

  1. 行玩家的最优混合策略 (p∗,1−p∗)：

    p∗=(a+c)−(b+d)d−c

  2. 列玩家的最优混合策略 (q∗,1−q∗)：

    q∗=(a+c)−(b+d)c−b

  3. 该博弈对行玩家的价值 V：

    V=(a+c)−(b+d)ac−bd

为什么行玩家是最大化最小值，而不是最小化极大值？

问得特别好！这正是理解零和博弈中双方战略思想的精髓所在。

简单来说，答案是：因为他们的根本目标不同。

  • 行玩家的目标：最大化自己的收益。
  • 列玩家的目标：最大化自己的收益，这在零和博弈中就等价于最小化行玩家的收益。

让我们一步一步地、站在行玩家（Player 1）的角度来思考他为什么必须是“最大化最小值 (Maximin)”。

1. 行玩家的思考过程：“我如何为最坏的情况做准备？”

行玩家是一个理性的决策者，他想让自己赚得尽可能多。但他知道两件事：

  • 他的收益不只取决于自己，还取决于对手的选择。
  • 他的对手（列玩家）的目标和他完全相反。他每多赚一块钱，就意味着对手要多亏一块钱。所以，对手会想尽一切办法让他赚得最少。

基于这个“对手会尽力坑我”的假设，行玩家必须采取一种非常谨慎和保守的策略。他的思考逻辑如下：

  1. 审视自己的第一个选项（比如“行1”）：

    “如果我选择‘行1’，我的对手会怎么做？他会看遍‘行1’的所有结果，然后选择那个能让我收益最低的选项。所以，如果我出‘行1’，我能得到的保底收益就是这一行里的最小值。”

  2. 审视自己的第二个选项（比如“行2”）：

    “同理，如果我选择‘行2’，理性的对手也会选择那一列来让我获得‘行2’里的最低收益。这个最小值就是我出‘行2’的保底收益。”

  3. 做出最终决策：

    现在，行玩家手上有一份“保底收益清单”，清单上的每一项都对应着他选择某一行后，在最坏情况下能得到的最低收益。作为一个想最大化自己收益的人，他会看着这份“保底清单”，然后选择那个能提供最高（Maximum）保底收益的选项。

整个过程串起来就是：他先找出每一行的最小值 (Minimum)，然后在这些最小值中，选择一个最大值 (Maximum)。这就是最大化最小值 (Maximin)。

这是一种“在最坏的情况里，为自己争取最好的结果”的策略。

2. 为什么“最小化极大值 (Minimax)”是对手的策略？

现在我们换位思考，站到列玩家（Player 2）的角度。

  1. 他的目标：他的目标是最小化自己的损失，也就是最小化行玩家的收益。
  2. 他的思考过程：
    • 审视他的第一个选项（比如“列1”）：“如果我出‘列1’，我的对手会怎么做？他会看遍‘列1’的所有结果，然后选择那个能让他自己收益最高的选项。所以，如果我出‘列1’，我可能遭受的最大损失（也就是行玩家的最大收益）就是这一列里的最大值。”
    • 审视他的第二个选项（比如“列2”）：“同理，如果我出‘列2’，我可能遭受的最大损失就是‘列2’里的最大值。”
    • 做出最终决策：现在，列玩家手上也有一份“最大损失清单”。作为一个想最小化自己损失的人，他会看着这份清单，然后选择那个能让他的最大损失变得最小 (Minimum) 的选项。

整个过程串起来就是：他先找出每一列的最大值 (Maximum)，然后在这些最大值中，选择一个最小值 (Minimum)。这就是最小化极大值 (Minimax)。

总结

行玩家 (Player 1) 列玩家 (Player 2)
目标 最大化自己的收益 最小化自己的损失（即最小化行玩家的收益）
思想 在最坏的情况里为自己争取最好结果 让对手在最好的情况下也占不到太大便宜
策略 最大化最小值 (Maximin) 最小化极大值 (Minimax)

所以，行玩家之所以是“最大化最小值”，是因为他的出发点是为自己求利，同时假设对手会让他利无可利；而“最小化极大值”则是从对手的视角出发，目标是让行玩家的利益最小化。冯·诺依曼的惊人发现在于，在两人零和博弈中，这两种看似不同的思考路径，最终会指向同一个均衡解。

7-4

这张幻灯片介绍了“序贯决策”框架中那个最普适、最强大的模型——随机博弈（或称马尔可夫博弈）。它完美地将我们之前讨论过的“矩阵博弈”和“马尔可夫决策过程(MDP)”融合在了一起，是理解现代多智能体强化学习 (MARL) 的理论基石。

1. 集大成者：融合了博弈论与强化学习

我们可以这样理解随机博弈的构成：

  • 它借鉴了矩阵博弈 (Matrix Games) 的核心思想：在任何一个时刻，都有多个智能体在进行策略互动。
  • 它又借鉴了马尔可夫决策过程 (MDPs) 的核心思想：整个系统存在多个状态，环境会根据参与者的行动从一个状态转移到另一个状态。

随机博弈 = 多智能体的MDP = 随状态变化的重复博弈

2. 图示解读：一场动态演变的博弈

这张图非常直观地展示了随机博弈是如何运作的。我们可以把它想象成一场动态的冒险游戏：

  1. 身处状态：假设你和你的对手（参与者1和2）当前身处“状态1 (State 1)”。
  2. 进行博弈：在这个状态下，你们必须玩“状态1”对应的那个2x2矩阵博弈。比如，你（P1）选择了“下”，对手（P2）选择了“右”。
  3. 获得即时回报：根据矩阵，这个(下, 右)的联合行动会给你们带来 (1, 1) 的即时回报。
  4. 世界发生改变（状态转移）：这是最关键的一步。你们的联合行动 (下, 右) 触发了状态转移。紫色的箭头告诉我们，接下来会发生什么：
    • 有 40% 的概率，你们会进入“状态2”。
    • 有 60% 的概率，你们会进入“状态3”。
  5. 进入新博弈：假设你们进入了“状态2”。现在，你们面对的是一个全新的2x2矩阵博弈，有着完全不同的收益规则。你们需要在这个新规则下再次决策，然后获得新的回报，并再次触发新的状态转移。

这个过程会一直持续下去。

3. 参与者的目标：深谋远虑

在一个随机博弈中，一个理性的参与者不会只盯着当前这一轮的得失。他的决策必须是深谋远虑的。

  • 例如，在“状态1”中，(上, 左)这个选择能立刻带来(2, 2)的高回报。但如果这个选择有90%的概率会让你转移到一个对你极其不利的“惩罚状态”，那你可能就不会选它。
  • 反之，你可能会选择一个即时回报较低的行动，如果它有很大概率把你带到一个未来回报极高的“天堂状态”。
  • 这就是折扣回报 (discounted rewards) 的作用。玩家的目标是最大化未来所有回报的“总现值”，即找到一个在所有状态下都最优的策略（Policy），而不仅仅是当前状态。

总结：随机博弈为我们描绘了一幅最接近真实世界复杂性的图景——多个决策者在不断变化的环境中持续互动。我们之前讨论的多智能体学习（MAL）的困难，例如“环境的非平稳性”，正是源于这个框架。对于任何一个智能体来说，环境之所以“不稳定”，就是因为状态的转移和回报不仅取决于自己的行动，还取决于其他所有同样在学习和适应的智能体的行动。

7-5

标题：随机博弈 vs. MDP (Stochastic Games vs. MDP)

  • 在一个随机博弈中，如果除了一个参与者之外的所有其他参与者都采取固定的 (fixed) 策略，那么对于剩下的那个智能体来说，这个问题就退化 (reverts back) 回了一个MDP。
    • — 这是因为，固定其他智能体的策略（即使这些策略是随机的），会使得状态转移变得马尔可夫化 (Markovian)，即只取决于剩下的那个参与者的行动。

这张幻灯片通过一个“思想实验”，精准地指出了多智能体学习（MARL）与单智能体学习（RL）的根本区别到底在哪里。它告诉我们，多智能体问题的核心困难，并不在于“有多个会动的个体”，而在于“有多个会学习和适应的个体”。

1. 问题复杂性的根源：变化的“游戏规则”

我们之前讨论，多智能体学习之所以困难，是因为环境的“非平稳性”（Non-stationarity）。对于任何一个智能体“我”来说，其他的智能体都是环境的一部分。当其他智能体也在学习、也在改变他们的策略时，就相当于“我”所面对的游戏规则本身在不断变化，这让学习变得极为困难。

2. “固定策略”意味着什么？—— 从“对手”到“自然规律”

这张幻灯片提出的“固定其他所有人的策略”这个条件，是问题的关键。这意味着什么呢？让我们用一个生动的例子来说明：

  • 情景A：随机博弈 (Stochastic Game)

    你是一个新手出租车司机（剩下的那个智能体），在一个大城市里学习如何最快地接送客人。城里还有成千上万的老司机（其他智能体），他们经验丰富，每天都在根据实时路况、新闻、个人习惯等调整自己的路线。这是一个极度复杂的多智能体学习问题，因为你的“环境”（即其他司机的行为）每天都在变。

  • 情景B：退化为MDP

    现在，假设奇迹发生，城里所有其他司机都被换成了简单的机器人。这些机器人的行为遵循一套永不改变的固定程序。例如：“在周一上午8点的A路口，这群机器人有70%会右转，30%会直行”。这个概率是固定的，机器人不会再学习或改变了。

在这个时刻，对于你（唯一的人类司机）来说，发生了什么？

其他司机不再是具有主观能动性的“对手”了，他们变成了城市交通中一个虽然是随机的、但却是稳定的、可预测的自然规律。

3. “马尔可夫化”：游戏规则被重新稳定下来

一旦其他人的策略被固定，整个系统对于“我”来说，就重新满足了马尔可夫性质。

  • 当“我”在某个路口（状态s），选择直行（动作a），下一分钟会到达哪里、会花多长时间（下一个状态s’），其概率 p(s′∣s,a) 现在只取决于“我”的动作a和那群机器人固定的行为模式。
  • 这个转移概率不再随时间变化了，因为机器人的“想法”不会变。
  • 于是，这个复杂的、不可预测的多智能体博弈，就退化成了一个经典的、可解的单智能体马尔可夫决策过程（MDP）。

总结：

这张幻灯片通过“固定他人策略”这一巧妙的设定，帮助我们隔离并识别了多智能体问题的“困难之源”。困难不在于环境中存在多个行动者，而在于这些行动者策略的动态演化。这个洞见是许多高级多智能体学习算法的基础，例如，有些算法就是通过“轮流学习”（一个学习，其他暂时固定）或者对其他智能体的策略进行建模和预测，来试图克服这种“非平稳性”带来的挑战。

7-6

这张幻灯片将原本简单的单次博弈，升级成了一个更复杂、也更贴近现实的双状态随机博弈 (Two-state Stochastic Game)。这里的“纳什均衡”不再是单个的行动组合，而是一个策略组合 (a profile of policies)，即每个厂商在每种状态下应该如何行动的完整计划。

这个问题的解取决于一个幻灯片上未给出但至关重要的参数——折扣因子 γ (discount factor)，它代表了厂商对未来收益的重视程度。

1. 分解两个“子博弈”

我们首先分析在每个状态下，只考虑当前一轮收益的“短视”均衡是什么。

  • 在状态1（无税收）：

    正如我们上一题分析的，双方都有一个占优策略：“污染”。因此，该状态下的短视纳什均衡是 (污染, 污染)。但这个选择会带来一个后果：根据转移概率 (0,1)，游戏将100%转移到状态2（有税收）。

  • 在状态2（有税收）：

    我们分析这个新的利润矩阵：

    • 对厂商1：如果厂商2选择“清洁”，厂商1会选“污染”(4>1)；如果厂商2选“污染”，厂商1还是会选“污染”(3>0)。“污染”是厂商1的占优策略。
    • 对厂商2：如果厂商1选择“清洁”，厂商2会选“污染”(5>2)；如果厂商1选“污染”，厂商2还是会选“污染”(4>1)。“污染”也是厂商2的占优策略。
    • 因此，该状态下的短视纳什均衡也是 (污染, 污染)。这个选择的后果是，游戏将100%留在状态2，继续被征税。

2. 长期战略的困境：短视 vs. 远见

分析完子博弈后，真正的战略困境浮现了。我们以厂商1在状态1的决策为例：

  • 短视的选择（选择“污染”）：可以立刻获得很高的收益（如果对方也污染，能得6）。但代价是，从下一轮开始，将永远陷入低收益的“状态2”。
  • 远见的选择（选择“清洁”）：会牺牲掉一部分即时收益（如果对方也清洁，只能得4）。但好处是，游戏将100%留在高收益的“状态1”，未来每一轮都可以继续获得高收益。

厂商会如何选择，完全取决于他们有多“远视”，即折扣因子 γ 有多大。

3. 可能存在的纳什均衡

这个随机博弈可能存在多个纳什均衡。

均衡A：“悲观”的污染均衡

  • 策略：无论在哪种状态，双方都选择“污染”。
  • 分析：如果对方的策略是“永远污染”，那么你最好的应对也是“永远污染”。因为如果你单方面选择“清洁”，在状态1你会获得更低的即时收益(3 vs 6)然后还是会进入状态2；在状态2你单方面“清洁”的收益(0 vs 3)也更低。因此，没有任何一方有单方面改变策略的动机。
  • 结论：（策略1=污染, 策略2=污染）是一个纳什均衡。在这个均衡下，厂商们第一轮在状态1获得(6,7)的收益，然后永久地陷入状态2，每轮获得(3,4)的收益。这是一个低效的、“双输”的均衡。

均衡B：“合作”的清洁均衡

  • 策略：双方约定，只要在状态1，就都选择“清洁”。

  • 分析：要让这个“君子协定”成为一个稳定的纳什均衡，就必须保证“背叛”是无利可图的。

    • 遵守协定的收益流（以厂商1为例）：4+4γ+4γ2+⋯=1−γ4

    • 单方面背叛的收益流：在状态1选择“污染”获得一次性的高收益7，但之后游戏进入状态2，双方陷入“永远污染”的均衡，后续每轮收益为3。其收益流为: 7+3γ+3γ2+⋯=7+1−γ3γ

    • 要让大家遵守协定，必须满足“遵守的收益 ≥ 背叛的收益”：

      1−γ4≥7+1−γ3γ

      4≥7(1−γ)+3γ⟹4≥7−4γ⟹4γ≥3⟹γ≥43

  • 结论：如果厂商们对未来的重视程度足够高（即折扣因子 γ ≥ 3/4），那么双方在状态1都选择“清洁”也可以成为一个纳什均衡。因为对未来的长期高收益的渴望，足以抑制住当前“背叛”以获取短期利益的诱惑。

总结：这个引入了税收和状态转移的随机博弈模型，比单次博弈要复杂和深刻得多。它的均衡不再是唯一的，而是可能存在多个——一个“坏”的均衡和一个“好”的均衡。系统最终会落入哪个均衡，取决于参与者对未来的耐心和期望（由γ体现）。这也为政府政策的设计提供了启示：一个好的制度，应该让“合作”的门槛（即所需的γ值）尽可能低，让参与者更容易达成对社会有利的结果。

7-7

标题：例子：“大冒险”游戏 (Example: the game of Dare)

  • 参与者1，领导者 (the leader)，和参与者2，挑战者 (the challenger)，同时选择“放弃 (pass)”或“挑战 (dare)”。

    • — 如果双方都选择“放弃”，支付为零（且游戏结束）。
    • — 如果参与者1“放弃”而参与者2“挑战”，参与者1赢得1。
    • — 如果参与者1“挑战”而参与者2“放弃”，参与者1赢得3。
    • — 如果双方都选择“挑战”，这个基础游戏将角色互换后重新进行。
      • (领导者变成挑战者，反之亦然)。
    • — 如果参与者们永远地持续“挑战”下去，则支付为零。

  • 博弈矩阵 G:

    $$G = \bordermatrix{ & \text{放弃} & \text{挑战} \cr \text{放弃} & 0 & 1 \cr \text{挑战} & 3 & -G^T }$$

    其中 -Gᵀ 代表角色互换后的游戏。（它的矩阵是G矩阵的转置的负数。）-Gᵀ的价值是G的价值的负数。

这张幻灯片描述了一个非常有趣的递归博弈 (recursive game)，它是一种特殊的随机博弈 (stochastic game)。这个博弈只有两个状态：“P1是领导者”和“P2是领导者”。当出现 (挑战, 挑战) 的结果时，游戏就在这两个状态之间切换。

1. 问题的核心：递归的价值

这个问题的精髓在于右下角的那个支付 -Gᵀ。

  • 让我们设这个博弈对于当前的领导者来说，其价值 (Value) 为 V。

  • 那么，领导者的支付矩阵就可以写成：

    G=(031Value(subgame))

  • 当双方都选择“挑战”时，游戏进入子博弈。在这个子博弈中，原先的挑战者（P2）变成了新的领导者。由于游戏的对称性，这个子博弈对于新的领导者（P2）来说，价值也应该是 V。

  • 既然对于新的领导者（P2）价值是 V，那么对于新的挑战者（也就是原来的P1）来说，价值就是 -V（因为是零和博弈）。

  • 因此，原领导者（P1）的支付矩阵可以写成一个包含其自身价值 V 的形式：

    G=(031−V)

2. 求解博弈价值 V

现在，问题转化为了：求解这个特殊矩阵的价值 V，并且这个价值 V 必须等于它自身。

$$V = \text{value} \begin{pmatrix} 0 & 1 \ 3 & -V \end{pmatrix}$$我们可以使用之前推导出的 2x2 零和博弈的通用价值公式：$$V = \frac{ac - bd}{(a+c) - (b+d)}$$其中，a=0, b=1, d=3, c=-V。代入公式：$$V = \frac{(0)(-V) - (1)(3)}{(0)+(-V) - (1)-(3)} = \frac{-3}{-V-4}$$现在我们得到了一个关于 V 的方程，求解它：

V(−V − 4) = −3−V2 − 4V = −3V2 + 4V − 3 = 0

这是一个一元二次方程。使用求根公式

我们得到了两个可能的解：V1=7−2≈0.646 和 V2=−7−2≈−4.646。

3. 选择正确的解

哪个才是这个博弈真正的价值呢？

我们看领导者的支付矩阵，他有一个“放弃”的选项。如果他选择“放弃”，最坏的结果是对手选择“挑战”，此时他的收益是1。这意味着，领导者至少可以为自己保证一个非负的收益。因此，一个负数（比如-4.646）不可能是这个博弈的理性价值。

所以，这个博弈对于领导者的价值是：根号7减去2

7-8

求解博弈G1和G2的价值：

7-9

7.2 值迭代与策略迭代

7-10

1、学习随机博弈中状态值函数贝尔曼方程推导

2、与单智能体MDP的关键区别

这个公式虽然形式上与单智能体MDP的贝尔曼方程很像，但幻灯片的最后一点指出了两个根本性的区别，这也是多智能体问题复杂性的根源：

  1. 价值是个人化的 (for each agent)：在MDP中，只有一个价值函数 V(s)。但在随机博弈中，每个参与者 i 都有自己的一套价值函数 Vi(s)。同一个状态 s，对我来说可能是天堂（Vi很高），对你来说可能却是地狱（Vj很低）。这体现了参与者之间合作与冲突并存的关系。
  2. 价值依赖于联合策略 (on the joint policy)：这是最致命的区别。在MDP中，价值函数 Vπ(s) 只取决于我自己的策略 π。但在这里，Viπ(s) 的值不仅取决于我的策略 πi，还取决于其他所有人的策略 π−i，因为是联合行动决定了回报和状态转移。
    • 这就导致了我们之前讨论的“非平稳性”或“移动靶心”问题。如果我的对手改变了他的策略，那么即使我的策略和当前状态都没变，我整个的价值函数 Vi(s) 也会跟着改变。我原以为很有价值的状态，可能因为对手策略的改变而突然变得一文不值。
7-11

这张幻灯片在重申了状态价值的定义之后，提出了一个关于它的非常重要的数学性质：有界性 (Boundedness)。这个性质是随机博弈能够被分析和求解的理论基础之一。

1. 核心思想：无限过程，有限价值

这条结论的核心思想是：尽管一个随机博弈的过程可能永远持续下去，但从任何一个状态开始，任何一个参与者能够获得的总的“折扣”价值都不是无限的，而是一个有限的、有上限的数值。

幻灯片给出了这个上限的计算公式：1−γM。

  • M: 代表在整个游戏所有可能的情况下，任何参与者在单一一轮中所能获得的最大绝对收益。可以理解为这个游戏里“单次操作的最大奖励或最大惩罚（的绝对值）”。
  • γ (gamma): 是我们熟悉的折扣因子（0 < γ < 1），代表了我们对未来收益的耐心程度。

2. 这个上限公式是怎么来的？（几何级数）

这个公式的推导非常直观，它基于我们熟知的等比数列（几何级数）求和。

  1. 根据定义，状态价值是所有未来折扣回报的总和：

    Viπ(s)=Eπ[r0+γr1+γ2r2+γ3r3+…]

  2. 在任何一步 k，我们能获得的即时回报 rk 的绝对值，都不可能超过定义好的最大单轮回报 M。即 ∣rk∣≤M。

  3. 因此，总价值 Viπ(s) 必然小于或等于一种最极端、最理想的情况：假设我们在未来的每一步，都能幸运地获得最大的正回报 M。

    Viπ(s)≤M+γM+γ2M+γ3M+…

  4. 将 M 提取出来：

    Viπ(s)≤M(1+γ+γ2+γ3+…)

  5. 括号里的部分是一个公比为 γ 的无穷等比数列。因为 γ < 1，这个级数是收敛的，其和为 1−γ1。

  6. 因此，我们得到了最终的边界：

    Viπ(s)≤1−γM

3. 这个性质为什么重要？

  1. 保证问题“有解”：这个有界性保证了我们要求解的状态价值函数是一个“行为良好”的函数，它的值不会发散到无穷大。这是所有后续分析和算法能够成立的数学前提。如果没有这个保证，我们可能都无法定义“最优策略”，因为所有策略的总回报都是无穷大，无法比较。
  2. 为算法提供基础：在很多求解随机博弈的算法（例如价值迭代）中，这个边界可以用于初始化价值函数，或者作为算法收敛性的一个判断依据。它确保了算法的计算过程会在一个有限的数值空间内进行，最终能够稳定下来。

总结：这张幻灯片的核心是告诉我们，尽管随机博弈的博弈过程可能是无限的，但其价值是有限的。这个有界性不仅为问题的“可解性”提供了理论保障，也为实际的计算算法奠定了基础。

7-12
7-13

结论与洞察

这个例子深刻地揭示了短期利益与长期战略之间的权衡。

  • 从短期看，第1列对列玩家更有利（即时损失更小）。
  • 但从长期看，第1列有更高的概率让游戏继续下去，这意味着他未来要持续地向行玩家支付价值为v的收益。而第2列能更快地结束游戏，从而“止损”。
  • 最终的均衡策略显示，长期战略（避免未来损失）的重要性压倒了短期利益。因此，列玩家的最优策略是更频繁地选择那个能更快结束游戏的第2列，尽管它眼前的损失看起来更大。
7-14

标题：价值迭代 (Value Iteration)

  • 夏普利证明了 vn(s) 会收敛到从s开始的随机博弈的真实价值 v(s)。
    • — 首先，收敛是以指数速率 (exponential rate) 进行的：最大误差至少以 γn 的速度下降。
    • — 其次，在第 n+1 阶段的最大误差，至多是“从n到n+1阶段的最大变化量”乘以 γ/(1−γ)。

这张幻灯片深入探讨了“价值迭代”算法的性能保证。它告诉我们，夏普利不仅证明了价值迭代这个方法是可行的（即最终能找到正确答案），更证明了它是高效和可靠的。这使得价值迭代从一个理论上的概念，变成了一个可以在实践中应用的强大工具。

1. 指数速率收敛：为什么说它“高效”？

“指数速率收敛”听起来很抽象，但它的意思是，算法的精确度在每一步迭代后都会得到一个“质的飞跃”。

  • 一个比喻：想象你在寻宝，宝藏在1公里外。有一个向导，你每走一步，他都会告诉你：“你现在离宝藏的距离，是你上一步距离的90%”。
    • 你的误差（与宝藏的距离）在每一步都会乘以一个固定的因子（0.9）。
    • 第一次迭代后，误差是 1×0.9。
    • 第二次迭代后，误差是 1×0.92。
    • 第n次迭代后，误差是 1×0.9n。
    • 误差以 0.9n 的速度急剧缩小，这就是指数级的衰减。
  • 在价值迭代中：折扣因子 γ (一个小于1的数) 就扮演了这个“0.9”的角色。每迭代一次，我们估算的价值函数 vn(s) 与真实价值 v(s) 之间的最大误差，都会大致缩小一个 γ 倍。因为 γ 小于1，所以经过多次迭代后，误差会变得非常小，算法能很快地逼近真实解。这背后的数学原理是，夏普利证明了价值迭代的更新算子是一个压缩映射 (Contraction Mapping)。

2. 误差边界：为什么说它“可靠”？

第二点结论解决了一个非常实际的问题：“我怎么知道什么时候可以停止算法，并且保证我的答案足够精确了？”

  • 面临的困境：我们希望我们的误差，即 |我们的估算值 vₙ - 真实值 v*|，小于一个我们能接受的阈值（比如0.001）。但问题是，我们并不知道那个神秘的“真实值 v*”到底是多少，所以无法直接计算这个误差。

  • 夏普利提供的解决方案：他给出了一个可计算的误差上限。公式告诉我们：

    真实的未知误差≤可计算的最大单步变化量×1−γγ

    这里的“可计算的最大单-步变化量”指的是 ∣vn+1(s)−vn(s)∣max，也就是在你最近一次迭代中，所有状态的价值估算值变化最大的那一个。这个值我们在计算过程中是完全知道的。

  • 实际应用（停止条件）：

    1. 我们设定一个目标精度 ε，比如我希望我的最终答案与真实值的误差不超过0.001。
    2. 根据公式，只要我们能让 (可计算的最大单步变化量) * γ/(1-γ) 这个上限小于 ε，那么真实的误差就一定小于 ε。
    3. 因此，我们的算法停止条件就变成了：持续迭代，直到我们观察到的最大单步变化量小于 ϵ⋅γ1−γ。
    4. 一旦满足这个条件，我们就可以放心地停止迭代，并宣布当前的估算值 vn+1 就是一个足够精确的解。

总结：这张幻灯片从理论上为价值迭代算法的有效性提供了强有力的背书。指数速率收敛保证了它的计算速度，而实用的误差边界则为它在现实中的应用提供了可靠的停止准则，使其成为求解两人零和随机博弈的核心算法之一。

7-15

为什么最小停止概率是0.5？

1. “最小停止概率是0.5”的来源分析

这个结论来自于对 G₁ 和 G₂ 两个矩阵中所有单元格的“持续概率”的分析。

在一个随机博弈的支付单元格中，形如 “即时回报 + 概率 × 未来价值” 的结构，那个概率就代表了游戏继续下去的可能性。而“停止概率”则等于 1 - 继续概率。

让我们来逐一检查两个矩阵中所有结果的“停止概率”：

对于博弈 G₁:

G(1)=(4+0.3G(1)1+0.4G(2)0+0.4G(2)3+0.5G(1))

  • (行1, 列1): 继续概率是 0.3。 停止概率 = 1 - 0.3 = 0.7
  • (行1, 列2): 继续概率是 0.4。 停止概率 = 1 - 0.4 = 0.6
  • (行2, 列1): 继续概率是 0.4。 停止概率 = 1 - 0.4 = 0.6
  • (行2, 列2): 继续概率是 0.5。 停止概率 = 1 - 0.5 = 0.5

对于博弈 G₂:

G(2)=(0+0.5G(1)−4−51+0.5G(2))

  • (行1, 列1): 继续概率是 0.5。 停止概率 = 1 - 0.5 = 0.5
  • (行1, 列2): 支付是-5（没有未来价值项）。继续概率是 0。停止概率 = 1 - 0 = 1
  • (行2, 列1): 支付是-4。继续概率是 0。停止概率 = 1 - 0 = 1
  • (行2, 列2): 继续概率是 0.5。停止概率 = 1 - 0.5 = 0.5

现在，我们把所有计算出的停止概率放在一起：{ 0.7, 0.6, 0.5, 1 }。

在所有这些可能性中，最小的那个值，就是 0.5。

这就是“最小停止概率是0.5”这句话的直接来源。

2. 这个数字为什么如此重要？

这个“最小停止概率”反过来告诉了我们整个系统的“最大继续概率”。

  • 最小停止概率 = 0.5
  • 最大继续概率 = 1 - 最小停止概率 = 1 - 0.5 = 0.5

这个“最大继续概率”，可以被看作是整个随机博弈系统的有效折扣因子 γ (effective discount factor)。

为什么呢？

价值迭代算法的收敛速度，取决于其更新算子是不是一个“压缩映射”，而其“压缩程度”就由折扣因子γ决定。为了保证整个系统一定收敛，我们必须考虑最坏的情况。

  • 收敛的最坏情况是什么？ 就是收敛得最慢的情况。
  • 什么时候收敛得最慢？ 就是“折扣”打得最少的时候，也就是游戏最不容易结束、继续下去的概率最大的时候。

在这个博弈中，游戏继续下去的最大概率是0.5。因此，整个价值迭代算法的收敛速度就由这个0.5来决定。

  • 收敛速率：因为有效折扣因子γ是0.5，所以算法的误差是以 (0.5)n 的指数速率下降的。
  • 误差边界：根据我们之前学过的误差边界公式 真实误差 ≤ 最大单步变化量 × γ/(1-γ)，代入γ=0.5，我们得到 γ/(1-γ) = 0.5/0.5 = 1。这意味着，真实的未知误差，不会超过我们在上一步迭代中能观测到的最大变化量。幻灯片中说v₆的误差至多是0.0002，就是基于这个原理计算出来的（从v₅到v₆的最大变化量约为0.0001，其上限0.0002是完全正确的）。

总结： “最小停止概率是0.5”这个结论，是通过分析所有可能结果得出的。它的真正意义在于，它为我们确定了整个动态系统的有效折扣因子 γ=0.5，从而为算法的收敛速度和误差分析提供了坚实的理论依据。

7.3 均衡学习

7-16

标题：均衡学习器 (Equilibrium Learners)

  • 均衡学习器的目标是找到作为随机博弈纳什均衡的策略。
    • — 由于找到这类均衡很困难，它们通常专注于一个较小的问题类别，例如零和博弈或两人一般和博弈。
  • 找到纳什均衡的优点在于，智能体可以学到一个性能的下界 (lower bound)，并且，
    • — 在这种情况下，它变得相当独立于其他智能体所采取的策略。
    • — 它至少会获得与该均衡相对应的回报量。

这张幻灯片介绍了一类在多智能体学习（MAL）中非常重要的算法思想——均衡学习器。这类算法的目标非常明确和“学院派”：它们不像其他一些学习器那样只追求“打败对手”或“最大化短期回报”，而是试图直接计算并执行整个博弈的纳什均衡策略。

  1. 什么是“均衡学习器”？（扮演博弈论家的智能体）

我们可以把“均衡学习器”想象成一个内置了博弈论模型的“理性人”。它的工作流程是：

  1. 观察和建模：通过与环境和其他智能体的交互，学习并构建出当前博弈的规则（即支付矩阵）。
  2. 计算均衡：利用我们之前学过的算法（如线性规划、迭代法等）来计算出这个博弈的纳什均衡解。
  3. 执行策略：按照计算出的纳什均衡策略（通常是混合策略）来行动。

这种方法与其他一些学习方法（比如，只根据对手上一步行动来调整策略的“最优反应”学习器）形成了鲜明对比。

  1. 核心优势：稳健性与“安全网”

幻灯片的核心观点是，采取这种方法的最大优势在于其稳健性 (robustness) 和它提供的一个“安全网”。

  • 性能下界 (Lower Bound)：纳什均衡策略（尤其是在零和博弈中的极小化极大策略）本质上是一种防御性策略。它的设计初衷就是为了应对一个完美的、理性的、并且想尽办法针对你的对手。
  • 独立于对手策略：当你执行纳什均衡策略时，你等于为自己的表现设定了一个最坏情况下的保证。无论对手多么聪明，只要他也是理性的，他就无法让你得到比这个均衡价值更差的结果。从这个意义上说，你的表现变得“独立于”对手的具体策略，因为你已经为所有最坏的情况做好了准备。
  • 一个生动的例子：在“石头剪刀布”中，你的纳什均衡策略是完全随机地出招（各1/3概率）。当你这样做时，你为自己保证的“性能下界”是期望收益为0（不输不赢）。你的对手，无论他怎么出招，长期来看都无法让你输钱。但如果你放弃这个均衡策略，比如你决定100%出“石头”，那你的“安全网”就没了，对手可以100%出“布”来稳定地击败你。
  1. 局限与挑战

当然，这种方法也有其固有的缺点，这也是为什么它不是多智能体学习中唯一的范式：

  1. 计算复杂度高：正如幻灯片和我们之前的讨论所指出的，计算纳什均衡（尤其是在非零和或多于两人的游戏中）是一个计算上非常困难的问题。这限制了均衡学习器在大型、复杂问题上的应用。
  2. 对“理性对手”的强假设：这种方法最大的前提是，它假设你的对手也是一个完美的“均衡学习器”。但如果你的对手是一个新手，或者是一个非理性的、有固定套路的玩家呢？在这种情况下，你那套“万无一失”的均衡策略可能就显得过于保守了。一个更具攻击性、更具“剥削性”的策略，可能会让你获得远高于均衡价值的收益。
  3. 多重均衡问题：在很多一般和博弈中，可能存在多个纳什均衡点。如果不同的学习器各自计算并收敛到了不同的均衡目标上，它们之间可能无法有效协调，导致一个糟糕的集体结果。

总结：均衡学习器是一种理论驱动的、非常强大的多智能体学习方法。它的核心优势在于稳健可靠，能提供最坏情况下的性能保证。它的主要缺点在于计算成本高昂，且在面对非理性或次优对手时可能过于保守。它在两人零和博弈这类结构清晰、均衡唯一的场景中最为有效。

7-17

这张幻灯片将强化学习中另一个核心概念——Q值（或称状态-动作价值）——引入到了随机博弈的框架中。它揭示了Q值在多智能体环境下的定义，并含蓄地指出了由此带来的巨大挑战。

  1. Q值与V值的关系

首先，我们需要理解Q值和我们之前讨论的V值（状态价值）之间的关系。它们是同一枚硬币的两面：

  • V值 (State Value) Viπ(s) 回答的是：“在状态s下，长期来看我能得到多少好处？”
  • Q值 (Action Value) Qiπ(s,a) 回答的是：“在状态s下，如果我们这次采取联合行动a，长期来看我能得到多少好处？”

它们之间的关系非常清晰：

  • 从Q到V：一个状态的价值（V），等于在该状态下根据策略π所能采取的所有动作的Q值的期望。

    Viπ(s)=∑aπ(a∣s)Qiπ(s,a)

  • 从V到Q：一个动作的价值（Q），等于采取该动作后的即时回报，加上所有可能进入的下一个状态的折扣V值的期望。

    Qiπ(s,a)=ri(s,a)+γ∑s′p(s′∣s,a)Viπ(s′)

    (注：这里假设了回报r是关于(s,a)的函数)

幻灯片上的推导过程正是展示了这层关系。

  1. 多智能体Q值的“灾难”：联合行动空间

幻灯片的最后一点“个体的Q值也取决于所有参与者的行动”是理解多智能体学习困难的关键。这看起来是一句废话，但其背后隐藏着指数级的复杂性。

  • 在单智能体中 (MDP)：

    Q函数是 Q(s,a)，其中a是我个人的行动。要找到最优动作，我只需要在我的几个可选动作中，找到那个能使 Q(s,a) 最大的a即可。这很简单。

  • 在多智能体中 (Stochastic Game)：

    Q函数是 Qi(s,a)，其中 a=(a1,a2,…,an) 是一个联合行动向量。

这就带来了两个灾难性的问题：

  1. 维数灾难 (Curse of Dimensionality)：我（智能体i）的Q值，取决于我、你、他、所有人共同做了什么。如果每个智能体有10个动作，总共有5个智能体，那么联合行动空间的大小就是 105=10万。要为每一个联合行动都计算和存储一个Q值，在计算和存储上都是一个巨大的挑战。
  2. 不确定性与协调问题：即使我能计算出所有可能的 Qi(s,a)，在做决策时，我只知道我自己的动作 ai。为了选择最优的 ai，我必须预测或假设其他所有参与者 a−i 将会采取什么行动。
    • 我怎么知道他们会做什么？
    • 他们也在同时预测我将做什么。
    • 这就形成了一个复杂的“鸡生蛋，蛋生鸡”的循环。我需要找到一个我的最佳行动 ai∗，它是我对他们最佳行动 a−i∗ 的最佳回应；而他们的 a−i∗ 也必须是他们对我 ai∗ 的最佳回应。
    • 这恰恰就是寻找当前状态下这个“子博弈”的纳什均衡的过程。

总结：

这张幻灯片定义了多智能体环境下的Q值。虽然其贝尔曼方程在形式上与单智能体情况相似，但其核心变量从个体行动变成了联合行动。这一根本性的转变，使得基于Q学习的多智能体算法面临着联合行动空间爆炸和智能体间决策高度耦合两大挑战，这也是多智能体强化学习（MARL）领域需要不断探索和解决的核心难题。

7-18

标题：均衡学习器 (Equilibrium Learners)

  • 通常，一个均衡学习器的解，是以下方程组在 π∗=(πi∗,π−i∗) 上的一个不动点 (fixed point)：

    ∀i=1…nQi∗(s,a)=ri(s,a)+γs′∑p(s′∣s,a)Vi∗(s′)

    • — 其中 Vi∗(s′) 代表当所有人都执行纳什均衡联合策略 π∗ 时，智能体 i 的均衡价值，并且
    • — 它是根据 Q值 来计算的。
    • — 这与贝尔曼最优方程很相似，区别在于状态价值函数的计算方式。

这张幻灯片为我们揭示了“均衡学习器”求解随机博弈的最终数学形式，并一针见血地指出了它与我们熟悉的单智能体强化学习（如Q-learning）最根本的区别。

  1. 核心思想：一个“自洽”的均衡解

这个方程组的核心思想是寻找一个“自洽的” (self-consistent) 或 “不动点” (fixed point) 的解。这是什么意思呢？

一个策略组合 π∗ 之所以被称为纳什均衡，是因为当所有人都采用这个策略时，它所产生的长期价值 (Q∗ 和 V∗)，反过来又会证明，继续沿用策略 π∗ 对每个参与者来说都是最优的。没有任何人有单方面偏离的动机。

换句话说，策略 π∗ 产生了价值 V∗，而价值 V∗ 又反过来支撑了策略 π∗ 的最优性。当策略和价值完美地相互印证、循环嵌套时，我们就找到了一个稳定的不动点，也就是纳什均衡。

  1. 最关键的区别：如何从Q值计算V值

幻灯片的最后一句是理解多智能体学习复杂性的关键。它指出，这个方程组和单智能体最优方程（如Q-learning中的）非常像，唯一的区别在于如何从Q值计算出V值。

让我们做一个清晰的对比：

  • 在单智能体MDP中 (Single-Agent MDP):
    • 一个状态的价值 V∗(s)，等于在该状态下采取最优可能动作的Q值。
    • 计算方式: V∗(s)=maxaQ∗(s,a)
    • 逻辑: “我是唯一的玩家，我当然会选择那个能让我长期收益最大化的动作。所以这个状态的价值就是我所有可选动作里最好的那个的价值。” 这是一个简单的最大化运算。
  • 在多智能体随机博弈中 (Multi-Agent Stochastic Game):
    • 一个状态的价值 Vi∗(s)，等于在该状态下，所有参与者玩“Q值博弈”所产生的纳什均衡结果中，参与者 i 能获得的期望收益。
    • 计算方式: Vi∗(s)=NashEquilibriumValuei(Qi∗(s,⋅))
    • 逻辑: “我只是众多玩家之一。我的收益不仅取决于我的动作，还取决于其他所有人的动作。在当前状态s下，所有可能的联合行动的Q值 Qi∗(s,a) 构成了一个新的‘即时’矩阵博弈。我不能简单地选一个收益最大的动作，因为那不一定是最终结果。这个状态的真实价值，是我在所有人都理性地进行这个‘Q值博弈’后，所能期望得到的均衡收益。”
  1. “嵌套”的复杂性

这个区别导致了多智能体学习在计算上的“嵌套式”困难。

  • 在单智能体的价值迭代中，每一步更新V值，只需要做一个简单的 max 运算。
  • 但在多智能体的价值迭代中，为了更新一次V值，你需要在每一个状态 s 下，都去求解一个完整的矩阵博弈（这个博弈的支付由上一轮迭代的Q值定义）。
    • 如果是零和博弈，这个“内部循环”就是解一个线性规划。
    • 如果是一般和博弈，这个“内部循环”就是解一个更复杂的LCP问题。

这使得整个算法的复杂度远高于单智能体的情况。

总结：

这张幻灯片给出了求解随机博弈均衡的最终数学形式。它看起来像我们熟悉的贝尔曼方程，但其核心的价值更新步骤——从Q值到V值的计算——隐藏着天壤之别。从一个简单的“取最大值”操作，升级为了一个复杂的“求解纳什均衡”操作，这正是多智能体系统复杂性的根源所在。

7-19

标题：Nash-Q：一种通用均衡学习器 (Nash-Q: general equilibrium learner)

  • Nash-Q 算法处理的是两人一般和博弈 (two-player general-sum games)。
    • — 使用二次规划 (quadratic programming) 来计算一般和均衡。
    • — 理论上仅限于单一均衡 (single equilibrium) 的情况。

这张幻灯片介绍了一个在多智能体强化学习（MARL）领域具有里程碑意义的算法——Nash-Q Learning。它是将单智能体的Q-learning成功扩展到多智能体博弈论场景的首次重要尝试之一，是典型的“均衡学习器”。

  1. Nash-Q 的核心思想：Q学习与纳什均衡的结合

Nash-Q算法的基本思路，是将我们之前讨论的两个概念——单智能体的Q值更新和博弈论的纳什均衡求解——无缝地结合起来。其学习更新的循环过程如下：

  1. 在当前状态 s，所有智能体采取一个联合行动 a。

  2. 系统转移到下一个状态 s'，并且每个智能体 i 获得一个即时回报 rᵢ。

  3. （纳什部分）：在新的状态 s'，智能体们会“在脑中”求解一个当前的“Q值博弈”。这个博弈的支付矩阵，就是它们当前估算的Q函数 Q(s′,⋅)。通过求解这个矩阵博弈的纳什均衡，它们能得到一个均衡状态下的期望收益，也就是我们上一张幻灯片里提到的均衡状态价值 Vi∗(s′)。

  4. （Q学习部分）：每个智能体 i 使用这个计算出的均衡价值 Vi∗(s′)，来更新它在上一步的Q值 Qi(s,a)。更新公式与标准的Q-learning非常相似：

    Qi(s,a)←(1−α)Qi(s,a)+α⋅[ri+γ⋅Vi∗(s′)]

通过这个过程，智能体学习到的Q值，不仅仅反映了即时的回报，更反映了未来在理性博弈下的长期价值。

  1. 数学工具的升级：从线性规划到二次规划
  • 在零和博弈中，双方利益完全对立，求解纳什均衡（即极小化极大值点）可以被优美地转化为一个线性规划 (LP) 问题。
  • 但在一般和博弈中，双方有各自独立的目标（最大化自己的收益），利益不再完全对立。这种更复杂的关系使得问题无法再用线性规划来描述。
  • 二次规划 (Quadratic Programming, QP) 是一个更强大的优化工具，它可以用来求解某些特定形式的非线性问题。研究表明，寻找两人一般和博弈的纳什均衡，可以被转化为一个二次规划问题来求解。因此，Nash-Q算法在“纳什部分”的计算，就需要动用QP这个更高级的工具。
  1. 理论的“阿喀琉斯之踵”：单一均衡假设

这是Nash-Q算法最核心、也是最致命的局限。

  • 问题所在：我们知道，一般和博弈（例如“性别大战”）经常拥有多个纳什均衡。
  • 算法的困境：在第3步更新时，算法需要一个唯一的均衡价值 Vi∗(s′) 来代入公式。如果求解“Q值博弈”后发现了多个纳什均衡，算法就“懵了”——它不知道应该用哪个均衡点的价值来进行下一步的Q值更新。
    • 比如，如果智能体1选择了均衡A的价值来更新，而智能体2选择了均衡B的价值来更新，他们的学习目标就不一致，整个学习过程会变得不稳定，甚至无法收敛。
  • 无奈的假设：为了保证理论上的收敛性，最初的Nash-Q算法不得不做出一个非常强的假设：在学习过程中的每一个阶段，所遇到的所有“Q值博弈”都恰好只有一个纳什均衡。这个假设在现实中很少成立，极大地限制了Nash-Q的直接应用范围。

总结：

Nash-Q 是一个开创性的算法，它成功地搭建了从单智能体Q学习到多智能体博弈均衡学习的桥梁。它的主要贡献是提供了一套清晰的、理论驱动的MARL框架。然而，它的主要局限——“单一均衡假设”——也恰恰揭示了多智能体学习中一个最核心的难题：当存在多个可能的稳定状态时，一群独立的学习者如何能够相互协调，共同收敛到同一个目标上？ 这个问题至今仍是MARL领域的研究热点。

  1. 每个状态下，每个智能体的支付矩阵是不是不一样？

简单直接的回答是：是的，在一般和博弈（General-Sum Game）中，通常情况下，每个状态下每个智能体的支付矩阵都是不一样的。

下面是更详细的解释：

  1. 为什么会不一样？—— 利益不完全对立

在一个战略博弈中，每个参与者都有自己独立的支付函数（Payoff Function），这个函数决定了在各种可能的结果下，他能获得多少收益。我们可以把这个函数想象成他的“记分牌”或“利益所在”。

  • 在零和博弈中：情况非常特殊。双方的利益是完全对立的。你赢的，恰好就是我输的。所以，参与者2的支付矩阵（我们称之为R₂），恰好是参与者1支付矩阵（R₁）的负数，即 R2=−R1。从这个角度看，它们的矩阵虽然数值不同，但信息是完全对称的，知道一个就知道了另一个。
  • 在一般和博弈中：情况更为普遍和现实。参与者们的利益既不完全对立，也不完全一致。我赢得多，不一定意味着你输得多。我们可能双赢，也可能双输。
  1. 一个经典的例子：协调博弈（或性别大战）

让我们回顾一下之前幻灯片里的那个“协调博弈”的例子：

  • 参与者1 (行玩家) 的支付矩阵:

    R1=(2001)

  • 参与者2 (列玩家) 的支付矩阵:

    R2=(1002)

我们来看一下左上角的那个结果 (行1, 列1):

  • 参与者1得到了 2 的收益。
  • 参与者2得到了 1 的收益。

他们的收益不相等，加起来也不等于零。这意味着，他们各自的支付矩阵 R₁ 和 R₂ 是两个完全不同的矩阵。这反映了他们有共同的目标（都想协调成功，避免得到0），但又有不同的偏好（参与者1更喜欢结果(2,1)，参与者2更喜欢结果(1,2)）。

  1. 在随机博弈的框架下

问题是“每个状态下…”，

在一个一般和随机博弈 (General-Sum Stochastic Game) 中，每一个状态 s 本身就是一个子博弈。因此：

  • 在状态s₁下，参与者1和参与者2面对的是一组支付矩阵 (R1(s1,⋅),R2(s1,⋅))。
  • 当他们转移到状态s₂后，他们面对的可能是另一组完全不同的支付矩阵 (R1(s2,⋅),R2(s2,⋅))。

在每一种状态下，这两个矩阵 R₁ 和 R₂ 通常都是不同的，反映了在该特定情境下，双方复杂的、既有合作又有冲突的利益关系。

总结：

“每个智能体的支付矩阵不一样”这正是“一般和博弈”的核心特征。它打破了零和博弈中“我得即你失”的简单对称性，引入了更复杂的、更贴近现实世界的战略互动，也正是这种复杂性，使得求解一般和博弈的纳什均衡比求解零和博弈要困难得多。

7-20

上图：Nash-Q：一种通用均衡学习器

  • Q函数可以通过一个与标准Q学习非常相似的随机近似过程来估计：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    初始化 Q(s, a) // a是联合行动
    初始化 s
    循环：
        aᵢ ← 从Q(s,a)导出的纳什策略的概率性结果 (混合了探索策略)

        为每个玩家i采取行动aᵢ，观察回报rᵢ，下一状态s'以及其他玩家的联合行动a₋ᵢ

        对于 i = 1...n:
            Qᵢ(s,(aᵢ,a₋ᵢ)) ← (1-α)Qᵢ(s,(aᵢ,a₋ᵢ)) + α(rᵢ + γVᵢ(s'))

        其中 V(s') = Nash([Q(s',a')]) // V是Q值博弈的纳什均衡价值

        s ← s'
    结束循环

    (左侧注释): 不再像Q学习中那样取“max”。

下图：Minimax-Q

  • Minimax-Q 被设计用于两人零和随机博弈。

    • — 在零和博弈中，只有一个均衡。
    • — 它可以使用线性规划来找到。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    初始化 Q(s, <a, o>) 和 π(s)  // a是自己的行动, o是对手的行动
    循环：
        a ← π(s) 的概率性结果 {混合了探索策略}

        采取行动a，观察回报r，下一状态s'和对手的行动o

        Q(s, (a, o)) ← (1-α)Q(s,(a,o)) + α(r + γV(s'))

        其中 V(s') = max_{π'∈PD(A)} min_{o'∈O} Σ_{a'∈A} π'(a'|s') Q(s', (a', o'))

        π(s) ← arg max_{π'∈PD(A)} min_{o'∈O} Σ_{a'∈A} π'(a'|s) Q(s, (a', o'))

        s ← s'
    结束循环

这两张幻灯片介绍了多智能体强化学习（MARL）中两种奠基石级别的“均衡学习器”算法：Nash-Q 和 Minimax-Q。它们的核心思想都是一致的：将单智能体Q学习中的 max 操作，替换为一次博弈论的“均衡求解”操作。

尽管思想一致，但它们分别针对不同类型的博弈，这导致了它们在实现和特性上的巨大差异。

  1. Nash-Q：更通用的“多面手”
  • 适用领域：两人一般和博弈。这是它的优势，因为它能处理更普遍的、合作与冲突并存的场景。
  • 核心计算：在每一步更新时，它都需要求解当前Q值矩阵的纳什均衡。这通常需要使用像二次规划 (QP) 这样的复杂优化工具。
  • 主要挑战：它最大的软肋在于，它假设在学习的每一步中，Q值博弈都恰好有唯一的纳什均衡。然而，一般和博弈经常出现多重均衡，这会让Nash-Q“不知所措”——它不知道应该用哪个均衡的价值来更新Q函数，从而可能导致学习过程不稳定或失败。
  1. Minimax-Q：更稳健的“专家”
  • 适用领域：两人零和博弈。这是它的局限，它只能用于利益完全对立的纯冲突场景。
  • 核心计算：在每一步更新时，它求解的是极大化极小值 (Maximin) 的解。这可以被高效地转化为一个线性规划 (LP) 问题来解决，计算上比二次规划更简单。
  • 主要优势：由于零和博弈的特性，其均衡价值（即博弈的价值V）是唯一且确定的。这彻底避免了Nash-Q遇到的多重均衡问题，使得Minimax-Q的理论基础更坚实，学习过程也更稳定。同时，它不仅更新Q值，还显式地更新了当前状态下的最优混合策略 π(s)。
  1. 对比总结

我们可以用一个表格来清晰地对比二者：

特点 / Feature Nash-Q Minimax-Q
适用领域 两人一般和博弈 (更通用) 两人零和博弈 (更专门)
核心计算 求解纳什均衡 求解极大化极小值
计算工具 二次规划 (QP) 线性规划 (LP)
均衡唯一性 不保证 (主要弱点) 保证 (主要优点)
优点 适用范围广 理论稳健，计算相对简单
缺点 依赖单一均衡假设，可能不稳定 只能用于纯冲突场景

结论：

Nash-Q 和 Minimax-Q 体现了多智能体学习中一个经典的权衡：通用性 vs. 稳健性。

  • Nash-Q 像一把瑞士军刀，尝试解决所有问题，但因为它所依赖的“单一均衡”假设过于理想化，所以在很多复杂情况下会“卡壳”。
  • Minimax-Q 像一把手术刀，只专注于零和博弈这一特定领域，但在该领域内，它的表现非常出色，理论保证强，结果稳定。

这两种早期的算法为后来的多智能体强化学习研究奠定了基础，许多现代算法都是在试图克服它们的局限（尤其是Nash-Q的多重均衡问题）的道路上发展起来的。

7.4 最佳对策

7-21

标题：多智能体学习器的期望性质 (Desired Properties of Multi-agent Learners)

  • 理性 (Rationality)：如果其他参与者的策略收敛到固定的策略，那么该学习算法也应收敛到一个作为对其他参与者策略的最佳应对 (best-response) 的策略。

  • 收敛性 (Convergence)：学习器必须能收敛到一个固定的策略。

    • — 定义：一个针对参与者 i 的学习算法是收敛的，当且仅当对于任何 ε > 0，都存在一个时间 T > 0，使得：

      对于所有 t > T, aᵢ ∈ Aᵢ, s ∈ S, 只要 P(s,t) > 0，就有 |P(aᵢ|s,t) - π(s,aᵢ)| < ε

    • — 其中 P(s,t) 是在时间t游戏处于状态s的概率，而 P(aᵢ|s,t) 是在时间t，给定游戏状态为s的条件下，该算法选择行动 aᵢ 的概率。

这张幻灯片为我们评估一个多智能体学习（MARL）算法的好坏，提出了两个至关重要的标准或“期望的品质”。这可以看作是一份给智能体学习算法的“成绩单”，我们希望它既“聪明”（理性），又“稳重”（收敛）。

  1. 理性 (Rationality)：抓住机会的能力
  • 它是什么？ “理性”指的是一个学习算法利用对手弱点的能力。这个性质保证了，如果你的对手们不再学习和改变，而是开始使用一套固定的、可预测的（甚至可能是很差的）策略，那么你的算法应该足够聪明，能够发现这一点，并最终学会那套能最大化自身利益的完美反制策略。
  • 为什么重要？ 这是一个智能体“智商”的基本体现。如果一个学习算法，连一个一成不变的、有明显弱点的对手都无法战胜，那它就算不上是一个好的学习算法。这个性质确保了智能体不会因为过于保守而错失良机。
  • 一个例子：在“石头剪刀布”中，如果你发现对手是一个只会出“石头”的“铁头娃”（一个固定的策略），那么一个具备理性的学习算法，其策略应该能很快地收敛到“永远出布”这个最佳应对上。
  1. 收敛性 (Convergence)：保持稳重的能力
  • 它是什么？ “收敛性”指的是，无论对手们在做什么（哪怕他们在混乱地学习、策略变来变去），我们自己的学习算法的策略也应该能最终稳定下来，而不是永远地摇摆不定或无限循环下去。
  • 为什么重要？ 这是稳定性和可预测性的保证。一个策略永远在振荡的智能体是不可靠的。我们希望我们的智能体，无论环境多么复杂，最终都能形成一套自洽的、固定的行为模式。没有收敛性，学习过程可能就只是一团毫无意义的混乱。
  1. “理性”与“收敛性”之间的核心矛盾

在多智能体学习的设计中，这两个看似都非常理想的性质，实际上经常是相互冲突的。设计一个能同时完美满足这两点的算法是极其困难的，这也是MARL领域的核心挑战之一。

  • 过于追求“理性”的风险：

    一个极度追求理性的智能体，会像一个“墙头草”，不断地去寻找对其他玩家当前策略的“最佳应对”。但问题是，其他玩家也在学习和变化。当你刚学会针对他们A策略的方法时，他们已经换成了B策略。这种永无休止的“追逐移动靶”，很容易导致策略的无限振荡，无法收敛。

  • 过于追求“收敛性”的风险：

    一个极度追求收敛的智能体，可能会像一个“顽固派”。它可能很快就锁定在一个“安全”的策略上（比如我们之前讨论的Minimax均衡策略），然后就一成不变，以确保自身的稳定。但这样做的代价是，即使它后来发现对手其实是个“铁头娃”，它也可能因为过于“稳重”而不愿意调整策略去利用这个弱点，从而失去了获得更高收益的机会，即丧失了理性。

总结：

“理性”和“收敛性”构成了评估多智能体学习算法的一对核心指标。一个理想的算法，应该像一个经验丰富的拳击手，既有自己稳定扎实的基本功（收敛性），又能敏锐地发现并利用对手的破绽（理性）。在MARL的研究中，如何在二者之间找到精妙的平衡，是设计出更强大、更通用的智能体的关键所在。

7-22

*（红色方框内的新增注释）*

收敛性通常是有条件的 (conditioned on)，其条件与其他参与者的学习算法有关。例如，相对于理性参与者的收敛，或是在自我博弈（self-play）（所有参与者都使用相同的算法）中的收敛。

这张幻灯片在上一张的基础上，对“收敛性”这个期望的性质增加了一个非常重要且符合现实的限定条件。它告诉我们，在复杂的多智能体世界中，我们通常无法奢求一个算法在任何情况下都保证收敛，而是会去证明它在某些特定的、合理的条件下是收敛的。

  1. 为什么“无条件收敛”过于苛刻？

上一张幻灯片中定义的“学习器必须收敛到一个固定策略”是一个非常强的、近乎理想化的要求。

  • 想象一下，你要设计一个学习算法，并保证它无论和谁博弈都能最终稳定下来。
  • 但如果你的对手是一个“捣乱者”，它的策略就是完全随机、毫无规律，甚至是故意要让你无法收敛呢？或者，如果你的对手也在学习，并且你们的互动陷入了一种类似“石头剪刀布”的无尽循环中呢？
  • 在这种情况下，强求你的算法单方面地“稳定下来”是不现实的，甚至可能是有害的（因为它会变得僵化，容易被利用）。

因此，在多智能体学习的研究中，学者们通常会退一步，去追求更有意义的“有条件收敛”。

  1. “有条件收敛”的两种典型情况

幻灯片中列举了两种最常见、也最重要的条件：

A. 相对于理性参与者的收敛 (Convergence with respect to rational players)

  • 含义：这个保证是说，“我的学习算法，在和一群同样是‘讲道理’、‘有理性’的玩家一起博弈时，是能够收敛的。”
  • 重要性：这证明了算法在一个“文明的”、可分析的多智能体环境中的稳定性。它排除了那些完全不可预测或恶意捣乱的对手，在一个更现实的“理性人”假设下，验证算法的可靠性。

B. 在自我博弈中的收敛 (Convergence in self-play)

  • 含义：这是目前多智能体强化学习研究中最常用的设定。“我的算法，在和它自己的克隆体进行博弈时，能够收敛到一个稳定的策略均衡。”
  • 重要性：这是一种“自我检验”。如果一个算法连和自己都玩不到一块儿去，学习过程都无法稳定，那很难说它是一个好的、可靠的算法。自我博弈创造了一个完美的、对称的实验环境，排除了因对手算法不同而带来的额外复杂性，让我们能纯粹地研究算法本身的动态特性。像 AlphaGo、AlphaStar 等许多著名的AI，其核心训练过程都是基于自我博弈。
  1. 总结：一个更务实的研究范式

这张幻灯片通过增加这个注释，向我们展示了科学研究中一个务实的思想：当一个问题在最普适的情况下难以解决时，我们可以先限定问题范围，在更有意义的特定条件下进行分析和证明。

  • 无条件收敛：是“圣杯”，非常理想，但可能无法实现。
  • 有条件收敛：是一个更实际、更有价值的“里程碑”。

在评估一个多智能体学习算法时，我们通常会问：“它能在自我博弈中收敛吗？”、“它能和理性学习者一起收敛吗？”、“它能收敛到好的均衡点上吗？”。一个算法能够提供的保证越强、越广泛，它就被认为越优秀。

7-23

标题：独立学习器（ILs）的困难 (Difficulty in Independent learners (ILs))

  • 假设其他智能体不在学习是不现实的。
  • 如果参与者1正在执行均衡策略，另一方可能会选择一个确定性策略并获得相同的回报。
  • 然而，一旦参与者2偏离了均衡，一个学习中的参与者1便可以利用这一事实，并采取某种能降低参与者2回报的策略。

图示文字翻译:

  • 右上角文字框: 参与者1利用了参与者2的确定性策略（注意 R2 = -R1）。
  • 右下角文字框: 参与者2偏离均衡，改为确定性策略，同时保持回报不变。
  • 图中: 标有“Nash”的点代表纳什均衡。

这张幻灯片非常深刻地揭示了为什么“独立学习器”（即每个智能体只顾自己学习，把对手当成环境背景）这种看似简单的方法，在实际中往往会失败。它描绘了一个“聪明的学习者”之间无法维持稳定均衡的动态过程。

我们可以把图中的动态过程分解为两步来理解：

第一步：参与者2的“安全”偏离

  1. 初始状态：我们从“Nash”点开始。这是一个混合策略纳什均衡。在这个均衡点，参与者1采取他的最优混合策略（比如50%出招A，50%出招B）。
  2. 无差异的诱惑：根据我们之前学到的“无差异原则”，当参与者1采取这个最优混合策略时，参与者2会发现，无论他选择“列1”还是“列2”，他的期望回报都是完全相同的。
  3. 参与者2的决策：他心想：“既然我怎么选，回报都一样，那我何必费劲去搞一个复杂的随机策略呢？我就一直出‘列1’（一个确定性策略）好了，省事而且结果也一样。”
  4. 图示：这对应了图中从“Nash”点出发的第一段横向箭头。参与者2的策略从混合策略变成了确定性策略，但因为无差异原则，他自己的回报（以及参与者1的回报）在这一刻保持不变。这看起来像是一次安全的、无害的简化。

第二步：参与者1的“理性”利用

  1. 发现机会：参与者1也是一个学习者，他会观察对手的行为。他很快就发现：“嘿！参与者2不再随机出招了，他现在只会出‘列1’，他的行为变得完全可预测了！”
  2. 调整策略：此时，参与者1会反思：“既然我已经知道他只会出‘列1’，那我原来的那个50/50混合策略还是最优的吗？” 答案显然是“不是”。参与者1会立刻放弃他原来的均衡策略，转而采取一个专门针对“列1”的、能让自己收益最大化的最佳应对策略。
  3. 图示：这对应了图中那条向上的、攀升的箭头。参与者1正在“爬”他的收益曲面，寻找针对参与者2这个固定策略的最高点。这个行动会极大地提高参与者1自己的回报R1。

后果：均衡的崩溃

由于这是一个零和博弈（R2 = -R1），当参与者1的收益R1达到新的高峰时，就意味着参与者2的收益R2跌入了谷底。参与者2会发现，他最初那个看似“安全”的偏离行为，最终给自己带来了灾难性的后果。

接下来，一个学习中的参与者2会立刻放弃他那个被剥削的确定性策略，从而开始新一轮的策略调整。

总结：

这张幻灯片描绘了一个“信任的瓦解”过程。独立学习器无法形成稳定的合作（这里的合作指共同维持纳什均衡），因为：

  1. 纳什均衡的“无差异”特性，为其中一方“偷懒”或“偏离”提供了最初的动机。
  2. 独立学习器天生就具有“利用”对手的倾向，它会把对手任何可预测的行为都当作环境中的一个可利用的“漏洞”。
  3. 这种“偏离-利用-反制”的循环，使得双方的策略在纳什均衡点附近不停地追逐和振荡，但永远无法真正稳定下来。

这正是独立学习范式的根本缺陷，也解释了为什么需要发展那些能明确处理智能体间互动的、更复杂的联合行动学习器（如Nash-Q）。

7-24

这张幻灯片进一步深入探讨了联合行动学习器 (Joint Action Learners, JALs) 的核心机制以及它们在现实中所面临的关键挑战。

  1. JAL 的核心思想回顾

JAL 的基本哲学是“直面博弈”，它承认在一个多智能体系统中，任何结果都由所有人的联合行动决定。因此，它的核心数据结构是一个基于联合行动的Q表格：Qi(s,a)，其中 a=(ai,a−i) 包含了自己和他人的行动。

  1. JAL 的两大实践挑战

幻灯片指出了将JAL付诸实践的两个主要障碍：

挑战一：完全可观测性的要求

  • 问题：为了更新 Qi(s,(ai,a−i)) 这个值，智能体 i 在行动之后，不仅需要知道自己做了什么 (aᵢ)，还需要准确地观察到所有其他参与者刚才做了什么 (a₋ᵢ)。
  • 现实：在许多真实场景中，这个要求过于苛刻。例如，在商业竞争中，你可能知道自己的营销策略，也知道最终的市场份额变化，但你很难知道每一个竞争对手具体采取了什么内部策略。这种信息的缺失（即部分可观测性）使得最基础的JAL算法难以应用。

挑战二：参与者的异质性 (Heterogeneity)

  • 问题：像 Nash-Q 这样的均衡学习器，往往隐含地假设“我的对手也和我一样聪明，也在试图计算并执行纳什均衡”。
  • 现实：你的对手可能是五花八门的。他可能是一个正在学习的新手，一个遵循固定规则的“机器人”，或者一个完全非理性的玩家。你无法保证所有人都处在同一个“频道”上。当对手的行为模式不符合你的“理性人”假设时，你计算出的均衡策略可能就不是最优的。
  1. 核心决策机制：对他人建模

面对这些挑战，JAL 在做决策时通常采用一种更务实的方法，也就是幻灯片里给出的那个公式。这个公式背后的思想是“对其他参与者建模 (Opponent Modeling)”。

EV(ai)=a−i∈A−i∑Q(⟨ai,a−i⟩)j=i∏π^j(a−i[j])

我们可以这样解读这个决策过程：

  1. “如果我选择行动aᵢ…”：智能体 i 会在心里盘算自己的每一个可选行动 aᵢ。
  2. “…其他人可能会怎么做？”：它会根据自己对其他人的观察，为每一个对手 j 建立一个策略模型 π^j。这个模型预测了“对手j有多大概率会出什么招”。这可能通过统计他们过去的行为频率来学习。
  3. “…那么我的期望收益是多少？”：它会遍历所有其他人可能的行动组合 a₋ᵢ，用自己学到的Q值 Q(s,(ai,a−i)) 乘以自己预测的“这种情况发生的概率” ∏π^j，然后求和。这就得到了采取行动 aᵢ 的总期望价值 EV(ai)。
  4. 最终决策：计算出所有自己可选行动的EV值后，选择那个期望价值最高的行动来执行。

总结：

JALs 提供了一个理论上更完备的MARL框架，但代价是面临着观测和扩展性的巨大挑战。幻灯片中的公式揭示了一种核心的实践方法：通过学习对手的模型来指导自己的决策。这使得 JAL 的研究分化为两个主要方向：一部分继续研究如何高效地进行均衡计算（如Nash-Q），另一部分则专注于如何更准确、更高效地进行对手建模，这两者共同推动着多智能体学习领域的发展。

7-25

这张幻灯片介绍了一类与“均衡学习器”（如Nash-Q）思想相对的、更具适应性的多智能体学习方法——对手建模 (Opponent Modeling)。这种方法的经典形式也被称为虚拟博弈 (Fictitious Play)。

  1. 核心思想：“经验主义” vs. “理论主义”

我们可以把这两类学习器的哲学思想做一个对比：

  • 均衡学习器 (如Nash-Q)：这是一个“理论主义者”。它假设对手是完全理性的博弈论家，其目标是计算出游戏抽象的、理论上的“纳什均衡”，然后去执行它。
  • 对手建模学习器：这是一个“经验主义者”。它不对对手做过高的理性假设，而是采取一种更务实的态度：“我不管你理论上该怎么玩，我就看你实际上是怎么玩的。” 它的目标是：
    1. 通过观察，学习并建立一个关于对手行为模式的统计模型。
    2. 计算并执行针对这个“模型”的最佳应对策略。
7-26
  1. “巨型对手”假设的含义

红色注释指出了这个特定算法实现的一个简化之处：它把所有其他参与者 a₋ᵢ 打包看作是一个“巨型对手”。它统计的是对手们“集体上”做了什么，而不是去为每一个对手 j 单独建模。

  • 优点：简化了问题，需要维护的计数器更少。
  • 缺点：模型较为粗糙，无法捕捉不同对手之间的个性化差异或他们之间可能存在的联动关系。更高级的对手建模算法会为每一个对手分别建立策略模型。
  1. 优缺点分析
  • 优点：
    • 满足“理性”：这种方法的核心就是计算最佳应对，所以它天生就满足我们之前讨论的“理性”性质。如果对手采取一个固定的、有漏洞的策略，这个算法能很快地学习到并加以利用。
    • 计算更简单：在决策时，它只需要做一次期望值计算，而不需要像Nash-Q那样在每一步都去求解一个复杂的均衡（如二次规划），计算上更高效。
  • 缺点：
    • 不保证“收敛”：这是它最大的问题。它假设对手的策略是固定的，但如果对手也是一个同样的学习者，双方就会陷入“你根据我的历史来预测我，我根据你的历史来预测你”的循环。在很多非零和博弈中（比如石头剪刀布），这种相互预测和应对会导致双方的策略永远振荡，无法收敛到纳什均衡。
    • 学习滞后：如果对手的策略变化很快，这种基于历史频率的建模方法会存在明显的滞后，导致它总是在应对一个“过去的”对手，从而表现不佳。

总结：

对手建模/虚拟博弈是多智能体学习中一种非常重要且直观的方法。它放弃了均衡学习器对“完美理性”的强假设，转而采用一种数据驱动、经验主义的方式来学习和适应。它的优势在于能够利用对手的弱点（满足理性），但代价是牺牲了收敛性的保证。