技术摘要：由有向网络定义的一类可解合作博弈

问题陈述

本文探讨了合作博弈论中固有的计算与分析挑战，特别是由加权有向图诱导的博弈。合作博弈通常面临相对于参与者数量呈指数级增长的表示规模，使得解概念（如沙普利值和班扎夫值）及稳定性属性（如核心）的计算变得不可行（在许多情况下为#P 完全问题）。

尽管先前的研究已探讨了由无向图或特定子类（如加权投票博弈）诱导的博弈，但仍需要定义由有向网络构成的结构化博弈类，使其在分析和计算上保持可解。作者引入了一类特定的博弈，称为“信任博弈”，其中联盟价值由内部互动和外部暴露共同决定。主要挑战在于为解概念推导闭式多项式时间公式，并刻画这些博弈的稳定性属性，特别是考虑到外部分量引入了非加性的、类似瓶颈的行为。

方法论

作者定义由加权有向图 $G = (N, E)$ 诱导的信任博弈 $(N, v)$，其中边权重 $a_{ij} \in [0, 1]$。联盟 $S \subseteq N$ 的价值定义为两个分量之和：

1. 内部项：所有满足 $i, j \in S$ 的边 $(i, j)$ 的权重之和。这对应于诱导子图博弈。
2. 外部项：对于 $S$ 中每个拥有来自 $S$ 外部入边的参与者 $i$，价值包含这些入边权重的最小值。如果 $S$ 中的某参与者没有来自外部的入边，则该项贡献为 0。

数学表达如下：
$$v(S) = \sum_{i \in S, j \in S, (i,j) \in E} a_{ij} + \sum_{i \in S^*} \min_{j \notin S: (j,i) \in E} a_{ji}$$
其中 $S^*$ 是 $S$ 中至少拥有一条来自 $N \setminus S$ 的入边的参与者集合。

为了分析该博弈，作者采用莫比乌斯变换将博弈分解为** unanimity 博弈**（$u_T$）的线性组合。

• 内部分量较为直接，涉及成对的 unanimity 博弈。
• 外部分量由于 $\min$ 算子而更为复杂。作者按非递减顺序对每个参与者 $i$ 的入邻居进行排序。他们证明，参与者 $i$ 的外部博弈可以表示为 unanimity 博弈的伸缩和，其中支撑集形成由入邻居排序决定的包含链。

这种分解使作者能够利用沙普利算子和班扎夫算子的线性性质，推导出显式公式。

主要贡献与结果

1. Unanimity 分解

本文建立了信任博弈的闭式 unanimity 分解。

• 引理 2.3：参与者 $i$ 的外部博弈 $w_i(S)$ 被分解为 unanimity 博弈 $u_{T_i(t)}$ 之和，其中 $T_i(t)$ 由参与者 $i$ 及其前 $t-1$ 个入邻居（按权重排序）组成。系数为排序后的边权重之差。
• 引理 3.2：总博弈 $v(S)$ 是内部成对 unanimity 博弈与分解后的外部 unanimity 博弈之和。

2. 多项式时间解概念

利用 unanimity 分解，作者推导出了以下显式多项式时间公式：

• 沙普利值（$\phi_i$）：该值表示为三部分之和：
  1. 内部边权重的平均值（对称加权度中心性）。
  2. 源自参与者 $i$ 自身入边的项（外部暴露）。
  3. 源自指向 $i$ 的出邻居的入边的项（共享邻居效应）。
     公式（定理 3.1）明确考虑了每个参与者在他人的入邻居中的排名。
• 班扎夫值（$\beta_i$）：同样推导出了闭式公式（定理 4.2），利用了 unanimity 博弈的特定班扎夫值（$2^{1-|T|}$）。

3. 边际效应分析

本文分析了边权重的局部变化如何影响解值。

• 引理 3.5 与 4.3：边权重 $a_{kj}$ 对参与者价值的边际效应取决于该参与者相对于该边的位置：
  • 内部边：对沙普利值和班扎夫值均呈线性贡献。
  • 外部边：效应是非线性的，取决于该参与者在目标节点入邻居中的排名。对于沙普利值，效应涉及 $\frac{1}{r(r+1)}$ 等项，而班扎夫值涉及 $\frac{1}{2^r}$。
• 零参与者刻画：引理 3.6 提供了参与者为零参与者（价值为 0）的充要条件，即该参与者没有入边，或者其入边来自在特定结构意义上本身即为零的参与者。

4. 稳定性与核心属性

作者调查了信任博弈的稳定性：

• 核心刻画（引理 5.1）：信任博弈的核心是单点集。它由唯一的分配组成，其中每个参与者 $i$ 获得来自整个图的所有入边权重之和（$\sum_{j} a_{ji}$）。
• 完全平衡性（引理 5.2）：该博弈是完全平衡的，意味着每个子博弈（限制于任何联盟 $S$）都具有非空的核心。这是通过为任何子博弈构造显式核心分配来证明的。
• 概念的 divergence：本文强调，基于总入权重的唯一核心分配通常不与沙普利值或班扎夫值重合。这展示了一个稳定性导向的分配与基于公平性的解概念发生分歧的设定。

意义与主张

本文声称提供了一个结构化网络诱导合作博弈的可解示例。其意义在于：

1. 计算可解性：它提供了一类博弈，其中解概念（沙普利值、班扎夫值）和稳定性属性（核心）可在多项式时间内计算，避免了通用合作博弈典型的指数级复杂度。
2. 结构洞察：Unanimity 分解揭示，外部分量中复杂的“最小值”算子创建了一个嵌套的 unanimity 博弈链，使得该博弈在分析上易于处理。
3. 理论区分：它明确展示了一种场景，即尽管博弈是完全平衡的，但核心（稳定性）与沙普利值（公平性/边际贡献）产生了不同的分配。
4. 未来工作的基础：作者建议此类博弈可作为探索参数化推广、外部分量替代聚合规则以及关于激励相容的机制设计问题的基准。

该工作并未提出新的实验应用，而是建立了一个理论框架，用于分析具有非对称局部评估的有向网络中的合作互动。