🤖 AI

Learning Strategic Value and Cooperation in Multi-Player Stochastic Games through Side Payments

本文引入并分析了适用于带侧支付的多人随机博弈的两种新颖价值概念HS-S与Coco-S，确立了它们的公理基础，证明了它们在双人情形下的等价性，同时展示了它们在更大规模群体中的分歧，并提供了计算这些价值概念的算法及其实证验证。

原作者： Yixin Chen, Jeffrey Richley, Darleen Perez-Lavin, Jessica Singh Syal, Solmaz Kia, Alan Kuhnle

发布于 2026-05-12

📖 1 分钟阅读☕ 轻松阅读

原作者： Yixin Chen, Jeffrey Richley, Darleen Perez-Lavin, Jessica Singh Syal, Solmaz Kia, Alan Kuhnle

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

想象一群朋友试图决定如何分披萨，但情况比简单的单次切割要复杂得多。他们正在玩一款视频游戏，在地图上移动，每秒做出决策，而获得的奖励取决于接下来发生的事。有时他们需要合作以赢得大奖，有时他们则相互竞争。

这篇论文提出的核心问题是：在长期中，如何公平地决定每个人应得多少，特别是如果他们被允许通过互相支付金钱（side payments）来使合作变得有利可图？

以下是用简单类比对论文思想的分解：

1. 问题：“公平份额”谜题

在简单游戏中，我们有公平规则（如沙普利值）。但在复杂、动态的游戏（称为随机博弈）中，情况变得混乱。

问题所在：如果你只看当下，可能会认为玩家 A 是最强的。但如果纵观整个未来，玩家 B 可能是那个真正能迫使其他人合作的人。
目标：作者希望为每位玩家创建一个“战略价值”。你可以将其视为未来影响力的信用评分。它确切地告诉你，基于你在整个游戏中威胁或帮助他人的能力（而不仅仅是当下），你加入一个团队应获得多少报酬。

2. 两种解决方案：“长远视角”与“分步视角”

这篇论文提出了两种计算这种公平价值的方法。它们就像两个不同的导航应用，试图带你到达同一个目的地，但走了不同的路线。

方案 A：HS-S（“长视野”规划者）

类比：想象一位能预见未来 20 步的国际象棋特级大师。他们计算每一种可能的未来场景，其中一组玩家联手对抗世界其余部分。他们会问：“如果这个群体在剩余的游戏时间里对抗所有人，他们能保证赢得多少？”
运作方式：它将游戏分解为针对每一种可能团队组合的微小“假设”场景。它计算每个团队在整个未来中对抗其他所有团队的“威胁力量”。
结果：它基于游戏终极的权力动态，给出一个非常稳定、公平的数值。它遵循数学家几十年来公认的一套严格公平公理。

方案 B：COCO-S（“分步”导航器）

类比：想象一个在每个路口都重新计算路线的 GPS。它不是同时展望未来 20 步，而是问：“如果我们此刻就在这个路口，基于我们接下来能去哪里，最公平的分配是什么？”它达成一笔交易，迈出一步，然后立即为下一步重新评估这笔交易。
运作方式：它将公平规则应用于当前时刻，假设未来价值已知，然后检查这些未来价值是否合理。这是一个“自洽”的循环。
结果：它更容易计算，并给出了关于在游戏每一步确切交换多少金额的清晰指令。

3. 重大发现：它们何时一致？

论文发现了这两种方法之间一个有趣的差异：

在双人博弈中：它们是相同的。如果你和我在玩游戏，两种方法都会给出完全相同的“公平份额”和完全相同的侧向支付。
在三人及以上博弈中：它们分道扬镳。
- 原因：“长视野”规划者（HS-S）关心一个群体在整个游戏中的总权力。而“分步”导航器（COCO-S）关心玩家在当前时刻拥有的即时杠杆。
- 反例：作者构建了一个特定的三人博弈，其中两种方法意见不一。在这个游戏中，分步方法可能认为玩家 A 值 10 美元，而长视野方法认为他们值 15 美元。根据各自的规则，两者都是“公平”的，但它们对“公平”的定义略有不同。

4. “侧向支付”协议

这篇论文不仅计算数字，还告诉你如何支付。

机制：在游戏的每一步，玩家同意采取能最大化总群体奖励的行动。
转移：然后，他们交换金钱（侧向支付），使每个人最终恰好获得其计算出的“战略价值”。
类比：想象一群朋友去公路旅行。他们决定走最快的路线（最大化节省的总时间）。但其中一位朋友必须全程驾驶，另一位必须负责导航。“战略价值”计算导航员应向驾驶员支付多少金额以使其公平。论文提供了在每一个里程标记处进行此交易的精确数学公式。

5. 实用性：“采样”技巧

