Lec 4: 合作博弈与数据估值⚓︎

从非合作博弈到合作博弈⚓︎

分摊美元博弈⚓︎

合作博弈⚓︎

更通俗地说，合作博弈的解概念就是一个将每个博弈都映射到一个可行的收入分配集合的函数，这个集合中的每个元素是一个分配向量 \((x_1, x_2, \dots, x_n)\)，其中 \(x_i\) 表示参与者 \(i\) 在当前分配下可以获得的收入。

核⚓︎

例子

例 1 例 2

题目解答

求下列三个参与人的合作博弈的核，其中 \(N = \{1, 2, 3\}\)，特征函数 \(v\) 的定义如下：

\[ v(\emptyset) = v(\{1\}) = v(\{2\}) = v(\{3\}) = 0, \\ v(\{1, 2\}) = v(\{2, 3\}) = 1, v(\{1, 3\}) = 2, v(\{1, 2, 3\}) = 3 \]

直接设出在核中的向量 \(x = (x_1, x_2, x_3)\)，并根据核的定义，这一向量应当满足有效率的：

\[ x_1 + x_2 + x_3 = v(\{1, 2, 3\}) = 3 \]

以及联盟理性，即：

\[ x_1 + x_2 \ge v(\{1, 2\}) = 1, x_2 + x_3 \ge v(\{2, 3\}) = 1, x_1 + x_3 \ge v(\{1, 3\}) = 2, \\ x_1 \ge v(\{1\}) = 0, x_2 \ge v(\{2\}) = 0, x_3 \ge v(\{3\}) = 0 \]

接下来的关键问题在于如何求出符合上述等式与不等式的所有向量．事实上，有效率性已经将 \(x\) 限制到 \(\mathbb{R}^3\) 中的一个平面，然后我们只需将这些不等式约束在这一平面上处理即可。

考虑三个参与人的合作博弈，\(N = \{1, 2, 3\}\)，特征函数 \(v\) 定义如下：

\[ v(\emptyset) = v(\{1\}) = v(\{2\}) = v(\{3\}) = 0, \\ v(\{1, 2\}) = v(\{1, 3\}) = v(\{2, 3\}) = v(\{1, 2, 3\}) = 1 \]

设核中向量为 \(x = (x_1, x_2, x_3)\)，基于下面这一简单的观察发现核为空集：

• 根据有效率的，我们有：

  \[ x_1 + x_2 + x_3 = v(\{1, 2, 3\}) = 1 \]

• 但根据联盟理性，由于 \(v(\{1, 2\}) = v(\{1, 3\}) = v(\{2, 3\}) = 1\)，因此 \(x_1 + x_2 \ge 1, x_2 + x_3 \ge 1, x_1 + x_3 \ge 1\)，于是我们有： $$ 2x_1 + 2x_2 + 2x_3 \ge 3 $$

显然这两个不等式是矛盾的，因此这一博弈的核为空集。

沙普利值的性质⚓︎

为了定义出沙普利值，我们首先需要写出沙普利值应当满足的效率和公平性质，然后给出定义并证明其唯一性．为了便于形式化地描述下面的沙普利性质，首先给出如下记号上的定义：

即所有参与者分完了整个联盟的全部收入，事实上这与核的要求一致，这一条件是理性参与者一定会希望满足的。

第二个性质是对称性，这一性质是公平性的关键．为了定义对称性，需要首先定义两个参与人什么时候是对称的：

用通俗的话说，两个参与人是对称的，即对于任何不包含他们的联盟，二者分别加入这一联盟后，联盟增加的效用（或称边际贡献(marginal contribution)）是一致的，因为对称性的定义等价于 \(v(S \cup \{i\})− v(S) = v(S \cup \{j\})− v(S)\)。

零参与者性质表明，如果一个参与人对于任何联盟的加入都不会增加联盟的效用，即他的边际贡献永远为 0，那么他获得的收入应当为 0。

沙普利值的定义⚓︎

