📑 本页目录（点开跳转）
20 · 公平分配的算法
⏱ 48 分钟 ｜ ⭐⭐ 最大化乘积，白送你 EF1 + PO
🎯 一句话
上一章说「EF1 一定存在」，这一章给出三个真能跑的算法：轮流拿（最快）、嫉妒图（最通用）、最大 Nash 福利（唯一同时保证 PO 的那个）。
🧩 一、Round-Robin：轮流拿最爱
最土的办法，也是最好用的。
- 随便定一个人的顺序 $i_1, i_2, \dots, i_n$
- 按顺序轮流叫号，轮到谁，谁就从剩下的物品里挑自己估值最高的一件
- 一圈叫完从头再来，直到物品分完
完整走一遍（顺序 1 → 2）：
| $g_1$ | $g_2$ | $g_3$ | $g_4$ | $g_5$ | |
|---|---|---|---|---|---|
| 1 | 100 | 30 | 5 | 10 | 5 |
| 2 | 100 | 10 | 5 | 5 | 40 |
| 轮 | 谁挑 | 挑走 | 之后 $A_1$ | $A_2$ |
|---|---|---|---|---|
| 1 | 1 | $g_1$（100 最高） | $\{g_1\}$ | $\varnothing$ |
| 1 | 2 | $g_5$（$g_1$ 没了，剩下最高是 40） | $\{g_1\}$ | $\{g_5\}$ |
| 2 | 1 | $g_2$（30） | $\{g_1,g_2\}$ | $\{g_5\}$ |
| 2 | 2 | $g_4$（5，与 $g_3$ 并列 —— ⭐ 这里我们取 $g_4$） | $\{g_1,g_2\}$ | $\{g_5,g_4\}$ |
| 3 | 1 | $g_3$ | $\{g_1,g_2,g_3\}$ | $\{g_5,g_4\}$ |
验 EF1：1 号自己 $135$、对方那堆 $15$ → 连嫉妒都没有 ✓。2 号自己 $45$、对方那堆 $110$ → 嫉妒；去掉 $g_1$ 后剩 $15 \le 45$ ✓ EF1。
⚠️ 并列怎么破，会改变最终数字 —— 但不改变结论。 第 2 轮 2 号在 $g_3$ 和 $g_4$ 之间并列（对他都是 5 分）。上面取了 $g_4$； 若改取 $g_3$，最后 1 号拿 $\{g_1,g_2,g_4\}$ = $100+30+10 = \mathbf{140}$、2 号仍是 $\mathbf{45}$。 ⭐ 两条分支都满足 EF1 —— 这正是定理的说法：Round-Robin 不管你怎么破并列，产出的一定是 EF1 分配。 💡 但要注意它们不是同一个分配，福利也不同（135+45 = 180 vs 140+45 = 185）。 「算法保证某个性质」和「算法有唯一输出」是两件事，这个区别在后面查 PO、比福利时会反复用到。
⭐ 为什么它一定 EF1（论证很短，值得看）
记 $g_t^i$ 是 $i$ 第 $t$ 次挑走的那件。核心观察只有一条：
$i$ 第 $t$ 次挑的时候，$j$ 第 $t$ 次要挑的东西还在桌上（如果 $i$ 排在 $j$ 前面）或已经被挑走（如果 $j$ 在前）。 于是对任意 $t < t'$ 都有 $v_i(g^i_t) \ge v_i(g^j_{t'})$ —— $i$ 自己第 $t$ 轮挑的，不会比 $j$ 更晚挑的那件差（不然 $i$ 当时就该挑那件）。
- 情况 1：$i$ 排在 $j$ 前面。 每一轮 $i$ 都先挑，所以 $v_i(g^i_t) \ge v_i(g^j_t)$ 逐轮成立，加起来就是 $v_i(A_i)\ge v_i(A_j)$ —— 直接 EF，比 EF1 还强。
- 情况 2：$j$ 排在 $i$ 前面。 把 $j$ 第一轮挑的那件 $g^j_1$ 划掉。剩下的 $g^j_2, g^j_3,\dots$ 逐个对应 $i$ 的 $g^i_1, g^i_2,\dots$，每一对都有 $v_i(g^i_{t-1}) \ge v_i(g^j_t)$。求和：$v_i(A_j \setminus \{g^j_1\}) \le v_i(A_i)$ —— EF1 ✓ ∎
顺带的好处：每个人恰好拿到 $\lfloor m/n\rfloor$ 或 $\lceil m/n\rceil$ 件 —— 结果是均衡的。要求「每人恰好 $k$ 件」时只有它能用。运行时间 $O(mn)$（预排序后）。
⚠️ 但 Round-Robin 不保证 PO。 最小反例：两人两件，$v_1=(1,1)$、$v_2=(1,0)$。顺序 1→2 时 1 号先挑（并列取 $g_1$），2 号只能拿 $g_2$，效用是 $(1,0)$。可换成 1 拿 $g_2$、2 拿 $g_1$，效用是 $(1,1)$ —— 1 号一点没亏，2 号白赚，原分配被帕累托支配。
🧩 二、嫉妒图算法：给「没人眼红的人」发东西
Round-Robin 强制每人轮流拿一件。如果想更自由地一件一件发（比如物品陆续到货），得换个思路。
嫉妒图 $G_A$：点是人，从 $i$ 画一条边到 $j$ 当且仅当 $v_i(A_i) < v_i(A_j)$（$i$ 眼红 $j$）。 分配是 EF ⟺ 嫉妒图一条边都没有。
现在一件一件发。发给谁是安全的？
- 给一个被人眼红的人再加东西 → 眼红他的人可能直接爆掉 EF1 ✗
- 给一个没有入边的人（source，谁都不眼红他）加一件 → 别人本来就不眼红他，加了这一件之后去掉这一件就回到原状，EF1 一定保住 ✓
⚠️ 但 source 可能不存在 —— 图里有环的时候。两人的例子：$A_1=\{g_5\}$、$A_2=\{g_4\}$，用第一节那张表，$v_1(A_1)=5 < v_1(A_2)=10$（1 眼红 2），$v_2(A_2)=5 < v_2(A_1)=40$（2 眼红 1）—— 互相眼红，没有 source。
⭐ 破环的办法：沿着环轮换整堆物品。 环上每个人拿走他所眼红的那个人的整堆。
为什么轮换是安全的：物品一件没多、一件没少，每个人换到的是他本来就更眼馋的那堆，所以每个人的价值只增不减。价值只增不减 ⟹ 不会冒出新的嫉妒边 ⟹ 边数严格下降。所以破环不会无限进行。
算法
- 所有人从空手开始
- 只要还有没发的物品：找嫉妒图的一个 source，把任意一件物品发给他
- 发完检查是否成环，成环就沿环轮换整堆，重复到无环
- 回到第 2 步
完整走一遍（还是第一节那张 2 人表）：
| 步 | 动作 | $A_1$ | $A_2$ | 嫉妒图 |
|---|---|---|---|---|
| 1 | 都是 source，给 1 号 $g_5$ | $\{g_5\}$ | $\varnothing$ | $v_2$: 自己 0 < 对方 40 → 2 → 1 |
| 2 | source 是 2，给它 $g_4$ | $\{g_5\}$ | $\{g_4\}$ | $v_1$: 5 < 10 → 1→2；$v_2$: 5 < 40 → 2→1，成环 |
| 3 | 沿环轮换两堆 | $\{g_4\}$ | $\{g_5\}$ | $v_1$: 10 > 5 ✓；$v_2$: 40 > 5 ✓ 无边 |
| 4 | 都是 source，给 1 号 $g_3$ | $\{g_4,g_3\}$ | $\{g_5\}$ | 无边 |
| 5 | source 给 2 号 $g_2$ | $\{g_4,g_3\}$ | $\{g_5,g_2\}$ | $v_1$: 15 < 35 → 1→2 |
| 6 | source 是 1，给它 $g_1$ | $\{g_4,g_3,g_1\}$ | $\{g_5,g_2\}$ | $v_2$: 50 < 110 → 2→1 |
发完了。最后检查 EF1：2 号眼红 1 号（$110 > 50$），但去掉 $g_1$ 后只剩 $10 \le 50$ ✓ EF1。
⭐ 注意第 3 步：轮换之后 1 号从 5 涨到 10、2 号从 5 涨到 40，两条边同时消失 —— 这就是「破环只会让边变少」的实例。
性质
- 正确性（归纳）：发第 $t$ 件之前是 EF1；发出去时收货人是 source，所以对任何 $j$ 都有 $v_j(A_j) \ge v_j(A_{i_t}\setminus \{g_t\})$ —— 仍然 EF1。破环只会让每个人的值变大、堆的集合不变，所以破环后依然 EF1。∎
- 复杂度：每发一件最多加 $n-1$ 条边，全程最多 $m(n-1)$ 条；每次破环至少去掉 2 条边，所以最多破 $m(n-1)/2$ 次环，找环用 DFS 是 $O(n^2)$ ⟹ 总共 $O(mn^3)$
- ⭐ 适用面比 Round-Robin 宽：它不需要可加估值，只要单调（$v(S\cup\{g\}) \ge v(S)$）就成立
- ⚠️ 但它不能做均衡分配：要求每人恰好 $k$ 件时，算法可能死死盯着一个已经拿满 $k$ 件的 source 不放，卡住。这种场合必须用 Round-Robin
🧩 三、最大 Nash 福利：一个目标函数换来两个性质
前两个算法都只保证 EF1，都不保证 PO。这一个两样全有。
⭐ MNW（Maximum Nash Welfare）：先最大化「拿到严格正效用的人数」，在这批人上最大化 $\prod_i v_i(A_i)$。 ⚠️ 前半句不能省 —— 有人拿 0 时乘积恒为 0，不先定人数的话所有这类分配都「并列最优」，没法区分好坏。
手算（$n=2$，$m=4$）：
| $o_1$ | $o_2$ | $o_3$ | $o_4$ | |
|---|---|---|---|---|
| 1 | 6 | 2 | 3 | 1 |
| 2 | 4 | 1 | 2 | 3 |
枚举几个分配的乘积：
| $X_1$ | $X_2$ | $v_1$ | $v_2$ | 乘积 |
|---|---|---|---|---|
| $\{o_1,o_2\}$ | $\{o_3,o_4\}$ | 8 | 5 | 40 ⭐ |
| $\{o_1,o_3\}$ | $\{o_2,o_4\}$ | 9 | 4 | 36 |
| $\{o_1\}$ | $\{o_2,o_3,o_4\}$ | 6 | 6 | 36 |
| $\{o_1,o_2,o_3\}$ | $\{o_4\}$ | 11 | 3 | 33 |
| $\{o_1,o_2,o_4\}$ | $\{o_3\}$ | 9 | 2 | 18 |
最大是 40。验一下：1 号自己 8、对方那堆 $3+1=4$ → 不嫉妒；2 号自己 5、对方那堆 $4+1=5$ → 不嫉妒。这个解甚至是完全 EF 的。
⚠️ 对照 USW：$X_1=\{o_1,o_2,o_3\}$、$X_2=\{o_4\}$ 的 USW 是 $11+3=14$，比 MNW 解的 $8+5=13$ 高，可 2 号只拿到 3。求和把差距拉大，乘积把差距压平。
⭐⭐ 定理（Caragiannis 等 2019）：任何 MNW 分配都同时是 EF1 和 PO 的。
PO 部分一行：帕累托改进会让某人的值严格变大、其他人不变小 ⟹ 乘积严格变大 ⟹ 与「已经最大」矛盾。
EF1 部分的直觉（这才是漂亮的地方）：假设 $i$ 眼红 $j$，而且去掉 $j$ 那堆里的任何一件都还眼红。那就从 $j$ 手里挑出这一件：
$$g^{*} = \arg\min_{g\in A_j,\ v_i(g)>0} \frac{v_j(g)}{v_i(g)}$$
也就是 「对 $j$ 最不值钱、对 $i$ 最值钱」的那一件。把 $g^*$ 从 $j$ 挪给 $i$：$i$ 的值涨的比例，比 $j$ 的值跌的比例更大 —— 于是乘积严格变大，和 MNW 矛盾。∎ （$i$ 「去掉任何一件仍眼红」这个假设，正好保证了那个比例算得过来。）
💀 代价：计算 MNW 是 NP 难的（连常数近似都很难）。实践中用整数规划求解 —— 真实上线的分配网站 spliddit.org 就是这么干的，遗产、房租、家务分摊都能算。
🧩 四、顺手把 MMS 也解决一半
上一章留了个尾巴：MMS 分配 $n\ge3$ 时可能不存在，怎么办？贪心版 Round-Robin 给出 $\frac12$-MMS：
- 记 $\beta_i = v_i(P)/|I|$（$P$ 是剩余物品、$I$ 是剩余的人）
- 只要存在某个人 $i$ 和某件物品 $g$ 满足 $v_i(g) \ge \beta_i/2$：把 $g$ 单独给 $i$，把 $i$ 移出局，重算所有 $\beta$
- 剩下的人和物品跑普通 Round-Robin
⭐ 两种人两种论证：第 2 步出局的人，一件就拿到了 $\beta_i/2 \ge \mathrm{MMS}_i/2$；留到第 3 步的人，桌上已经没有大件（每件都小于 $\beta_i/2$），而 Round-Robin 保证 EF1，EF1 减去一件小东西还剩一半 —— 同样 $\ge \mathrm{MMS}_i/2$。∎
关键的一步是上一章那条引理：$\frac{v_i(P)}{|I|} \ge \mathrm{MMS}_i(|I|,P) \ge \mathrm{MMS}_i(n,M)$ —— 人越少、物品越多，MMS 门槛只会更高不会更低，所以拿走一个人和一件物品之后的估算依然是安全下界。
🧩 五、三个算法怎么选
| Round-Robin | 嫉妒图 | MNW | |
|---|---|---|---|
| 保证 | EF1、PROP1、均衡 | EF1、PROP1 | EF1 + PO ⭐ |
| 复杂度 | $O(mn)$ | $O(mn^3)$ | NP 难 |
| 估值要求 | 必须可加 | 只需单调 | 可加 |
| 什么时候用它 | 默认选它；要求每人 $k$ 件时只能用它 | 物品陆续到货、估值不可加 | 人少、要效率保证、能上求解器 |
⭐ 一句话决策：能接受「只保 EF1」就用 Round-Robin，非要 PO 就上 MNW 并做好算不动的准备。
🔗 这一章连到哪里
| 去哪 | 为什么 |
|---|---|
| 19-怎么算公平.md | EF1 / PROP1 / MMS 的定义和「为什么必须放松」都在那儿。本章只负责把它们算出来 |
| 21-有钱与随机分配.md | 嫉妒图在下一章会长出边权：权重变成「嫉妒了多少」，于是能算出「补多少钱才不嫉妒」 |
| ../模型上线之后/15-长期效应与代理指标.html | USW 和 Nash 福利是两种截然不同的「总目标」。那边讲的正是「优化了一个加总指标却毁掉分布」这类事故 |
✅ 检查点
- Round-Robin 里，「$i$ 排在 $j$ 前面」这种情况得到的结论比 EF1 更强，强在哪？
- 情况 2 的证明为什么要专门划掉 $j$ 第一轮挑的那件？划第二轮的行不行？
- $v_1=(1,1)$、$v_2=(1,0)$ 这个反例说明了 Round-Robin 的什么缺陷？帕累托改进具体是怎么换的？
- 嫉妒图里为什么给 source 发东西是安全的，给被眼红的人发就不安全？
- 沿环轮换整堆之后，为什么保证不会冒出新的嫉妒边？
- 手算例子第 3 步轮换后两个人的值分别变成了多少？边数怎么变的？
- 嫉妒图算法比 Round-Robin 宽在哪、窄在哪？
- MNW 的定义为什么要先最大化「拿到正效用的人数」？
- MNW ⟹ EF1 的论证里，那个被挪走的 $g^*$ 是按什么标准挑的？为什么是这个标准？
- 贪心 Round-Robin 里第 2 步出局的人和第 3 步留下的人，分别靠什么论证拿到 $\frac12$-MMS？
👀 答案
- 强在它是完全 EF（不只是 EF1）：$i$ 每一轮都先挑，所以 $v_i(g^i_t)\ge v_i(g^j_t)$ 逐轮成立，求和直接得 $v_i(A_i)\ge v_i(A_j)$。
- 因为 $j$ 第一轮挑的那件是唯一一件「$i$ 还没挑过任何东西就被拿走」的物品，没有 $i$ 的物品能与它配对。划掉它之后，$j$ 的第 $t$ 件正好能和 $i$ 的第 $t-1$ 件配对（$v_i(g^i_{t-1})\ge v_i(g^j_t)$）。划第二轮的话第一轮那件配不上对，不等式链断掉。
- 说明 Round-Robin 不保证 PO。1 号先挑（两件并列，取 $g_1$），2 号只剩 $g_2$，效用 $(1,0)$；换成 1 拿 $g_2$、2 拿 $g_1$ 就是 $(1,1)$ —— 1 号一点不亏、2 号白赚，原分配被帕累托支配。
- source 是没有入边的点：谁都不眼红他。给他加一件之后，别人对他的嫉妒「去掉这一件」就回到了原来的无嫉妒状态，EF1 天然保住。给被眼红的人加东西则会把已有的嫉妒继续放大，可能一件都减不回来。
- 因为轮换只是交换整堆，物品没增没减，而环上每个人换到的正是他本来就更眼馋的那堆 —— 每个人的值只增不减。值只增不减就不可能产生新的嫉妒关系，所以边只会变少。
- 轮换前 $A_1=\{g_5\}$（$v_1=5$）、$A_2=\{g_4\}$（$v_2=5$）互相眼红共 2 条边；轮换后 $A_1=\{g_4\}$ 值 10、$A_2=\{g_5\}$ 值 40，两条边同时消失，剩 0 条。
- 宽在估值只需单调（$v(S\cup\{g\})\ge v(S)$）而不必可加，且可以一件一件随到随发；窄在做不了均衡分配 —— 要求每人恰好 $k$ 件时，算法可能一直指着已经拿满的 source，卡死。复杂度也从 $O(mn)$ 涨到 $O(mn^3)$。
- 因为只要有一个人拿 0，乘积就是 0，所有这类分配会「并列最优」，目标函数分不出好坏。先把「有正效用的人数」拉满，才能保证不会为了省事让人颗粒无收。
- $g^*=\arg\min_{g\in A_j,\,v_i(g)>0} \frac{v_j(g)}{v_i(g)}$ —— 对 $j$ 最不值钱、对 $i$ 最值钱的那一件。挪走它时 $j$ 的相对损失最小、$i$ 的相对收益最大，于是乘积严格变大，与 MNW 最优矛盾。
- 第 2 步出局的人：他拿的那一件本身就 $\ge \beta_i/2 = \frac{v_i(P)}{2|I|} \ge \frac{\mathrm{MMS}_i}{2}$。第 3 步留下的人：此时桌上每一件都小于 $\beta_i/2$，而 Round-Robin 保证 EF1，把「少的那一件」减掉后仍有一半的量 —— 同样 $\ge \mathrm{MMS}_i/2$。两处都用到引理 $\frac{v_i(P)}{|I|}\ge \mathrm{MMS}_i(n,M)$。
🛑 可以停在这里
⚡ 走神救援
上一章证明了 EF1 一定存在，这一章给算法。
⭐ Round-Robin：定个顺序轮流叫号，轮到谁谁就从剩下的挑自己估值最高的一件。手算的 2 人 5 物例子跑出 $A_1=\{g_1,g_2,g_3\}$（值 135）、$A_2=\{g_5,g_4\}$（值 45）；2 号眼红对方的 110，但去掉 $g_1$ 只剩 15，EF1 ✓。它 EF1 的论证只有两句：$i$ 排在 $j$ 前面时逐轮都有 $v_i(g^i_t)\ge v_i(g^j_t)$，求和直接得到完全 EF；$j$ 排在前面时把 $j$ 第一轮那件划掉，剩下的逐个对应 $i$ 的前一轮，求和得 EF1。优点：$O(mn)$、结果均衡（每人 $\lfloor m/n\rfloor$ 或 $\lceil m/n\rceil$ 件），要求「每人恰好 $k$ 件」时只有它能用。⚠️ 缺点：不保证 PO，最小反例是 $v_1=(1,1)$、$v_2=(1,0)$ —— 换一下就能让 2 号白赚。
⭐ 嫉妒图算法：点是人，$i\to j$ 表示 $i$ 眼红 $j$；EF ⟺ 图无边。一件一件发，只发给 source（没有入边的人），因为「去掉刚发的这一件就回到原状」，EF1 天然保住。没有 source 说明有环，就沿环轮换整堆 —— 物品没变、每个人换到的是他本来更眼馋的那堆，值只增不减，所以边只会变少，破环必然终止。手算里第 3 步轮换后两人从 5、5 变成 10、40，两条边同时消失。复杂度 $O(mn^3)$；⭐ 它只要求估值单调、不必可加，但做不了均衡分配。
⭐⭐ MNW（最大 Nash 福利）：先最大化拿到正效用的人数，再最大化 $\prod_i v_i(A_i)$（前半句不能省，否则有人拿 0 时全部并列）。手算的 4 物例子里最优是 $X_1=\{o_1,o_2\}$、$X_2=\{o_3,o_4\}$，乘积 $8\times5=40$ —— 而 USW 更高的那个方案会把 2 号压到 3。定理（Caragiannis 等 2019）：MNW ⟹ EF1 且 PO。 PO 一行（帕累托改进会让乘积变大）；EF1 的关键是挑出 $g^*=\arg\min v_j(g)/v_i(g)$（对 $j$ 最不值钱、对 $i$ 最值钱的那件）挪给 $i$，乘积严格变大导出矛盾。💀 代价是计算 NP 难，实务上整数规划求解（spliddit.org 就是这么做的）。
最后顺手补上 MMS：贪心 Round-Robin 给 $\frac12$-MMS —— 先把「有一件就值 $\beta_i/2$ 以上」的人用一件物品打发走并重算 $\beta$，剩下的人跑普通 Round-Robin。两拨人分别靠「那一件够大」和「桌上已无大件 + EF1」拿到一半的 MMS。选型一句话：能接受只保 EF1 就用 Round-Robin，非要 PO 就上 MNW 并做好算不动的准备。
下一节 👉 21-有钱与随机分配.md