19 · 怎么算公平

⏱ 44 分钟 ｜ ⭐⭐ EF 常常不存在，所以才有一整排「放松版」

🎯 一句话

一人分一堆东西时，「效率」不够用了 —— 本章给出一整条公平判据的阶梯：EF（谁都不眼红）→ EF1（去掉一件就不眼红）→ PROP（至少拿到 1/n）→ PROP1 → MMS（自己分堆最后挑），以及每一级为什么非放松不可。

🧩 一、换设定：这次是一人一堆

前两章都是「一人配一个」。这一章：$n$ 个人分 $m$ 件不可分割的物品，一个人可以拿好几件 —— 遗产分割、食物银行分捐赠、给快递员派件，都是这个形状。

分配实例 $\langle N, M, v\rangle$：分配 $A=(A_1,\dots,A_n)$ 是 $M$ 的一个 $n$-划分（每件物品恰好归一个人，全部分完）。

⚠️ 序数偏好在这里不够用了：要对所有子集排序，那是 $2^m$ 个集合 —— 表达不了也问不出来。所以改用基数估值：

可加估值：每个人给每件物品一个数 $v_i(g)\ge 0$，一堆的价值就是加起来 $v_i(S)=\sum_{g\in S} v_i(g)$，且 $v_i(\varnothing)=0$。

本章通篇的例子表（后面反复用）：

⚠️ 这些数字只在同一个人内部可比。「1 给 $g_1$ 打 100、3 打 30」不代表 1 比 3 更需要它 —— 每个人的标尺是自己的，这一点后面会咬人。

🧩 二、先用效率筛一遍：三种社会福利

帕累托最优（PO） 还是老定义：不存在另一个分配让所有人不变差、至少一人严格变好。PO 一定存在（分配数量有限），但PO 太弱了 —— 「把所有东西给 1」也是 PO。

① 功利福利（Utilitarian，USW）= 求和

$$\mathrm{USW}(A)=\sum_{i\in N} v_i(A_i)$$

⭐ 可加估值下最大化 USW 是一行代码的事：每件物品给对它出价最高的人。上表里 $g_1\to 1$、$g_2\to 1$、$g_3,g_4\to 3$、$g_5\to 2$，USW $=100+30+50+50+40=270$。

💀 但 USW 会算出灾难性的不公平 —— 只要一个人的估值整体偏高，最优解就把几乎所有东西塞给他。加总把「一个人损失 50」和「另一个人获得 50」当成一回事。

② 平等福利（Egalitarian，ESW）= 最小值：$\mathrm{ESW}(A)=\min_{i} v_i(A_i)$

$A=(\{g_1\},\{g_2,g_4,g_5\},\{g_3\})$ 三人的值是 $100,55,50$，ESW $=50$； $A'=(\{g_1\},\{g_2,g_5\},\{g_3,g_4\})$ 是 $100,50,100$，ESW 也是 $50$。 可 $A'$ 明显更好 —— 它把第二低的从 55 抬到 100。ESW 只盯最惨那个，看不见这个差别。

③ Leximin：把「只看最惨」推广成「逐层比」

leximin 元组 $L_A$：把 $n$ 个人的价值从小到大排成一列。$A$ leximin 支配 $A'$：存在位置 $t$ 使 $L_A[t] > L_{A'}[t]$，且前面所有位置都相等。