上面的定义能满足除了对称性以外的所有性质，这时我们心里应当有一个强烈的声音告诉我们，这里的不对称性来源于强制给定了这 \(n\) 个参与人的排序，而不同的排序可能会带来不同的分配结果，因此自然的想法是：为什么不尝试把所有的排序对应的结果取平均呢？记这 \(n\) 个参与人的全体排序构成的集合为 \(S_n\)，根据简单的组合知识可知这一集合中含有 \(|S_n|= n!\) 个元素．对于任意排序 \(\sigma \in S_n\)，定义：

即在排序 \(\sigma\) 下位于参与人 \(i\) 前面的所有参与人的集合。例如若在排序 \(\sigma\) 下参与人 \(i\) 排在了第一位，那么 \(P_i(\sigma) = \emptyset\)。

即我们将所有排序下前面失败的定义取了平均。

前面的定义基于对不同排列的边际贡献加权平均，我们可以重新整理这一定义，得到基于对不同联盟的边际贡献的加权平均定义的沙普利值等价定义。假设 \(i \in N\) 是一个参与者，\(S\) 是某个不包含 \(i\) 的联盟，考虑有多少种排序 \(\sigma\) 恰好可以使得排在 \(i\) 的前面就是 \(S\)，即 \(P_i(\sigma) = S\)。相当于将 \(n\) 个参与者分成了三个部分，最前面是 \(S\)，中间是 \(i\)，最后是 \(N - (S \cup \{i\})\)。这三个部分的参与者的相对顺序是确定的，而这三个部分内的参与者的相对顺序又是可以任意排列的，因此这一情况下的排序数目为 \(|S|!(n − |S| − 1)!\)。因此这 \(|S|!(n − |S| − 1)!\) 个排列下 \(P_i(\sigma) = S\)，基于此我们可以将上面式子中所有排列按 \(P_i(\sigma)\) 对应的联盟组合起来，得到沙普利值的等价定义：

数据估值⚓︎

留一法⚓︎

一个自然的想法是使用逆向思维，即为了衡量数据集 \(D_i\) 的贡献，可以考虑如果没有数据 \(D_i\)，模型的表现会受到多大的影响，这就是留一法（leave-one-out，简称 LOO）的基本思想，即基于留一法数据价值 \(\varphi_i\) 的定义如下：

即使用所有数据训练出的模型的表现与去掉数据 \(D_i\) 后训练出的模型的表现之差．换句话说，也就是在已有其它数据集的情况下，加入 \(D_i\) 后的模型的性能可以提升多少．这一定义的直观合理性在于，如果数据 Di 对模型的贡献很大，那么去除数据 \(D_i\) 后模型的表现应当会受到很大的影响，即 \(\varphi_i^{LOO}\) 的值应当较大。

Data-Shapley⚓︎

数据集 \(D_i\) 的 Data-Shapley 值的定义如下：

进一步地，可以考虑将所有 \(|S|\) 一致的项合并．令

即加入数据集 \(\{D_i\}\) 后对所有大小为 \(j\) 的联盟的带来的模型训练结果提升的平均值，称为 \(D_i\) 对大小为 \(j\) 的联盟的边际贡献(marginal contribution)。基于此，Data-Shapley 的定义可以进一步改写为：

从这一角度看，数据集 \(D_i\) 的 Data-Shapley 值实际上就是 \(D_i\) 对所有不同大小的联盟的边际贡献的平均。也就是说，Data-Shapley 将数据对任意大小联盟的贡献是平等对待的。

Beta-Shapley⚓︎

在 Data-Shapley 中，数据对任意大小的联盟的贡献是平等对待的，也就是说，一个数据集对小的联盟的贡献和对大的联盟的贡献在 Data-Shapley 中具有相同的权重．然而，一个自然的问题是，当联盟本身已经很大时，此时再加入一个数据集，对联盟的贡献通常而言会比较小，所以对较大联盟的边际贡献值更容易受到噪声干扰．因此直观上来看，在数据估值中，如果对较大联盟的边际贡献的权重应当适当缩小，更加重视对较小联盟的边际贡献，可能对数据集的评估会更加准确．基于此，Beta-Shapley 的定义为：

