Sequential Elimination and Union Shapley Value for Group Assessment in Coalitional Games

技术摘要：联盟博弈中群体评估的序贯剔除与并集沙普利值

问题陈述
在合作博弈论及相关领域（如网络中心性和机器学习数据估值）中，一个根本性挑战是将个体玩家评估扩展至群体。现有方法通常依赖两种直接途径：

1. 求和：聚合个体值（例如，沙普利值之和）。这忽略了合作的基础结构以及玩家之间的依赖关系。
2. 合并：将群体视为单一合并元素并对其进行评估（例如，合并沙普利值）。这会改变博弈结构，且无法区分独立玩家与高度依赖玩家。

这两种方法通常无法准确捕捉群体内部的依赖关系。例如，在一个由两对互不相交的玩家独立产生价值的博弈中，对个体值求和或合并群体可能会错误地赋予一对合作玩家与一对独立玩家同等的权重，未能反映其系统性影响的不对称性。

方法论
作者提出并分析了一种基于序贯剔除的第三种途径。在该框架下，群体中的元素被逐一移除，并在由此产生的简化博弈中聚合其评估值。核心假设是，这种方法通过剔除重叠效应并聚焦于群体缺席所造成的损害，自然地衡量了群体的净贡献。

本研究基于对联盟博弈中群体值的全面公理化分析。方法论包括：

• 定义公理类：作者引入了一类群体（弱一致）半值。这些群体值满足线性性、对称性、弱单调性、零玩家剔除和哑玩家公理。他们还定义了一类相应的协同半值，用哑化玩家公理（由 Grabisch 和 Roubens 提出）替代了哑玩家公理。
• 序贯扩展：论文确立了玩家值存在序贯扩展当且仅当其满足平衡贡献性质。已证明，每个一致半值（满足零玩家剔除）都 admits 唯一的序贯扩展。
• 势函数：作者利用 Hart 和 Mas-Colell 引入的势函数来刻画沙普利值的序贯扩展。

主要贡献与结果

1. 并集沙普利值：
   作者引入了并集沙普利值作为沙普利值的唯一序贯扩展。其定义为原博弈的势与群体移除后博弈的势之差：
   $$US_S(N, v) = P(N, v) - P(N \setminus S, v) = \sum_{T \subseteq N, S \cap T \neq \emptyset} \frac{\Delta v(T)}{|T|}$$
   其中 $\Delta v(T)$ 为 Harsanyi 红利。

• 解释：该值衡量了群体离开时对博弈造成的“损害”。它聚合贡献，使得每个联盟的红利最多被计算一次，即使该群体包含该联盟的多个成员。
• 公理化：并集沙普利值由势（或平衡贡献）公理与效率公理唯一刻画。在群体半值中，它也由群体平等公理（在一致博弈中所有群体同等重要）唯一刻画。

2. 群体值的公理分类：
   论文区分了群体评估的两种变体：

• 总价值：评估群体总价值的值（例如，求和扩展、合并沙普利值、并集沙普利值）。这些由群体半值捕捉。
• 协同：衡量群体协同效应的值（例如，交互指数）。这些由协同半值捕捉。
  作者提供了这两类之间的函数对应关系。具体而言，他们表明合并沙普利值对应于交互指数（一种协同对应物），而并集沙普利值对应于一种新的协同值，称为交集沙普利值。

3. 交集沙普利值：
   定义为包含整个群体的联盟的红利之和：
   $$IS_S(N, v) = \sum_{S \subseteq T \subseteq N} \frac{\Delta v(T)}{|T|}$$
   该值衡量贡献的交集。对于大小为二的群体，并集沙普利值与交集沙普利值之和等于个体沙普利值之和：
   $$US_{\{i,j\}}(N, v) + IS_{\{i,j\}}(N, v) = SV_i(N, v) + SV_j(N, v)$$
   这种分解允许将群体的联合价值分离为“并集”部分（仅计算一次贡献）和“交集”部分（协同效应）。

4. 与现有工作的比较：
   该分析阐明了所提出的值与现有文献之间的关系：

• 合并沙普利值（Marichal 等人）被证明是满足哑联盟公理的唯一群体半值。
• 交互指数（Grabisch 和 Roubens）被识别为一种协同半值，与群体半值不同，因为它违背了标准的哑玩家公理，转而采用哑化玩家公理。
• 论文证明，序贯扩展方法在理论上具有稳健性，因为它适用于所有一致半值，并产生具有强公理性质的值。

意义
论文声称，序贯扩展方法，特别是并集沙普利值，构成了将玩家值扩展至联盟博弈中群体的最自然且理论根基最深厚的途径之一。通过区分评估总价值与衡量协同效应，作者提供了一个统一的框架，阐明了文献中现有概念之间的差异。引入并集和交集沙普利值为分析交互作用提供了新工具，特别是在需要剔除贡献重叠（并集）或需要隔离纯协同效应（交集）的场景中。该工作确立了这些值并非任意的启发式方法，而是由平衡贡献、势和群体平等等基本公理唯一确定的。