精确计算这些价值就像试图数清海滩上的每一粒沙子——如果玩家太多，这太难了。

解决方案：作者表明你不需要数清每一粒沙子。你可以随机抽取“假设”场景（联盟）的样本，从而获得非常准确的估计。
优势：这使得数学运算速度快到足以在计算机上运行多玩家游戏，这是人工智能和多智能体系统的一大进步。

总结

这篇论文解决了“在玩家可以互相支付的复杂动态游戏中，我们如何公平地分配战利品？”的问题。

它提供了两种有效的公平计算方法：一种着眼于整个未来（HS-S），另一种着眼于紧接着的下一步（COCO-S）。
当只有两名玩家时，它们是一致的；但当有三名或更多玩家时，它们会产生分歧，揭示了复杂群体中的“公平”具有两个截然不同但数学上合理的定义。
它为AI 智能体提供了一套实用的方案，使其能够合作、计算自身价值，并交换支付，以确保每个人在每一步都对交易感到满意。

技术摘要：通过侧支付在多智能体随机博弈中学习战略价值与合作

1. 问题陈述

本文探讨了在具有可转移效用的一般和、多智能体随机博弈中，定义和计算单智能体长期战略价值的挑战。在智能体可以利用侧支付（如合同、信用）来稳定互惠行为的场景中，核心问题不仅仅是识别均衡策略，而是确定如何分配长期价值，使得合作对每个智能体而言都是个体理性的。

现有的解决方案概念无法满足这一特定目的：

极小化极大值（Minimax values） 仅限于零和、双智能体场景。
沙普利值（Shapley values） 适用于具有可转移效用的合作博弈，但需要为每个联盟定义特征函数，且无法固有地捕捉非合作博弈中产生的战略威胁。
多智能体一般和随机博弈中的纳什均衡与相关均衡 往往存在非唯一性、计算不可行性，以及缺乏针对侧支付的、可分解为合作与竞争分量的特性。
Coco 值（Kalai & Kalai, 2013）及其随机扩展（Coco-Q） 为双智能体博弈提供了令人信服的分解，但无法直接推广到 $n > 2$ 的情况，且缺乏具有可比性的公理化特征。

作者旨在将哈萨尼 - 沙普利（HS）值（该值通过联盟对补集的零和博弈来定义联盟的“威胁力”）扩展到随机博弈的动态环境中。核心的技术障碍在于，在随机博弈中，威胁和机会通过状态转移传播，使得“联盟价值”成为一个依赖于状态的长期对象，而非单一标量。

2. 方法论

本文引入了两种基于 HS 的随机博弈价值概念，当博弈仅包含单一状态时，两者均退化为标准形式的 HS 值。

2.1 HS-S（联盟分解）

HS-S 通过聚合整个未来的动态联盟威胁力，提升了标准形式的 HS 公式。

机制： 对于每个非平凡联盟 $I \subseteq N$ ，作者构建了一个由 $I$ 与其补集 $\bar{I}$ 参与的诱导双智能体零和随机博弈。他们计算威胁力 $\delta_G(I, x)$ ，定义为该零和博弈贝尔曼算子的唯一不动点（即联盟 $I$ 能确保对抗 $\bar{I}$ 的极大极小值）。
聚合： 状态 $x$ 下智能体 $i$ 的 HS-S 值是这些威胁力的加权和，使用权重为标准的沙普利式权重：
$V^{HS-S}_i(x) = \frac{1}{n} \sum_{I \subseteq N: i \in I} \binom{n-1}{|I|-1}^{-1} [\delta_G](I, x)$
公理： 作者将 Kohlberg–Neyman 公理（效率、对称性、可加性、零玩家、个体理性及平衡威胁）扩展到了随机环境。他们证明了HS-S 是满足这些公理的唯一映射（其中“平衡威胁”被放宽为“弱平衡威胁”）。

2.2 COCO-S（贝尔曼算子）

COCO-S 采用了一种“动态规划风格”的方法，在每个状态局部应用标准形式的 HS 计算。

机制： 对于候选价值函数 $V$ ，作者在每个状态 $x$ 定义了一个局部标准形式博弈 $H_x(V)$ 。 $H_x(V)$ 中的收益包含了即时奖励以及基于 $V$ 的折扣后延续价值。
算子： 他们定义了一个贝尔曼风格的算子 $\tilde{T}$ ，其中 $[\tilde{T}(V)](x) = HS(H_x(V))$ 。COCO-S 值定义为该算子的不动点： $V = \tilde{T}(V)$ 。
性质： 该构造推广了双智能体 Coco-Q 算子。作者证明了所有有限随机博弈中不动点的存在性，并通过拓扑度理论和谱条件确立了双智能体博弈及三智能体双状态博弈中的唯一性。

2.3 比较与分歧