Data-Banzhaf⚓︎

从 Data-Banzhaf 的表达式中很容易看出其中的思想，事实上就是将 \(D_i\) 对所有 \(2n−1\) 个联盟 \(S \subseteq D - \{D_i\}\) 的贡献取平均，而此前 Data-Shapley 对每个单独的联盟的权重与联盟大小有关（为 \(\dfrac{|S|!(n - |S| - 1)!}{n!}\)），只有将同一大小联盟权重求和才是常数。

和 Beta-Shapley 相比，二者均是 Data-Shapley 的优化，Beta-Shapley 解决了对大联盟边际贡献噪声大的问题，Data-Banzhaf 是从另一个角度，即针对随机学习算法带来的扰动进行优化。

时间复杂度⚓︎

• 留一法：\(O(n)\)
• Data-Shapley, Beta-Shapley, Data-Banzhaf：\(O(2^n)\)（\(P\) 完全问题蒙特卡洛采样）

多项式时间复杂度游戏⚓︎

在合作博弈论中，Airport Game 是一个经典的成本分摊问题，用于模拟机场跑道的建设成本分摊问题．其核心思想是：

• 每个玩家（航空公司）需要一条长度为 \(c_i\) 的跑道（\(c_i\) 是玩家 \(i\) 的最大需求）
• 跑道的总成本由所有玩家中最大的 \(c_i\) 决定（即 \(U(S) = \max\limits_{i \in S} c_i\)）
• 目标是公平地分摊总成本 \(U(N)\)（其中 \(N\) 是全体玩家集合）

不妨假设 \(c_1 \le c_2 \le \dots \le c_n\)，对于玩家 \(i\)，只有与 \(S \subseteq \{1, 2, \dots, i-1\}\) 合作时对成本产生贡献，且

因此，可以通过直接枚举 \(S\) 中需求最大的玩家 \(j\) 以及计算满足 \(j \in S\) 且 \(j = \arg \max_{k \in S} c_k\) 的集合 \(S\) 的组合数在多项式时间内求得 \(i\) 的成本：

沙普利值计算⚓︎

• 边际贡献：\(MC(S \cup \{i\}) = U(S \cup \{i\}) - U(S)\)
• 沙普利值：\(SV_i = \dfrac{1}{n!} \sum_\pi U(S_i^\pi \cup \{i\}) - U(S_i^\pi) = \dfrac{1}{n} \sum_{S \subseteq N - \{i\}} \dfrac{MC(S \cup \{i\})}{\binom{n-1}{|S|}}\)
• 计算复杂度：\(O(2^n)\)

沙普利值近似的高效采样方法⚓︎

下面以这种情况为例分析：

• \(N = \{1, 2, 3\}\)
• \(SV_1 = \dfrac{1}{3}[U(\{1\}) - U(\emptyset) + \dfrac{U(\{1, 2\}) - U(\{2\}) + U(\{1, 3\}) - U(\{3\})}{2} + U(\{1, 2, 3\}) - U(\{2, 3\})]\)

排列采样⚓︎

• 初始为 \(\widehat{SV_1} = 0, \widehat{SV_2} = 0, \widehat{SV_3} = 0\)

• 采样第 1 个排列：1, 2, 3 $$ \widehat{SV_1} += U({1}) - U(\emptyset), \widehat{SV_2} += U({1, 2}) - U({1}), \widehat{SV_3} += U({1, 2, 3}) - U({1, 2}) $$

• 采样第 2 个排列：3, 2, 1 $$ \widehat{SV_3} += U({3}) - U(\emptyset), \widehat{SV_2} += U({3, 2}) - U({3}), \widehat{SV_3} += U({3, 2, 1}) - U({2, 1}) $$

• 平均：\(\widehat{SV_1} /= 2, \widehat{SV_2} /= 2, \widehat{SV_3} /= 2\)

分层采样⚓︎

Stratum：层

