总收益已经分完,为什么仍可能有联盟想退出?
读后可检查:把联盟价值写成约束,检查核心是否为空,再比较放松稳定性的方案。
📑 本页目录(点开跳转)
22 · 联盟博弈与核心
⏱ 28 分钟 | 时间仅供参考,可以按下面的入口分次读。
🎯 一句话
核心(Core)检查一份分配是否稳定:全部收益分完后,有没有某一伙人能退出、独自合作,再让这伙人都拿得更多?
这不是“人人一样多”,也不保证一定找得到。我们先用三个人分 100 的例子判断核心,再用手套博弈区分“联盟稳定”和“按贡献分配”。
🔀 一、这里发生了一次转折
这里切换的是分析视角:从每个人选择什么行动,转向每个联盟能创造多少收益,以及如何分配。
| 视角 | 从什么开始 | 主要问题 |
|---|---|---|
| 非合作模型 | 行动、信息与收益规则 | 按规则行动会出现什么均衡 |
| 本章联盟模型 | 每一伙人的可得收益 | 怎样分才不会被某个联盟反对 |
本章假设合作协议与内部分配可以执行,因此把合作细节概括成联盟价值。但不能把非合作博弈解释成“所有合同都不算数”:可执行合同、重复互动与协商过程也能放进非合作模型的规则中。
合资项目分利润、团队分成、网络成员贡献,都可用这种视角研究。拼车分摊费用属于成本博弈:越少付越好,需相应改写不等式,不能直接套用本章“收益越多越好”的式子。
🧩 二、TU 博弈:把「一伙人值多少钱」写下来
一个可转移效用(TU)的联盟博弈写作 $(N,v)$:
- $N=\{1,\ldots,n\}$:所有参与者,合在一起称“大联盟”。
- $S\subseteq N$:某一伙参与者,称“联盟”。
- $v(S)$:这伙人不依靠其他成员,能够获得的总收益。
- $v(\emptyset)=0$:没有人的联盟收益为 0。
形式上,$v:2^N\to\mathbb R$。这里 $2^N$ 表示所有子集,不是把某个收益平方。
可转移效用指收益使用可相互转移的同一效用单位,联盟内部可以再分;只说“能转账”还不够。若每个人对钱的效用不同,或转移有约束,要另外建模。
本章算例采用非负、单调的收益:成员变多不使可得价值减少,即 $S\subseteq T$ 时 $v(S)\le v(T)$。这不是所有 TU 博弈的定义要求,也不保证核心非空。
先读一张完整的联盟账本
| 联盟 S | v(S) |
|---|---|
| ∅ | 0 |
| {1} | 4 |
| {2} | 2 |
| {3} | 1 |
| {1,2} | 7 |
| {1,3} | 10 |
| {2,3} | 11 |
| {1,2,3} | 15 |
看 {1,3} 那一行:两人合作总共能得到 10,还没有规定这 10 怎样在两人间分。
三个人已有 $2^3=8$ 个联盟;20 人有 $2^{20}=1\,048\,576$ 个。如何简洁表示 $v$ 是计算问题的一部分,下一章还会用紧凑表示法讨论它。
简单博弈与加权投票
简单博弈在这里指单调的 0/1 博弈,且空集为 0、大联盟为 1。值为 1 的是获胜联盟,值为 0 的是失败联盟,适合表示“哪些人凑起来能通过议案”。
加权投票博弈(WVG)给每人非负权重 $w_i$,设正门槛 $q$;所有权重之和至少达到门槛。规则是:
$$v(S)=1\ \Longleftrightarrow\ \sum_{i\in S}w_i\ge q$$
记作 $[q;w_1,\ldots,w_n]$。例如 $[3;2,1,1]$:
- 1 号权重为 2,不能单独通过。
- 1 号与 2 号、或与 3 号联手,都达到 3。
- 2 号和 3 号合计只有 2,不能通过。
为什么不是每个简单博弈都能写成一组权重?
取四个人,极小获胜联盟为 $\{1,2\}$、$\{1,4\}$、$\{2,3\}$。极小的意思是:该联盟获胜,但去掉任何成员就失败;包含这些联盟的更大集合也获胜。
$\{1,3\}$ 与 $\{2,4\}$ 都不包含上述获胜组合,所以失败。如果存在权重表示:
- {1,4} 胜、{2,4} 败,同减 $w_4$,推出 $w_1>w_2$。
- {2,3} 胜、{1,3} 败,同减 $w_3$,推出 $w_2>w_1$。
两条矛盾。因此权重表示很直观,却不能表达每一种简单博弈。
💰 三、分配的两条最低要求
分配向量 $x=(x_1,\ldots,x_n)$ 表示每人拿多少。记 $x(S)=\sum_{i\in S}x_i$,即一伙人合计拿到的收益。
效率:总收益分完。
$$\sum_{i\in N}x_i=v(N)$$
这里的“效率”是这条总量等式,不是说分配算法跑得快。
个体理性:每个人至少拿到单干的收益。
$$x_i\ge v(\{i\})\quad\text{对每个 }i$$
同时满足两条的分配称为 imputation,集合记作 $I(v)$。只有效率、不要求个体理性的,叫 preimputation。
先确认:最低要求本身能满足吗?
$I(v)$ 非空,当且仅当大联盟的收益不少于各人单干收益之和:
$$v(N)\ge\sum_i v(\{i\})$$
账本例子中,$15\ge4+2+1=7$,可以先保证各人底线,再分剩下的 8。
反例:两个人单干各得 1,合作总共也只有 1。虽然收益非负且单调,却无法同时满足两人的底线。后面关于核仁存在的结论,要先假设 $I(v)$ 非空。
⭐ 四、核心(Core)
一个人不想退出,不代表一伙人不想退出。核心把个体理性推广到所有联盟。
在总收益分完的前提下,要求:
$$x(S)\ge v(S)\quad\text{对所有 }S\subseteq N$$
例如一伙人目前合计拿 6,单独合作却能拿 8。在可转移收益的设定下,多出的 2 可以再分,让联盟每位成员都比原来多拿一些;这就是对当前分配的反对理由。
核心只排除这种严格改善的退出动机。双方收益相等时,成员也可能无差异;核心不是对所有现实行为的保证。
记号:本章把余额叫作超额
沿用本章的余额口径:
$$e(x,S)=x(S)-v(S)$$
- 正数:留在大联盟的合计收益更高。
- 0:合计收益相同。
- 负数:联盟独自合作能多赚。
- 核心:有效率,且全部余额非负。单点联盟也在其中,所以自动满足个体理性。
不同资料的符号可能反过来。若资料定义超额为 $v(S)-x(S)$,就要把本章每个余额取负;此时核心要求“超额不大于 0”。后面的排序方向也要一起反转,不能只换大小号。
🔨 n=3 的手算套路
三个人共有 8 个联盟,其中 7 个非空。空集约束恒成立,大联盟由效率保证,3 个单点给出各人的下限。
剩下 3 个两人联盟,可利用总和固定,换成“第三人最多拿多少”:
$$x(S)\ge v(S)$$
等价于:
$$x(N\setminus S)\le v(N)-v(S)$$
所以要同时检查三个下限、三个上限,以及总和。不能只看上限相加够不够,还要看每个人的上下限是否冲突。
完整走一遍
这次换一组账本:三个单点收益都是 0,两人联盟与总收益如下。
| 联盟 | 收益 |
|---|---|
| {1,2} | 50 |
| {1,3} | 70 |
| {2,3} | X |
| {1,2,3} | 100 |
我们保持非负、单调的设定,所以参数范围先限定为 $0\le X\le100$。
第一步:把两人下限换成第三人的上限。
| 联盟约束 | 等价上限 |
|---|---|
| $x_1+x_2\ge50$ | $x_3\le50$ |
| $x_1+x_3\ge70$ | $x_2\le30$ |
| $x_2+x_3\ge X$ | $x_1\le100-X$ |
还要保留 $x_1,x_2,x_3\ge0$ 与总和为 100。
第二步:试一个能直接验证的值。当 $X=60$ 时,上限是 40、30、50。可取 $x=(30,20,50)$:
| 联盟 | 分到 | 单干值 | 是否满足 |
|---|---|---|---|
| {1,2} | 50 | 50 | 是 |
| {1,3} | 80 | 70 | 是 |
| {2,3} | 70 | 60 | 是 |
三个单点都非负,总和也为 100,所以它确实在核心里。
第三步:找核心为空的边界。三个上限的和必须至少为 100:
$$50+30+(100-X)\ge100$$
于是 $X\le80$。在既定参数范围内,答案是 $0\le X\le80$ 时核心非空。
这不只是必要条件:取 $x=(20,30,50)$,可同时满足这整个范围的约束。$X=80$ 时三个上限之和恰好为 100,只剩这一点。
另一种证明:为什么 X 大于 80 一定无解?
将三个两人联盟的下限相加。每个人的收益都被算两次,左边固定为 $2\times100$:
$$2\times100\ge50+70+X$$
所以必须 $X\le80$。超过 80 时,无论怎样分,三个联盟的要求都不能同时满足。
这个例子演示了如何验证分配并求出三人情形的可行边界。下一节处理“没有任何分法能让所有联盟接受”的情况。
⚠️ 五、核心很容易空
三个人中,任意两人就能完成一个价值为 1 的任务:人数至少为 2 的联盟值为 1,否则为 0。
先找矛盾。两人拿到的合计必须至少为 1,但总共只有 1;于是剩下的第三人至多拿 0。对三个人分别如此,得到 $x_1,x_2,x_3\le0$,不可能再凑出总和 1。
所以核心为空。问题不是计算不够努力,而是这些联盟要求本来就不相容。
简单博弈的快捷判据:有没有不可缺的人?
否决者(vetoer):每一个获胜联盟都必须包含他。等价地,不含他的任何联盟都失败。
对本章定义的单调简单博弈:
核心非空,当且仅当存在否决者;核心里非否决者只能拿 0。
分三步证明这个判据
有否决者时能构造核心。给某个否决者 1,其余人 0。所有获胜联盟都含他,拿到 1;失败联盟的价值为 0,也不被亏待。
非否决者在核心中只能拿 0。去掉非否决者 $i$ 后,剩下的人仍能获胜,因此 $1-x_i\ge1$,即 $x_i\le0$。个体理性又给出 $x_i\ge0$。
没有否决者时必然矛盾。每个人都只能拿 0,却必须把总收益 1 分完。
任意两人完成任务的例子没有否决者:去掉谁,另外两人都能赢。它的核心为空,与前面的计算一致。
🩹 六、Least Core 与 Nucleolus
核心为空,只代表没有分法满足全部联盟要求。如果个体理性的分配集合 $I(v)$ 非空,还可以在这些分配中寻求妥协。
最小核心:先降低最坏的亏欠
本章采用非负松弛版:允许每个联盟的余额最低到 $-\varepsilon$,其中 $\varepsilon\ge0$。
把所有满足这个要求的 $x\in I(v)$ 称为 $\varepsilon$-核心;让它刚好非空的最小 $\varepsilon^\ast$,对应的分配集合称为 least core(最小核心)。
计算时,最小化 $\varepsilon$,同时保留三类约束:
$$x(S)\ge v(S)-\varepsilon\quad(S\subseteq N)$$
$$x_i\ge v(\{i\}),\qquad x(N)=v(N)$$
$$\varepsilon\ge0$$
这里没有放松个人单干的底线。只有当每个人单干值都为 0,个体理性才简化成 $x_i\ge0$;账本第一例的底线仍是 4、2、1。
$I(v)$ 非空时,先任选一个分配,再把有限个联盟中的最大亏欠作为 $\varepsilon$,就能得到可行解。因此本章的最小核心非空;若 $I(v)$ 本身空,放松联盟约束不能修好个人底线冲突。
读其他资料时:为什么有的最小核心允许负 ε?
本章把 $\varepsilon$ 当作非负的“容许亏欠”。原核心非空时,$\varepsilon^\ast=0$,本章版本的最小核心就等于核心。一种采用非负松弛与余额口径的研究定义
也有常见定义只比较非空真子联盟,允许 $\varepsilon$ 为负,用来衡量所有这些联盟能同时得到多少额外余额。另一些定义在 preimputation 上求解。
例如两个人单干均为 0、合作值为 10:本章非负版包含全部非负且总和为 10 的分配;若在相同分配集合上允许负 $\varepsilon$、只检查两个单点,最优是 $\varepsilon^\ast=-5$,只剩 $(5,5)$。
因此跨资料比较数值时,先看分配范围、联盟范围、是否允许负松弛,不要把几个版本的性质混在一起。
空核心例子的完整复算
回到“任意两人值 1”的例子。每个两人联盟至少拿 $1-\varepsilon$;三条相加:
$$2\ge3(1-\varepsilon)$$
所以 $\varepsilon\ge1/3$。
取 $x=(1/3,1/3,1/3)$:每个两人联盟拿 $2/3$,恰好比独自合作少 $1/3$;个人底线与总和都满足。
而当 $\varepsilon=1/3$ 时,每个第三人都至多拿 $1/3$,再结合总和为 1,强制三人全部拿 $1/3$。所以最小核心只有这一个点,且 $\varepsilon^\ast=1/3$。
核仁:最坏项相同时,再比较后面的项
最小核心有时仍包含多个点。为了继续比较,令 $\theta(x)$ 把所有联盟的余额 $e(x,S)$ 从小到大排列。
核仁(Nucleolus)是在 $I(v)$ 中,让这个向量按字典序最大的分配。不是在任意效率分配中不加限制地寻找。
“字典序”像逐位比较成绩:
- 先比最小余额,谁更大谁更好。
- 最小余额相同,再比第二小的。
- 继续比较,直到出现第一处差异。
联盟身份可能随分配而改变;不是先指定某一个联盟,然后永远按同一成员名单依次优化。
对于有限 TU 博弈,在 $I(v)$ 非空的前提下,核仁有三条性质:
- 存在且唯一。这是 Schmeidler 提出的核仁所具有的性质。
- 位于本章的最小核心。先优化最坏亏欠,再继续细分。
- 核心非空时位于核心。不会选一个被某联盟严格反对的分配。
若改用相反的超额 $v(S)-x(S)$,需取负、降序排、字典序最小化,三步一起变才等价。若去掉个体理性、只保留效率,通常称为 pre-nucleolus(前核仁),不能只改定义域却照搬名称与前提。核仁的定义域与存在条件
🧤 手套博弈:完整手算
1 号有一只右手套,2、3 号各有一只左手套。一双值 1;即使三个人都在场,也只能凑出一双。
先保留完整账本,再比较两个分配。A 为 $(1/2,1/4,1/4)$,B 为 $(1,0,0)$;下表余额均按 $x(S)-v(S)$ 计算。
| 联盟 S | v(S) | A 余额 | B 余额 |
|---|---|---|---|
| {1,2} | 1 | −1/4 | 0 |
| {1,3} | 1 | −1/4 | 0 |
| {1,2,3} | 1 | 0 | 0 |
| ∅ | 0 | 0 | 0 |
| {2} | 0 | 1/4 | 0 |
| {3} | 0 | 1/4 | 0 |
| {1} | 0 | 1/2 | 1 |
| {2,3} | 0 | 1/2 | 0 |
看第一行:A 给 {1,2} 合计 $3/4$,但两人独自合作能得 1,余额是 $-1/4$;因此 A 不在核心里。
为什么核仁确实是 B,而不只是“B 比 A 好”?
只比较两个候选,无法证明全局最优。这里先找出整个核心:
- {1,2} 必须至少拿 1,总和又只有 1,所以 $x_3\le0$;个体理性使 $x_3=0$。
- 对 {1,3} 同理,得到 $x_2=0$。
- 效率迫使 $x_1=1$;B 逐项满足上表全部联盟要求。
因此核心恰好为 $\{(1,0,0)\}$。核仁在非空核心中,而这里只有一个点,所以核仁就是 B。
也可用否决者定理复核:1 号是唯一否决者,非否决者 2、3 在核心中只能拿 0。
再练一次字典序:保留 A、B 全部八项余额
升序后的向量按位置逐项列出,避免一行塞满八个分数:
| 位置 | θ(A) | θ(B) |
|---|---|---|
| 1 | −1/4 | 0 |
| 2 | −1/4 | 0 |
| 3 | 0 | 0 |
| 4 | 0 | 0 |
| 5 | 1/4 | 0 |
| 6 | 1/4 | 0 |
| 7 | 1/2 | 0 |
| 8 | 1/2 | 1 |
第一项 $0>-1/4$,所以 B 的向量更大。后面某一项 A 更大也不能推翻这个判断:字典序看的是第一处差异。
这一步演示比较规则;核仁的全局结论由上面的唯一核心证明支撑。
“稳定”不等于唯一的公平标准
给 2 号正收益,会让 {1,3} 合计拿不到 1,于是他们有动力单独配对。这解释了核心为何把全部收益给右手套拥有者,不代表他们“更值得”拿钱。
下一章用平均边际贡献得到 Shapley 值 $(4/6,1/6,1/6)$。此时 {1,2} 合计拿 $5/6<1$,所以不在核心里。
两个答案服务不同标准:核仁强调联盟稳定性的细化;Shapley 值强调边际贡献与相应公理。不能把后者说成唯一“公平”的答案,也不能认为二者必须一致。
📊 七、四个解概念
下面“最小核心”和“核仁”的存在性均以 $I(v)$ 非空为前提;最小核心沿用本章非负松弛版。
| 解概念 | 存在? | 唯一? | 在比较什么 |
|---|---|---|---|
| 核心 Core | 可能为空 | 不保证 | 是否所有联盟都不吃亏 |
| 最小核心 | 在上述前提下存在 | 不保证 | 最坏的容许亏欠 |
| 核仁 | 在上述前提下存在 | 是 | 排序后逐层比较余额 |
| Shapley 值 | 有限 TU 博弈中存在 | 是 | 平均边际贡献 |
Shapley 值一般不保证在核心里;对一般 TU 博弈,也不能无条件保证个体理性。
计算难度要看价值函数如何表示。显式列出核心约束,最多涉及 $2^n$ 个联盟;这说明输入与约束可能很大,不代表每个具体博弈都难算。
Shapley 定义可对 $n!$ 个排列取平均,但还能合并为对 $2^{n-1}$ 个子集的加权求和。紧凑结构或近似方法可能节省计算,不能把定义里的枚举数量直接当成所有算法的必需代价。
🔗 这一章连到哪里
- 23 · Shapley 值:同一个手套账本,核仁为 (1,0,0),Shapley 为 (4/6,1/6,1/6)。继续看平均边际贡献怎么算、对应什么公理。
- 24 · 投票规则:从“哪些联盟能通过一个提案”,转向“如何汇总偏好作出集体决定”。它们有关联,但不是完全相同的问题。
- 模型上线之后 09 · 特征重要性的三种谎言:把“成员贡献”连到特征归因。先看工程上的解释风险,再结合下一章理解基于 Shapley 的归因。
✅ 检查点
- 本章与非合作模型主要换了什么视角?为什么不能说非合作模型里的合同都无效?
- 为什么价值函数的表示方法影响计算?简单博弈与加权投票有什么区别?
- 个体理性分配什么时候存在?核心比它多要求了什么?
- 三人手算时,为什么两人联盟的下限等价于第三人的上限?
- 单点为 0、两人收益为 50、70、X,总收益为 100:在非负单调设定下,X 什么范围核心非空?X=60 时举一个点。
- 任意两人完成任务的例子为何核心为空?否决者判据如何解释?
- 本章最小核心采用什么定义范围?该空核心例子的最小松弛与分配是多少?
- 核仁在哪个集合里优化什么?为什么手套博弈的核仁确实是 (1,0,0)?
👀 答案
- 从行动、信息和均衡,转向联盟价值与收益分配。本章把协议执行作为假设;非合作模型也可以把合同及执行机制写进规则。
- n 人有 $2^n$ 个联盟,20 人为 1,048,576 个。简单博弈是单调的 0/1 规则;非负权重加门槛给出 WVG,但不是每个简单博弈都能表示成 WVG。
- $v(N)\ge\sum_i v(\{i\})$ 时有效率且个体理性的分配存在。核心还要求每个联盟的分配总和至少为其独自合作值。
- 固定总和 $x(N)=v(N)$ 后,$x(S)$ 增加多少,补集能分的就减少多少;从效率等式移项即可。下限、上限与总和必须一起检查。
- 先限定 $0\le X\le100$;核心非空恰好是 $0\le X\le80$。X=60 可取 (30,20,50),三对分别拿 50、80、70。X=80 时唯一点为 (20,30,50)。
- 三个两人约束迫使每个人至多拿 0,却要求总和为 1。去掉谁另外两人都能获胜,所以没有否决者,与简单博弈的判据一致。
- 在非空的 $I(v)$ 上,用非负 ε 放松联盟约束,但不放松个人底线。三人例子中,三条约束相加给出 ε≥1/3;均分能达到,且是唯一达到的分配。
- 在 $I(v)$ 中,让全部余额升序后的向量字典序最大;它存在且唯一,并落在本章最小核心中,核心非空时也在核心里。手套例子的核心被全部约束强制成唯一点 (1,0,0),因此它是核仁;只比较 A、B 两个向量不够证明这一点。
本节回顾
⚡ 走神救援
带走四个判断
- 先算每伙人能得多少,再讨论怎么分;收益与成本的方向不同。
- 核心要求总收益分完,且每个联盟都不比独自合作少拿。
- 先确认个人底线能满足,再讨论本章最小核心与核仁的存在。
- 手套例子里,稳定性与平均贡献会给出不同分配。
下一节 👉 23 · Shapley 值