6 7 Cooperative Games
合作博弈 Cooperative Games¶
合作博弈（cooperative game）允许参与者组成联盟并共同创造价值，研究联盟如何形成、收益如何分配，以及分配是否稳定或公平。联盟价值说明“合作能创造多少”，分配规则说明“每个人拿多少”；两者需要分别建模。
可转移效用模型¶
可转移效用（transferable utility，TU）合作博弈写作 \(G=(N,v)\)，其中 \(N=\{1,\ldots,n\}\) 是玩家集合，特征函数（characteristic function）\(v:2^N\to\mathbb R\) 给出每个联盟（coalition）的价值，通常满足 \(v(\varnothing)=0\)。全体玩家组成大联盟（grand coalition）\(N\)。
单调性（monotonicity）指
TU 允许联盟把总价值在成员间自由转移，不需要逐一描述联盟内部的生产行动。若不同联盟互不影响，便可用各联盟能实现的最大总价值概括其行动选择。
农场与冰淇淋示例¶
规模为 \(k\) 的农场联盟可生产 \(k^2\) 吨苹果或 \(3k\) 吨橙子，每吨分别售价 £200 与 £300，因此
在课件的三人范围内，最优选择是橙子，价值为 \(900|C|\)；不能据此推断任意规模下都为线性价值。
冰淇淋例中，C、M、P 分别拥有 6、4、3 美元。合并预算后购买最大可负担规格，得到
这里字母连写表示相应成员组成的集合，价值单位为克。合作收益不必等于单人收益之和。
结果、效率与个体理性¶
联盟结构（coalition structure）\(CS\) 是 \(N\) 的一个划分。结果（outcome）为 \((CS,x)\)，其中 \(x_i\) 是玩家收益，要求每个联盟 \(C\in CS\) 满足
这表示联盟内分配全部价值，不允许从其他联盟转移收益。若只研究大联盟，则效率（efficiency）要求 \(x(N)=v(N)\)，其中 \(x(C)=\sum_{i\in C}x_i\)。个体理性（individual rationality）进一步要求
满足效率和个体理性的分配称为归责分配（imputation）。可行、稳定、公平是不同要求。
超可加性与凸性¶
超可加性（superadditivity）要求对不相交联盟 \(C,D\)，
合并联盟不会降低总价值，因此在超可加博弈中可聚焦大联盟的收益分配。若原博弈不超可加，可定义超可加覆盖（superadditive cover）：
凸博弈¶
凸博弈（convex game）要求特征函数满足超模性（supermodularity）：
等价地，对 \(T\subseteq S\)、\(i\notin S\)，玩家的边际贡献（marginal contribution）满足
联盟越大，新增玩家的贡献不会下降。凸性蕴含超可加性，反向不成立。例如 \(v(C)=|C|^2\) 的新增贡献为 \(2|C|+1\)，所以是凸博弈。
诱导子图博弈（induced subgraph game）把玩家视为带权图顶点，联盟价值为内部边权之和：
若边权非负，新增玩家在更大联盟中会增加更多非负边权，因此博弈凸；允许负边权时不能直接使用这一结论。
核心：抗联盟偏离的稳定性¶
核心（core）由无法被任何联盟阻挡的结果组成。对大联盟分配，定义为
若 \(x(C)<v(C)\)，联盟 \(C\) 可退出，并把额外收益分给所有成员使每人都改善，所以它能阻挡（block）当前分配。单人联盟约束同时保证个体理性。
稳定性与公平性不同¶
课件另一个冰淇淋例取 \(v(CM)=v(CP)=500\)、\(v(MP)=0\)、\(v(CMP)=750\)。分配 \((200,200,350)\) 被联盟 \(CM\) 阻挡，因为二人当前总收益为 \(400\)，却能自行创造 \(500\)。均分 \((250,250,250)\) 与 \((750,0,0)\) 都在核心中；后者说明稳定分配可能非常不均衡。
核心可能为空¶
三人博弈中，任何至少两人的联盟价值为 \(1\)，单人价值为 \(0\)。核心若存在，则
相加得到 \(2(x_1+x_2+x_3)\ge3\)，与效率要求总和为 \(1\) 矛盾，故核心为空。
凸博弈的核心非空¶
固定一个玩家排列 \(\pi\)，令 \(S_i^\pi\) 为排在 \(i\) 前面的玩家集合，并给玩家分配
这些边际贡献相加望远镜消去中间项，得到 \(x^\pi(N)=v(N)\)。对任意联盟 \(C\)，按同一排列只让 \(C\) 的成员依次加入，由凸性，每位成员在大联盟排列中的贡献不少于其在 \(C\) 内的贡献，所以 \(x^\pi(C)\ge v(C)\)。
因此每个排列的边际贡献向量都在核心中。给定价值查询预言机（value oracle），只需查询 \(n\) 个前缀联盟价值即可构造一个核心分配。
简单博弈与加权投票¶
简单博弈（simple game）满足 \(v(C)\in\{0,1\}\) 且单调：价值为 \(1\) 的联盟获胜，价值为 \(0\) 的联盟失败。空玩家（null player）对任何联盟的价值都不产生影响；否决玩家（veto player）出现在每个获胜联盟中。
加权投票博弈（weighted voting game，WVG）记为 \([q;w_1,\ldots,w_n]\)，联盟获胜当且仅当
每个 WVG 都是简单博弈，但反向不成立。四人规则“联盟同时与 \(\{1,3\}\) 和 \(\{2,4\}\) 相交”无法加权表示：获胜联盟 \(\{1,2\}\)、\(\{3,4\}\) 要求总权重至少 \(2q\)；失败联盟 \(\{1,3\}\)、\(\{2,4\}\) 却要求总权重小于 \(2q\)，矛盾。
简单博弈的核心¶
对标准简单博弈 \(v(N)=1\)，核心非空当且仅当有否决玩家。把全部价值给任意否决玩家即可得到核心分配；更一般地，任意仅给否决玩家分配收益且总和为 \(1\) 的向量都属于核心。
若没有否决玩家，所有 \(N\setminus\{i\}\) 均获胜。任何有效分配中总有人收益为正，去掉此人的联盟当前收益小于 \(1\)，却能自行创造 \(1\)，所以能阻挡。只需查询每个 \(v(N\setminus\{i\})\) 即可检测否决玩家。
ε-核心与最小核心¶
ε-核心（epsilon-core）允许每个联盟最多存在 \(\varepsilon\) 的收益缺口：
在每个二人联盟价值为 \(1\) 的三人博弈中，均分 \((1/3,1/3,1/3)\) 的最大缺口为 \(1/3\)。把三个二人联盟约束相加得到
因此 \(\varepsilon\ge1/3\)，且均分达到该下界。
最小核心（least core）选择使这些约束可行的最小 \(\varepsilon\)，即最小化所有联盟的最大收益缺口。课件的定义保留大联盟效率，并逐一放宽联盟约束；使用不同教材时应核对是否额外限制 \(\varepsilon\ge0\) 或要求个体理性。
Shapley 值：按边际贡献公平分配¶
夏普利值（Shapley value）对所有玩家加入顺序取平均：
等价地，它是玩家在均匀随机排列中的期望边际贡献。按联盟求和的公式为
权重来自恰好让 \(C\) 全部排在 \(i\) 之前、其他人排在之后的排列数量。一般博弈中直接计算涉及指数多个联盟。
四条刻画公理¶
| 公理 | 要求 |
|---|---|
| 效率 | \(\sum_i\phi_i(v)=v(N)\) |
| 空玩家 | 边际贡献恒为零的玩家得到零收益 |
| 对称性 | 对所有联盟作用相同的玩家得到相同收益 |
| 可加性（additivity） | \(\phi_i(v+w)=\phi_i(v)+\phi_i(w)\) |
Shapley 值是唯一同时满足这四条公理的分配规则。它一般不保证属于核心；若博弈凸，每个边际贡献向量都在核心中，它们的平均值也在核心中，所以凸博弈的 Shapley 值稳定。
计算例与结构化简¶
两个对称玩家各自价值 \(5\)、大联盟价值 \(20\)，两个顺序分别分配 \((5,15)\) 与 \((15,5)\)，Shapley 值为 \((10,10)\)。
课件第 42 页另取儿童预算 6、4、2 美元，C 的六个边际贡献为 \(0,0,750,500,1000,1000\)，所以 \(\phi_C=3250/6\approx542\) 克。该页 P 的预算与前面 3 美元的版本不同，不能混用价值表。
在诱导子图博弈中，一条边的价值在随机排列里有一半概率由任一端点带来，故两个端点均分边权：
在简单博弈中，玩家边际贡献只可能是 \(0\) 或 \(1\)；当其加入使失败联盟变为获胜联盟时，称为关键玩家（pivotal player）。Shapley 值因此等于其在随机排列中成为关键玩家的概率，解释为投票权力。
不可转移效用与偏好联盟¶
不可转移效用（non-transferable utility，NTU）模型中，联盟可实现的是一组个人效用向量，而非可任意分配的总数。例如两个行动分别产生 \((1,6)\)、\((4,2)\)；成员不能自由把效用转给对方。研究者合作所带来的晋升、奖金和减课也常由个人所属机构决定。
偏好联盟博弈（hedonic game）中，每位玩家的偏好只取决于所在联盟的成员。联盟结构稳定，当且仅当不存在一个联盟 \(S\)，使其中每个人都严格偏好加入 \(S\) 而不是留在当前联盟；这定义了该模型的核心，核心仍可能为空。
稳定匹配与延迟接受算法¶
稳定匹配（stable matching）考虑两侧各 \(n\) 人，每人严格排列另一侧所有对象。完美匹配（perfect matching）使每个人恰有一个伴侣。若未配对的两个人都更偏好彼此而非当前伴侣，则构成阻挡对（blocking pair）；没有阻挡对的完美匹配即为稳定匹配。
稳定匹配可视为只允许跨侧二人联盟的偏好联盟博弈核心。稳定室友问题（stable roommates problem）则只有一个集合，所有人互相排序并两两配对；这种模型不一定存在稳定解。
Gale–Shapley 算法¶
盖尔–沙普利延迟接受算法（Gale–Shapley deferred acceptance algorithm）以男性提案为例：
- 所有人起初未匹配。
- 未匹配男性向自己最偏好的、尚未提案过的女性提案。
- 女性在新提案者和当前暂留对象中选择最偏好的一人，拒绝其余对象。
- 重复直到没有男性需要继续提案。
暂留并非最终承诺；女性可换为更偏好的新提案者。每对最多提案一次，因此至多发生 \(n^2\) 次提案，可在 \(O(n^2)\) 时间内实现。
完美性与稳定性¶
在人数相等、严格完整偏好的条件下，终止时若有男性未匹配，他已经向所有女性提案。女性一旦收到提案就一直暂留某人，故所有女性都已匹配，与存在未匹配男性矛盾，输出必为完美匹配。
若男性 \(m\) 更偏好女性 \(w\) 而不是最终伴侣，他必曾向 \(w\) 提案并被拒绝。女性只会更换为更喜欢的人，所以 \(w\) 最终更偏好自己的伴侣而非 \(m\)。因此任意未匹配对都不能同时获益，输出稳定。
提案方最优性¶
有效伴侣（valid partner）是在至少一个稳定匹配中能与该人配对的对象。男性提案的算法给每位男性其最偏好的有效伴侣，称为男性最优稳定匹配（man-optimal stable matching）。
反设某次出现算法首次拒绝有效伴侣：女性 \(A\) 拒绝男性 \(Y\)，暂留更喜欢的 \(Z\)。取一个包含 \(Y-A\) 的稳定匹配，其给 \(Z\) 的伴侣为 \(B\)。此前 \(Z\) 未被有效伴侣 \(B\) 拒绝，因此能向 \(A\) 提案说明他更偏好 \(A\) 而非 \(B\)；\(A\) 也更偏好 \(Z\) 而非 \(Y\)。于是 \(Z-A\) 阻挡该稳定匹配，矛盾。
男性最优同时意味着女性最差稳定匹配（woman-pessimal stable matching）：每位女性得到自己最不喜欢的有效伴侣。若她在另一个稳定匹配中得到更差的男性，而原配男性在那里得到其他女性，男性最优性就使原配双方同时更偏好彼此，从而阻挡另一个匹配。交换提案方得到女性最优、男性最差的结果。
这里“最优/最差”只在所有稳定匹配的范围内比较，并非所有可能配对。严格偏好下，改变同一提案方的提案处理顺序不会改变其最优稳定结果。
模型扩展¶
多对一模型可用于学校录取与医院—住院医师匹配，须指定容量与接收方偏好规则。若人数不等或存在不可接受对象，可允许有人未匹配，并仅向可接受对象提案。若偏好有并列，任意打破并列再运行算法可得到弱稳定匹配（weakly stable matching），即不存在双方都严格偏好彼此的阻挡对；更强稳定概念需要另外分析。
核心概念对照¶
| 概念 | 回答的问题 | 关键限制 |
|---|---|---|
| 核心 | 是否有联盟能偏离并获益？ | 可能为空，也不保证公平 |
| 最小核心 | 最少放宽多少稳定性要求？ | 最小化最大联盟缺口 |
| Shapley 值 | 如何按平均边际贡献分配？ | 一般不保证稳定；凸博弈例外 |
| 稳定匹配 | 是否有双方都愿意改配的阻挡对？ | 依赖两侧结构与偏好假设 |
| 延迟接受算法 | 如何高效找到稳定匹配？ | 提案方最优，另一方最差 |