• 初始为 \(\widehat{SV_{1, 1}} = 0, \widehat{SV_{1, 2}} = 0, \widehat{SV_{1, 3}} = 0\)
• 在第 1 层取一个样本：\(U(\{1\}) - U(\emptyset)\)，\(\widehat{SV_{1, 1}} += U(\{1\}) - U(\emptyset)\)
• 在第 2 层取一个样本：\(U(\{1, 3\}) - U(\{3\})\)，\(\widehat{SV_{1, 2}} += U(\{1, 3\}) - U(\{3\})\)
• 在第 3 层取一个样本：\(U(\{1, 2, 3\}) - U(\{1, 2\})\)，\(\widehat{SV_{1, 3}} += U(\{1, 2, 3\}) - U(\{1, 2\})\)
• 平均：\(\widehat{SV_1} = \dfrac{\widehat{SV_{1, 1}} + \widehat{SV_{1, 2}} + \widehat{SV_{1, 3}}}{3}\)

补充贡献⚓︎

• 补充贡献 (conplementary contribution)：\(CC(S) = U(S) - U(N - S)\)
• 沙普利值：\(SV_i = \dfrac{1}{n} \sum\limits_{S \subseteq N - \{i\}} \dfrac{CC(S \cup \{i\})}{\binom{n-1}{|S|}}\)

例子

• \(A: U(\{A, B\}) -U(\{C\})\)
• \(B: U(\{A, B\}) -U(\{C\})\)
• \(C: U(\{C\}) -U(\{A, B\})\)

分层 (stratification)：

例子

动态沙普利值计算⚓︎

• 加法：将数据点集合 \(D_{add} = \{z_{n+1}, \dots, z_m\}\) 加到 \(D\)，构成一个新的数据集 \(N^+ = D \cup D_{add}\)。\(z_i \in N^+\) 的沙普利值为： $$ SV_i^+ = \dfrac{1}{n+m} \sum\limits_{S \subseteq N^+ - {i}} \dfrac{U(S \cup {i}) - U(S)}{\binom{n-1}{|S|}} $$

• 减法：将数据点子集 \(D_{del} = \{z_p, \dots, z_q\}\) 从 \(D\) 移除，构成一个新的数据集 \(N^- = D - D_{del}\)。\(z_i \in N^-\) 的沙普利值为： $$ SV_i^- = \dfrac{1}{n+p-q-1} \sum\limits_{S \subseteq N^- - {i}} \dfrac{U(S \cup {i}) - U(S)}{\binom{n+p-q-2}{|S|}} $$

动态沙普利值计算的问题就是对于 \(N^+\)/\(N^-\) 的数据点，高效计算 \(SV_i^+\)/\(SV_i^-\)。

例子

算法：

• 加法：支点算法，增量 (delta) 算法
• 减法：YN 算法，增量算法

支点法⚓︎

位于 \(D \cup \{z_i\}\) 的排列的 \(z_i\)（出现在 \(z_{n+1}\) 之前）的边际贡献已经在 \(D\) 中预先计算过了，能够被再次使用。

例子

增量法⚓︎

计算 \(\Delta SV_i\) 而非 \(NSV_i\)，这样只需用到更少的采样排列，但可以达到相同的精度。

YN 算法⚓︎

将预先计算好的效用存储在多维数组中，供后续再次使用。

例子

算法步骤：

• 给定 \(D = \{z_1, \dots, z_n\}\)
  • \(YN[z_i][z_j][k] = \sum\limits_{S \subseteq D, |S| = k, z_i \in S, z_j \notin S} U(S)\)
  • \(NN[z_i][z_j][k] = \sum\limits_{S \subseteq D, |S| = k, z_i \notin S, z_j \notin S} U(S)\)
• 给定 \(N^- = D - z_{del}, z_i \in Z^-\) $$ SV_i^- = \dfrac{1}{n - 1} \sum\limits_{k=1}^{n-1} \dfrac{YN[z_i][z_{del}][k] - NN[z_i][z_{del}][k - 1]}{\binom{n-2}{k-1}} $$

例子

P-Shapley：沙普利值在概率分类器上的应用⚓︎

可以用不同的平均概率表示相同的模型精度