🏠 总目录📚 本教程 22 · 联盟博弈与核心 ← →

总收益已经分完,为什么仍可能有联盟想退出?

读后可检查:把联盟价值写成约束,检查核心是否为空,再比较放松稳定性的方案。

📑 本页目录(点开跳转)

22 · 联盟博弈与核心

⏱ 28 分钟 | 时间仅供参考,可以按下面的入口分次读。


🎯 一句话

核心(Core)检查一份分配是否稳定:全部收益分完后,有没有某一伙人能退出、独自合作,再让这伙人都拿得更多?

这不是“人人一样多”,也不保证一定找得到。我们先用三个人分 100 的例子判断核心,再用手套博弈区分“联盟稳定”和“按贡献分配”。


🔀 一、这里发生了一次转折

这里切换的是分析视角:从每个人选择什么行动,转向每个联盟能创造多少收益,以及如何分配。

视角 从什么开始 主要问题
非合作模型 行动、信息与收益规则 按规则行动会出现什么均衡
本章联盟模型 每一伙人的可得收益 怎样分才不会被某个联盟反对

本章假设合作协议与内部分配可以执行,因此把合作细节概括成联盟价值。但不能把非合作博弈解释成“所有合同都不算数”:可执行合同、重复互动与协商过程也能放进非合作模型的规则中。

合资项目分利润、团队分成、网络成员贡献,都可用这种视角研究。拼车分摊费用属于成本博弈:越少付越好,需相应改写不等式,不能直接套用本章“收益越多越好”的式子。


🧩 二、TU 博弈:把「一伙人值多少钱」写下来

一个可转移效用(TU)的联盟博弈写作 $(N,v)$:

形式上,$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,4\}$、$\{2,3\}$。极小的意思是:该联盟获胜,但去掉任何成员就失败;包含这些联盟的更大集合也获胜。

$\{1,3\}$ 与 $\{2,4\}$ 都不包含上述获胜组合,所以失败。如果存在权重表示:

两条矛盾。因此权重表示很直观,却不能表达每一种简单博弈。


💰 三、分配的两条最低要求

分配向量 $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)$$

不同资料的符号可能反过来。若资料定义超额为 $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)$ 中,让这个向量按字典序最大的分配。不是在任意效率分配中不加限制地寻找。

“字典序”像逐位比较成绩:

  1. 先比最小余额,谁更大谁更好。
  2. 最小余额相同,再比第二小的。
  3. 继续比较,直到出现第一处差异。

联盟身份可能随分配而改变;不是先指定某一个联盟,然后永远按同一成员名单依次优化。

对于有限 TU 博弈,在 $I(v)$ 非空的前提下,核仁有三条性质:

若改用相反的超额 $v(S)-x(S)$,需取负、降序排、字典序最小化,三步一起变才等价。若去掉个体理性、只保留效率,通常称为 pre-nucleolus(前核仁),不能只改定义域却照搬名称与前提。核仁的定义域与存在条件

🧤 手套博弈:完整手算

1 号有一只右手套,2、3 号各有一只左手套。一双值 1;即使三个人都在场,也只能凑出一双。

右手套是共同必需的成员,左手套有两个替代者 1 号:右手套 每一双都需要他 2 号:左手套 3 号:左手套 {1,2} 值 1 {1,3} 值 1 {2,3} 都是左手套,合起来值 0
1 号不可缺,2、3 号互为替代。

先保留完整账本,再比较两个分配。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. {1,2} 必须至少拿 1,总和又只有 1,所以 $x_3\le0$;个体理性使 $x_3=0$。
  2. 对 {1,3} 同理,得到 $x_2=0$。
  3. 效率迫使 $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}$ 个子集的加权求和。紧凑结构或近似方法可能节省计算,不能把定义里的枚举数量直接当成所有算法的必需代价。


🔗 这一章连到哪里


✅ 检查点

  1. 本章与非合作模型主要换了什么视角?为什么不能说非合作模型里的合同都无效?
  2. 为什么价值函数的表示方法影响计算?简单博弈与加权投票有什么区别?
  3. 个体理性分配什么时候存在?核心比它多要求了什么?
  4. 三人手算时,为什么两人联盟的下限等价于第三人的上限?
  5. 单点为 0、两人收益为 50、70、X,总收益为 100:在非负单调设定下,X 什么范围核心非空?X=60 时举一个点。
  6. 任意两人完成任务的例子为何核心为空?否决者判据如何解释?
  7. 本章最小核心采用什么定义范围?该空核心例子的最小松弛与分配是多少?
  8. 核仁在哪个集合里优化什么?为什么手套博弈的核仁确实是 (1,0,0)?
👀 答案
  1. 从行动、信息和均衡,转向联盟价值与收益分配。本章把协议执行作为假设;非合作模型也可以把合同及执行机制写进规则。
  2. n 人有 $2^n$ 个联盟,20 人为 1,048,576 个。简单博弈是单调的 0/1 规则;非负权重加门槛给出 WVG,但不是每个简单博弈都能表示成 WVG。
  3. $v(N)\ge\sum_i v(\{i\})$ 时有效率且个体理性的分配存在。核心还要求每个联盟的分配总和至少为其独自合作值。
  4. 固定总和 $x(N)=v(N)$ 后,$x(S)$ 增加多少,补集能分的就减少多少;从效率等式移项即可。下限、上限与总和必须一起检查。
  5. 先限定 $0\le X\le100$;核心非空恰好是 $0\le X\le80$。X=60 可取 (30,20,50),三对分别拿 50、80、70。X=80 时唯一点为 (20,30,50)。
  6. 三个两人约束迫使每个人至多拿 0,却要求总和为 1。去掉谁另外两人都能获胜,所以没有否决者,与简单博弈的判据一致。
  7. 在非空的 $I(v)$ 上,用非负 ε 放松联盟约束,但不放松个人底线。三人例子中,三条约束相加给出 ε≥1/3;均分能达到,且是唯一达到的分配。
  8. 在 $I(v)$ 中,让全部余额升序后的向量字典序最大;它存在且唯一,并落在本章最小核心中,核心非空时也在核心里。手套例子的核心被全部约束强制成唯一点 (1,0,0),因此它是核仁;只比较 A、B 两个向量不够证明这一点。

本节回顾

⚡ 走神救援

带走四个判断

下一节 👉 23 · Shapley 值

打卡记录保存在你的浏览器里,首页能看到总进度