双智能体情况： 当 $n=2$ 时，HS-S 和 COCO-S 重合。两者均满足完整的 HS 公理集。
多智能体情况（ $n > 2$ ）： 两种价值发生分歧。作者提供了一个明确的三智能体反例，其中 $V^{HS-S} \neq V^{COCO-S}$ $V^{H S - S} \neq = V^{C O C O - S}$ 。
- HS-S 满足弱平衡威胁，但违反马尔可夫一致性（状态下的价值取决于无限视野的威胁力，而不仅仅是具有自洽延续的局部博弈结构）。
- COCO-S 满足马尔可夫一致性（状态下的价值由将 HS 公式应用于具有自洽延续的局部博弈决定），但违反弱平衡威胁。

2.4 实际计算

为了解决评估所有 $2^n$ 个联盟带来的组合爆炸问题，本文提出了基于采样的估计器：

HS-S 估计： 对采样的联盟威胁力进行一次性蒙特卡洛聚合。
COCO-S 估计： 一种迭代值迭代算法，其中 HS 算子通过在每一步进行联盟采样来近似。算子的收缩特性抑制了早期迭代的采样误差。
复杂度： 两种估计器均实现了 $\tilde{O}(n^2)$ 的采样复杂度，并具有有限样本保证。

3. 主要贡献

两种基于 HS 的价值概念： 定义了适用于一般和、 $n$ 智能体随机博弈的 HS-S（通过动态联盟分解）和 COCO-S（通过贝尔曼风格算子）。
公理化特征：
- 证明了HS-S是满足效率、对称性、可加性、零玩家、个体理性和弱平衡威胁的唯一价值。
- 证明了COCO-S是满足关于哈萨尼 - 沙普利值的马尔可夫一致性的唯一价值。
结构分析： 展示了两种价值在 $n=2$ 时重合，但在 $n > 2$ 时发生分歧，这种分歧源于满足弱平衡威胁（HS-S）与马尔可夫一致性（COCO-S）之间的权衡。
存在性与唯一性： 证明了 COCO-S 不动点的存在性（通过布劳威尔定理），并通过拓扑度理论证明了特定类别博弈（双智能体、三智能体双状态）的唯一性。
实施协议： 推导了基于 COCO-S 值的动态侧支付协议。在每个状态下，合作行动最大化总收益，且预算平衡的转移支付确保每个智能体的期望收益等于其 COCO-S 值。
实证验证： 在多智能体网格博弈（广义囚徒困境、协调博弈、敌友博弈等）上进行了评估。结果表明，两种方法都能产生合理的战略价值和侧支付，通常在相对智能体强度上达成一致，但在名义数值上存在差异。COCO-S 在值迭代中表现出稳健的收敛性，而相关均衡（Correlated-Q）在多智能体设置中经常无法收敛。

4. 结果

收敛性： 使用 COCO-S 算子的值迭代在所有测试基准中均稳健收敛。相比之下，相关均衡（CE）在一般和多智能体一般和博弈中经常无法收敛。
侧支付： COCO-S 产生的状态级侧支付可解释为局部盈余的再分配。HS-S 侧支付在策略层面是连贯的，但可能会将遥远状态的价值归因于当前状态。
可扩展性： 基于采样的估计器显著减少了计算时间（例如，从枚举 4,096 个联盟减少到采样 3,000 个），同时保持了较小的估计误差。在一个 12 智能体双状态博弈中，COCO-S 采样实现的绝对偏差最大值小于 HS-S 采样。
分歧： 在非对称博弈（如敌友博弈）中，HS-S 和 COCO-S 在智能体的名义强度上可能存在显著分歧，反映了它们对威胁视野的不同处理方式。

5. 意义与主张

本文声称提供了在多智能体战略环境中支持理性侧支付所缺失的对象：一种适用于随机博弈的、有原则的、公理化的单智能体战略价值。

理论贡献： 确立了将哈萨尼 - 沙普利值扩展到随机博弈的两种不同且定义明确的方式，其区别在于它们满足的公理（弱平衡威胁 vs. 马尔可夫一致性）。这澄清了动态环境中合作解概念的全景。
实践贡献： 提供了一个计算上可行的框架（通过 COCO-S 和采样），用于计算价值并生成使合作个体理性的侧支付协议。
局限性与未来工作： 作者谦逊地指出，COCO-S 对于一般 $n$ 和 $m$ 的唯一性依赖于一个谱条件，该条件虽经数值验证，但尚未对所有有限随机博弈得到证明。他们还指出，将这些特征扩展到无限状态空间以及开发更高效的采样估计器是开放的研究方向。

这项工作并未声称解决所有多智能体学习问题，而是专门针对可转移效用环境中的价值分配，以通过侧支付来论证和实施合作。