上例 $L_A=(50,55,100)$、$L_{A'}=(50,100,100)$ —— 第 1 位打平、第 2 位 $A'$ 更高，$A'$ leximin 支配 $A$。

leximin 最优一定存在、一定 PO、一定最大化 ESW（又叫罗尔斯式公平），但 💀 强 NP 难，而且有标尺问题：某人所有估值都极小时，为了抬高最小值会把一大堆东西塞给他。

④ Nash 福利 = 乘积：$\mathrm{NW}(A)=\prod_{i} v_i(A_i)$

乘积自带边际递减 —— 给已经拿很多的人加一件，乘积涨得少；给几乎空手的人加一件，涨得多。而且任何人拿 0，整个乘积归零，天然抗拒「有人颗粒无收」。下一章会证明它是这四个里最强的。

🧩 三、无嫉妒（EF）：最自然的那个定义

⭐ 无嫉妒（envy-free, EF）：对任意两人 $i,j$，都有 $v_i(A_i) \ge v_i(A_j)$。 —— 没有人想跟别人换手里的整堆东西。

EF 好在哪：只用自己的估值就能验证 —— 不用知道别人怎么想，把每一堆按自己的标尺算一遍，看自己那堆是不是最高。

手算：换一组估值

分配 $A=(\{g_1,g_5\},\{g_3\},\{g_2,g_4\})$： - 1 号看：自己 $100$，2 号那堆 $70$，3 号那堆 $80$ → 不嫉妒 - 2 号看：自己 $70$，1 号那堆 $60$，3 号那堆 $50$ → 不嫉妒 - 3 号看：自己 $3$，1 号 $3$，2 号 $2$ → 不嫉妒

$A$ 是 EF 的 ✓。

⚠️ 但 EF 经常根本不存在

两个人，一件物品。 谁拿到，另一个人就嫉妒。完。

这不是个刁钻反例，是不可分割物品的常态。（物品可分时 —— 蛋糕、土地、钱 —— EF 总是存在的，这也是切蛋糕理论比这一章轻松的原因。）

而且：判断一个实例有没有 EF 分配是强 NP 难的（同样从 3-划分归约）。

⚠️ 乘性放松救不了

自然的想法：不要求完全不嫉妒，要求「差不太多」—— $\alpha$-EF：$v_i(A_i) \ge \alpha\, v_i(A_j)$。

反例（任意固定 $\alpha \in (0,1]$，取 $0<\epsilon<\alpha$）：

两件东西两个人，无论怎么分，拿到 $g_2$ 的那个人手里是 $\alpha-\epsilon$，对方手里是 $1$，而 $\alpha-\epsilon < \alpha \cdot 1$。对任何 $\alpha>0$ 都没有 $\alpha$-EF 分配。

⭐ 教训很具体：这里的障碍是「离散」不是「差距」。乘性放松处理的是「差距」，所以完全无效。必须改成组合式的放松 —— 允许「拿掉一件」。

🧩 四、EF1：去掉一件就不嫉妒

⭐ EF1（envy-free up to one item，Budish 2011）：对任意 $i,j$，存在 $g\in A_j$ 使得 $$v_i(A_i)\ \ge\ v_i(A_j\setminus\{g\})$$ —— 我可能眼红你，但只要从你那堆里拿走某一件（挑对我最值钱的那件），我就不眼红了。

回到那个杀死 $\alpha$-EF 的两件物品实例：2 号拿 $g_2$（值 $\alpha-\epsilon$），嫉妒拿着 $g_1$ 的 1 号（值 1）。但去掉 $g_1$ 后 1 号那堆是 $0 < \alpha-\epsilon$ —— EF1 成立。原本无解的实例，现在有解了。

手算一个不是 EF1 的（用第三节那张表）：$A=(\{g_1\},\{g_2\},\{g_3,g_4,g_5\})$ —— 1 号自己只有 $10$，3 号那堆值 $230$，就算去掉最贵的 $g_5$ 还剩 $140>10$，去掉哪一件都不够 ✗

改成 $A'=(\{g_1,g_5\},\{g_3,g_4\},\{g_2\})$：1 号自己 $100$、2 号那堆 $140$ → 嫉妒，但去掉 $g_3$ 后剩 $70\le100$ ✓；2 号自己 $110$，看别人是 $60$ 和 $10$ → 不嫉妒 ✓；3 号自己 $1$、1 号那堆 $3$ → 嫉妒，去掉 $g_5$ 后剩 $1\le1$ ✓。$A'$ 是 EF1。

关系很清楚：EF ⟹ EF1，反过来不成立。

⭐⭐ 而 EF1 分配永远存在，而且多项式时间就能算出来。 这是整块理论的支点 —— 下一章给两个算法（轮流拿 + 嫉妒图），还会给一个同时保证 PO 的。

🧩 五、比例性：换个角度定「够不够」

EF 是相对判据（跟别人比）。另一条路是绝对判据（跟阈值比）：

比例性（PROP）：$v_i(A_i)\ \ge\ \tfrac{1}{n}\,v_i(M)$ —— 每个人至少拿到他心目中总价值的 $1/n$。

⭐ 定理：EF ⟹ PROP。 三行：EF 给出 $v_i(A_j)\le v_i(A_i)$ 对每个 $j$ 成立，求和得 $$v_i(M)=\sum_{j\in N} v_i(A_j) \le n\,v_i(A_i)$$ 除以 $n$ 即可。∎ 反过来不成立 —— PROP 只管「够 1/n」，不管别人拿了多少。

PROP 的现实分量比 EF 大：很多国家的遗产法、离婚财产分割法写的就是比例条款。

⚠️ 但 PROP 同样经常不存在（两人一件物品，没拿到的那个是 0）。于是同样放松：

PROP1：存在某件 $g \in M$ 使 $v_i(A_i \cup \{g\}) \ge \frac{1}{n} v_i(M)$ —— 再添一件我就达标。

⭐ 定理：EF1 ⟹ PROP1，所以下一章的算法顺带把 PROP1 也解决了。

💀 但 PROP1 可以难看到离谱：第一节那张表两个人分，$A=(M,\varnothing)$ 让 2 号拿 0；可 $v_2(\{g_1\})=100 > \frac{160}{2}=80$ —— 「一件不给」也是 PROP1 的。⚠️ 放松版判据是下限，不是目标。（$\alpha$-PROP 的反例和 $\alpha$-EF 一模一样，乘性放松同样无效。）

🧩 六、MMS：切蛋糕思想的推广

回到最古老的那个机制：一人切、另一人先挑。切的人会怎么切？他会切得两块在他眼里一样好 —— 因为他知道自己只能拿到剩下那块。

把它推广到 $n$ 个人：

⭐ 最大最小份额（maximin share，MMS）： $$\mathrm{MMS}_i \;=\; \max_{A}\ \min_{j\in N}\ v_i(A_j)$$ 「让 $i$ 自己把所有物品分成 $n$ 堆，然后别人先挑，他拿最后一堆」—— 他能保证到手的最高值。 分配 $A$ 是 MMS 公平的，如果每个 $i$ 都有 $v_i(A_i) \ge \mathrm{MMS}_i$。

手算（第一节的表，$n=3$）：1 号要把 5 件分成 3 堆并最大化最差那堆 —— $\{g_1\}=100$、$\{g_2\}=30$、$\{g_3,g_4,g_5\}=20$，最差是 20；换成 $\{g_2,g_3\}=35$ 和 $\{g_4,g_5\}=15$ 反而更差，所以 $\mathrm{MMS}_1=20$。同理 $\mathrm{MMS}_2=20$（$100/40/20$），$\mathrm{MMS}_3=45$（$50/50/45$）。

⭐ 总有 $\mathrm{MMS}_i \le \frac{1}{n} v_i(M)$（$n$ 堆的最小值不可能超过平均值）—— MMS 是打了折的比例性，比 PROP 更弱。

存在性：$n=2$ 时一人切一人挑就够了 —— 1 号切出的两堆对他都 $\ge \mathrm{MMS}_1$；2 号挑走更大的那堆，值 $\ge \frac{1}{2}v_2(M) \ge \mathrm{MMS}_2$。∎ 💀 但 $n\ge 3$ 时 MMS 分配可能不存在，已知反例只要 3 人 9 件物品。

计算：算单个 $\mathrm{MMS}_i$ 本身就 NP 难（$n=2$ 时从均衡划分归约）。所以只能近似：多项式时间目前能做到 $\frac{3}{4}+\frac{1}{12n}$-MMS（Garg & Taki 2020），而存在实例没有分配能好过 $\frac{39}{40}$-MMS（Feige 等 2021）。下一章会给一个非常好懂的 $\frac12$-MMS 贪心算法。

🧩 七、把阶梯摆在一起

蕴含关系（都是单向）：EF ⟹ EF1 ⟹ PROP1、EF ⟹ PROP。⚠️ 但 EF1 和 MMS 互不蕴含 —— 一个是相对的（跟别人比），一个是绝对的（跟自己的切分比），会互相打架。

⚠️ 别和机器学习里的「算法公平性」搞混： 那边的「公平」是同一个模型对不同人群的错误率是否一致（群体公平、机会均等）；这边的「公平」是每个人分到的那一份够不够。两个词同名，量的不是一件事。

🔗 这一章连到哪里

✅ 检查点

1. 为什么这一章要从序数偏好切换到基数估值？
2. USW 最大化为什么在可加估值下是「一行代码」？它会犯什么错？
3. $L_A=(50,55,100)$ 和 $L_{A'}=(50,100,100)$，谁 leximin 支配谁？ESW 能看出差别吗？
4. 用第三节那张表，验证 $A=(\{g_1,g_5\},\{g_3\},\{g_2,g_4\})$ 对 2 号是不是 EF。
5. 为什么 $\alpha$-EF 这种乘性放松救不了 EF？障碍到底是什么？
6. EF ⟹ PROP 的证明用了哪一步不等式？
7. 「一件不给」的分配为什么可能是 PROP1 的？这说明放松版判据该怎么用？
8. $\mathrm{MMS}_i$ 和 $\frac{1}{n}v_i(M)$ 哪个大？为什么？
9. $n=2$ 时 MMS 分配一定存在，靠的是什么机制？$n\ge3$ 呢？

🛑 可以停在这里

⚡ 走神救援

这一章从「一人一件」换到「一人一堆」：$n$ 个人分 $m$ 件不可分割物品。序数偏好在这里废了（要给 $2^m$ 个子集排序），改用可加基数估值 $v_i(S)=\sum_{g\in S}v_i(g)$。

效率不够用：PO 太弱，全给一个人也是 PO。四种社会福利中，USW（求和）多项式可算（每件给出价最高的人，例子表里 270）但极不公平；ESW（最小值）只看最惨的，分不出 $(50,55,100)$ 和 $(50,100,100)$；Leximin（价值从小到大排成元组比字典序）一定存在、一定 PO、一定最大化 ESW，但强 NP 难、受估值尺度影响；Nash 福利（乘积）有人拿 0 就整体归零，性质最好但算不动。

公平这边是一条放松的阶梯。⭐ EF：$v_i(A_i)\ge v_i(A_j)$，只用自己的估值就能验；但两人一件物品就不存在了，判存在性强 NP 难。乘性放松 $\alpha$-EF 完全无效 —— 两人估值都是 $(1,\alpha-\epsilon)$ 的反例对任何 $\alpha>0$ 都失败，因为障碍是离散不是差距。所以改成组合式放松：⭐ EF1：存在 $g\in A_j$ 使 $v_i(A_i)\ge v_i(A_j\setminus\{g\})$。EF1 总是存在、多项式可算，是整块理论的支点。

另一条路是绝对阈值：PROP 要求 $v_i(A_i)\ge \frac1n v_i(M)$，EF ⟹ PROP（三行求和证明），很多遗产法写的就是这条；同样常常不存在，放松成 PROP1（再添一件就达标），且 EF1 ⟹ PROP1。💀 但 PROP1 可以极难看：2 人例子里「一件都不给」也是 PROP1（$v_2(\{g_1\})=100>80$）—— 放松判据是下限不是目标。最后是 MMS：$\mathrm{MMS}_i=\max_A\min_j v_i(A_j)$，即「自己分 $n$ 堆、最后挑」，例子表里三人是 20、20、45，且总有 $\mathrm{MMS}_i\le\frac1n v_i(M)$。$n=2$ 靠一人切一人挑必然满足；💀 $n\ge3$ 可能不存在（3 人 9 件的反例），算 $\mathrm{MMS}_i$ 本身也 NP 难，只能近似（$\frac34+\frac1{12n}$ 可得，上界 $\frac{39}{40}$）。⚠️ 别把这里的「公平」和机器学习的「算法公平性（群体错误率一致）」混用。

下一节 👉 20-公平分配的算法.md