无嫉妒、比例与 MMS,能排成一条公平阶梯吗?
读后可检查:用各自定义比较同一份分配,区分可分性与不可分物品带来的条件。
📑 本页目录(点开跳转)
19 · 怎么算公平
⏱ 34 分钟 | 时间仅供参考,可分次读;先分清“跟谁比”,再看判据
🎯 一句话
公平不是一把尺子:你可以跟别人拿到的东西比,也可以跟自己的最低份额比。满足其中一种,不代表满足其他所有种。
先带着这个问题读:三个人分五件东西,某人拿得少,就一定不公平吗?答案取决于他如何评价这些东西,以及你采用哪条规则。
- 别人为什么眼红? 从 EF 与 EF1 开始。
- 自己拿得够不够? 看 PROP 与 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$。
本章通篇的例子表(后面反复用):
| $g_1$ | $g_2$ | $g_3$ | $g_4$ | $g_5$ | 合计 | |
|---|---|---|---|---|---|---|
| 1 | 100 | 30 | 5 | 10 | 5 | 150 |
| 2 | 100 | 10 | 5 | 5 | 40 | 160 |
| 3 | 30 | 10 | 50 | 50 | 5 | 145 |
读表时固定一行:1 号看 $g_1$ 是 100,看 $g_2$ 是 30,看两件放在一起就是 130。
这些分数首先是同一个人的标尺。“1 号打 100、3 号打 30”本身不证明前者更需要它。下面仍会演示求和、取最小值等福利目标,但使用它们作跨人比较,需要说明采用了什么共同单位或归一化约定。
🧩 二、先用效率筛一遍:四种社会福利
帕累托最优(PO):不存在另一个分配让所有人不变差、至少一人严格变好。有限个分配中一定能找到 PO 分配,但 PO 不等于公平。
例如上表每件东西对 1 号都有正价值。全部给 1 号时,只要拿走一件,他就会变差,因此这个分配也是 PO,却让另外两人空手。若有东西对 1 号值 0、对别人有正价值,这个结论就不成立。
① 求和:总分有多高
功利福利(Utilitarian,USW)就是各人所得分数相加:
$$\mathrm{USW}(A)=\sum_{i\in N} v_i(A_i)$$
可加且没有额外分配限制时,最大化 USW 可以逐件决定:每件给报分最高的人,并列时任选。物品之间没有搭配加成,所以不必试所有组合。
上表可以把 $g_1,g_2$ 给 1 号,$g_3,g_4$ 给 3 号,$g_5$ 给 2 号。最大总分为 $100+30+50+50+40=270$。
风险是:若某人的分数普遍很高,求和可能偏向他。把“一人损失 50”和“另一人获得 50”直接抵消,是这个目标的选择,不是公平性的证明。
② 取最小值:只照顾最低分吗
平等福利(Egalitarian,ESW)只取各人所得中的最小值:$\mathrm{ESW}(A)=\min_i v_i(A_i)$。
| 分配 | 1 号所得 | 2 号所得 | 3 号所得 | 三人自己的分数 | ESW |
|---|---|---|---|---|---|
| $A$ | $g_1$ | $g_2,g_4,g_5$ | $g_3$ | $(100,55,50)$ | 50 |
| $A'$ | $g_1$ | $g_2,g_5$ | $g_3,g_4$ | $(100,50,100)$ | 50 |
ESW 分不出这两个分配。注意:$A'$ 不是对 $A$ 的帕累托改进,因为 2 号从 55 降到了 50。下面的 leximin 会选择 $A'$,是因为它采用了另一条比较规则。
③ 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 难
当人数也是输入的一部分,可以用 3-Partition(3-划分)说明困难:给 $3n$ 个数,总和为 $nB$,每个数都在 $B/4$ 与 $B/2$ 之间,让所有人对每件物品的估值等于对应的数。
若最大 ESW 能达到 $B$,总和约束迫使每人恰好拿到价值 $B$;每组也恰好有三个数。这就解出了强 NP 完全的 3-Partition。leximin 最优一定最大化 ESW,因此求它同样至少这么难。这里说的是一般输入的最坏情形,不是说本章五件物品也算不动。
④ Nash 福利:兼顾各人的相对增益
Nash 福利取各人所得的乘积:$\mathrm{NW}(A)=\prod_i v_i(A_i)$。
当各人所得都大于 0 时,同样增加 1 分,给低分者带来的相对增幅更大。例如 $(2,10)$ 的乘积是 20;给前者加 1 变成 30,给后者加 1 只变成 22。
这也可以用“最大化各人分数的对数之和”理解。不是原始乘积对每个人的分数都具有边际递减:固定其他人时,乘积对某一人的分数是线性的。
若有人得 0,乘积就为 0;但若所有可行分配都含 0,单看乘积完全分不出优劣。下一章会补上“先让尽可能多人获得正价值”的规则,再说明最大 Nash 福利的 EF1 与 PO 保证。它不是对所有公平标准都“最强”。
| 福利 | 定义 | 存在性 | 好不好算 | 毛病 |
|---|---|---|---|---|
| USW | 求和 | ✓ | 多项式(逐件取最大) | 可能偏向高报分者 |
| ESW | 最小值最大化 | ✓ | NP 难 | 看不见第二惨的人 |
| Leximin | 元组字典序 | ✓ | 强 NP 难 | 受估值尺度影响、难验证 |
| Nash | 乘积,零值须补规则 | ✓ | NP 难 | 有 EF1 与 PO 保证,不保证所有公平标准 |
🧩 三、无嫉妒(EF):最自然的那个定义
⭐ 无嫉妒(envy-free, EF):对任意两人 $i,j$,都有 $v_i(A_i) \ge v_i(A_j)$。 —— 没有人想跟别人换手里的整堆东西。
EF 好在哪:只用自己的估值就能验证 —— 不用知道别人怎么想,把每一堆按自己的标尺算一遍,看自己那堆是不是最高。
手算:换一组估值
| $g_1$ | $g_2$ | $g_3$ | $g_4$ | $g_5$ | |
|---|---|---|---|---|---|
| 1 | 10 | 10 | 70 | 70 | 90 |
| 2 | 10 | 10 | 70 | 40 | 50 |
| 3 | 1 | 1 | 2 | 2 | 2 |
分配 $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,不是在估计现实里有多少比例的实例无解。
如果改成可分、价值随份额线性增加、没有额外限制,每种物品都给每人 $1/n$,就能得到 EF。实际土地分割若要求连通等额外条件,不能仅凭“可分”就照搬这个保证。
判断一般实例有没有 EF 分配也是强 NP 难的:在前面的 3-Partition 构造中,所有人估值相同,EF 就要求各堆同值,恰好对应等和划分。
⚠️ 乘性放松不能保证总有解
自然的想法:不要求完全不嫉妒,要求「差不太多」—— $\alpha$-EF:$v_i(A_i) \ge \alpha\, v_i(A_j)$。
反例(任意固定 $\alpha \in (0,1]$,取 $0<\epsilon<\alpha$):
| $g_1$ | $g_2$ | |
|---|---|---|
| 1 | 1 | $\alpha-\epsilon$ |
| 2 | 1 | $\alpha-\epsilon$ |
如果每人一件,拿 $g_2$ 的人只有 $\alpha-\epsilon<\alpha\cdot1$,不达标。如果两件全给一人,另一人得 0,也不达标。
因此,对每个固定的 $\alpha\in(0,1]$,都能构造一个没有 $\alpha$-EF 分配的实例。不是说一个固定实例会对所有正数 $\alpha$ 同时无解。
结论是:单靠固定比例的放松,仍不能保证总有解。下面研究另一种办法——允许在比较时“拿掉至多一件”。转账或随机分配也是不同出路,会在第 21 章讨论。
🧩 四、EF1:去掉一件就不嫉妒
EF1(envy-free up to one item):对任意 $i,j$,若 $A_j$ 为空,自动满足;否则存在 $g\in A_j$ 使得 $$v_i(A_i)\ \ge\ v_i(A_j\setminus\{g\})$$ —— 我可能眼红你,但只要从你那堆里拿走某一件(挑对我最值钱的那件),我就不眼红了。
这里只是假想移除后做比较,物品没有真的被收走。不同的比较者可以选择不同的那一件。这个放松标准在 Budish(2011)的研究中得到系统使用。
回到刚才没有 $\alpha$-EF 解的两件物品实例:2 号拿 $g_2$(值 $\alpha-\epsilon$),嫉妒拿 $g_1$ 的 1 号。但去掉 $g_1$ 后,对方那堆变成 0,不超过自己所得。1 号原本就不嫉妒,所以这个分配满足 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\})$。它不是 EF1:3 号自己只有 1,而 2 号那堆按 3 号的估值是 $2+2=4$,去掉一件还剩 $2>1$。
可以改成 $B=(\{g_1,g_5\},\{g_2,g_3\},\{g_4\})$。这次逐人、逐堆检查:
| 评价者 | 看 1 号 | 看 2 号 | 看 3 号 |
|---|---|---|---|
| 1 号 | 自己:100 | 80 | 70 |
| 2 号 | 60 | 自己:80 | 40 |
| 3 号 | 3 | 3 | 自己:2 |
1、2 号自己的分数不低于任何一堆,原本就不嫉妒。3 号看 1 号时去掉 $g_5$,看 2 号时去掉 $g_3$,两堆都从 3 降到 1,不超过自己的 2。
所以 $B$ 是 EF1,但不是 EF。要验证“对所有人都成立”,不能只挑几对有利的比较。
关系很清楚: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」,不管别人拿了多少。
这里的 $1/n$ 是平等权益的数学模型,不等同于现实法律规定的份额,也不是按物品件数平均分。
⚠️ 但 PROP 同样经常不存在(两人一件物品,没拿到的那个是 0)。于是同样放松:
PROP1:对每个人 $i$,要么已经达到 PROP,要么存在一件不属于自己的物品 $g\in M\setminus A_i$,假想添上后达到 PROP。
$$v_i(A_i\cup\{g\})\ge \frac{v_i(M)}{n}$$
“添一件”也只用于检验,不是真的重复分配物品。已经拿得够多,或全部物品都没有价值时,不需要再找一件才能算达标。
⭐ 定理:EF1 ⟹ PROP1,所以下一章的算法顺带把 PROP1 也解决了。
但 PROP1 不保证每个人都拿到正价值。 只取第一张表的 1、2 号,两人分全部五件物品。全给 1 号时,他已达标;2 号虽然得 0,但假想添上 $g_1$ 就有 $100>160/2=80$,所以也满足 PROP1。
对 PROP 作固定正比例的放松,也不能保证总有解:两人只有一件双方都认为有正价值的东西,空手者连正比例门槛都达不到。这里不需要沿用前面的双物品反例;那个反例的参数不能直接照抄。
可选:EF1 为什么能保证 PROP1
固定一个还未达到 PROP 的人 $i$,记他已有价值为 $a$,其余物品中对他最贵的一件价值为 $b$。EF1 说明,每个别人的堆最多比他多出其中一件的价值,因此每堆不超过 $a+b$。
$$v_i(M)\le na+(n-1)b$$
所以 $a+b\ge v_i(M)/n$;假想添上那件值 $b$ 的物品就足够了。这个推理用到了非负、可加和全部分完的假设。
🧩 六、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$。
先看能达到的数值
用第一节的表,分别让每个人按自己的估值分三堆:
| 评价者 | 第一堆 | 第二堆 | 第三堆 | 最差那堆 |
|---|---|---|---|---|
| 1 号 | $g_1$:100 | $g_2$:30 | $g_3,g_4,g_5$:20 | 20 |
| 2 号 | $g_1$:100 | $g_5$:40 | $g_2,g_3,g_4$:20 | 20 |
| 3 号 | $g_3$:50 | $g_4$:50 | $g_1,g_2,g_5$:45 | 45 |
这说明三人的 MMS 至少为 20、20、45。每行是一个人自己设想的分堆,不是要求三行同时作为实际分配。
可选:为什么这三个数确实是最优,而不只是某次分堆结果
- 1 号:含 $g_1$ 的堆之外,另两堆最多能用剩余价值 50,其中 $g_2$ 单件就值 30。不含 $g_2$ 的那一堆只能从另外三件中拿,最多 20。因此不可能让三堆都超过 20。
- 2 号:同理,排除 $g_1$ 后的价值为 60,其中 $g_5$ 占 40。另一个不含 $g_5$ 的堆最多 20。
- 3 号:$g_3,g_4$ 各值 50。三堆中至少有一堆不含这两件,它最多拿到其他三件,总值 45。
上界和表中的可行方案相等,才能宣布 $\mathrm{MMS}=(20,20,45)$。只比较两种方案(例如 1 号把 30 和 5 放一起,剩下一堆变成 15),不能证明全局最优。
⭐ 总有 $\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 件物品。
计算困难,不等于每个实例都只能近似。 精确计算单人的 MMS 在一般情形下 NP 难;两人时,判断能否达到总价值的一半就包含 Partition 问题。五件物品的小例子仍可以手算或枚举。
“没有精确公平分配”和“有解但求起来难”是两件事。下一章会给 $\tfrac12$-MMS 算法及其门槛条件,先理解它保证了多少,不必先背研究纪录。
可选:原来提到的近似比例,应怎样准确理解
以下是有年份的研究结果,不宣称是当前最佳纪录:
🧩 七、这些标准不是一条阶梯
| 判据 | 说的是什么 | 一定存在? | 自己能验吗 | 算不算得动 |
|---|---|---|---|---|
| EF | 不想跟任何人换整堆 | ❌ 两人一物就没了 | ✓ 只需自己的估值 | 判存在性强 NP 难 |
| EF1 | 去掉你那堆里的某一件后就不眼红 | ✅ 总是存在 ⭐ | ✓ | 多项式 ⭐ |
| PROP | 至少拿到我心中总值的 $1/n$ | ❌ | ✓ 且不用看别人 | NP 难 |
| PROP1 | 再添一件就达标 | ✅(EF1 ⟹ PROP1) | ✓ | 多项式 |
| MMS | 自己分成 $n$ 堆、最后挑,能保住的那个值 | ❌ $n\ge3$ 可能没有 | 需知道或界定 MMS 门槛 | 精确计算一般困难,小实例可枚举 |
本章直接说明的蕴含包括:EF ⇒ EF1 ⇒ PROP1,以及 EF ⇒ PROP ⇒ MMS;PROP 也直接蕴含 PROP1。 不能把它们排成“EF1 ⇒ PROP”的直线。
用两个小例子记住“不蕴含”
例子 A:EF1 不保证 MMS 或 PROP。 两人、三件物品,每人的估值都是 $(10,1,1)$。让一人只拿一件值 1 的物品,另一人拿剩下的两件。
- 从大堆去掉值 10 的物品后只剩 1,因此满足 EF1。
- 两人各自的 MMS 是 2(可分成 10 与 2),PROP 门槛是 6。只拿 1 的人两项都没达到。
例子 B:MMS 不保证 EF1。 三人、五件物品,每件对每人都值 1。按件数分成 $(1,3,1)$。
- 每人的 MMS 都是 1(分成 2、2、1 已最优),因此三人都满足 MMS。
- 大堆去掉一件还剩 2,拿 1 的人仍嫉妒,因此不是 EF1。
因此 EF1 与 MMS 在一般情形下互不蕴含。第一例还直接说明 EF1 不蕴含 PROP。
⚠️ 别和机器学习里的「算法公平性」搞混: 机器学习中的公平性可能比较不同人群的选择率、真阳性率、错误率或校准情况,指标之间也可能冲突;并非都要求“所有错误率一致”。这里研究的是资源份额,不要直接混用定义。
🔗 这一章连到哪里
| 去哪 | 为什么 |
|---|---|
| 20-公平分配的算法.md | 本章只给判据没给算法。下一章把「EF1 总是存在」变成三个能手算的算法,并给出 EF1 + PO 同时达成的结论 |
| 18-住房市场与TTC.md | 区分带初始所有权的一人一件交换,与本章无初始所有权的一人多件分配;不能不改假设就套用 TTC 的结论 |
| 21-有钱与随机分配.md | 本章说 EF 常常不存在 —— 但允许转账之后它会以另一种形式回来 |
| 模型上线之后 19 · 合规、审计与模型卡 | 确认你说的「公平」是哪一种:那边是分类器对人群的错误率差异,这边是分配份额。写合规文档时混用会出事 |
✅ 检查点
- 为什么这一章要从序数偏好切换到基数估值?
- USW 最大化为什么在本章假设下可以逐件决定?使用跨人的报分有什么风险?
- $L_A=(50,55,100)$ 和 $L_{A'}=(50,100,100)$,谁 leximin 支配谁?ESW 能看出差别吗?
- 用第三节那张表,验证 $A=(\{g_1,g_5\},\{g_3\},\{g_2,g_4\})$ 对 2 号是不是 EF。
- 为什么 $\alpha$-EF 这种乘性放松救不了 EF?障碍到底是什么?
- EF ⟹ PROP 的证明用了哪一步不等式?
- 「一件不给」的分配为什么可能是 PROP1 的?这说明放松版判据该怎么用?
- $\mathrm{MMS}_i$ 和 $\frac{1}{n}v_i(M)$ 哪个大?为什么?
- $n=2$ 时 MMS 分配一定存在,靠的是什么机制?$n\ge3$ 呢?
- 在 EF1 算例中,为什么不能只检查 1 号和 2 号?
👀 答案
- 只给单件物品排序,不能算任意两堆的数值差距。任意子集有 $2^m$ 个;可加基数模型用每人的 $m$ 个数表示整堆价值。代价是排除了互补、替代等非可加关系,不是说序数分配方法失效。
- 每件物品独立地给对它出价最高的人即可(可加性下物品互不影响),例子表里最大 USW $=270$。错误在于加总把「一人损失 50」和「另一人获得 50」当成一回事。
- $A'$ leximin 支配 $A$:第 1 位都是 50,第 2 位 $100>55$。ESW 看不出差别,两者都是 50。
- 2 号:自己 $\{g_3\}=70$;1 号那堆 $10+50=60$;3 号那堆 $10+40=50$。$70\ge60$ 且 $70\ge50$ → 不嫉妒,对 2 号是 EF。
- 对每个固定的 $\alpha\in(0,1]$,选 $0<\epsilon<\alpha$,令两人估值都为 $(1,\alpha-\epsilon)$。各拿一件时小件不达标;全给一人时空手者不达标。因此固定比例不能保证所有实例有解。可换用 EF1,或研究转账、随机化等其他模型。
- 用 $v_i(A_j)\le v_i(A_i)$ 对所有 $j$ 求和:$v_i(M)=\sum_j v_i(A_j)\le n\,v_i(A_i)$。
- PROP1 只要求「再添一件就达标」:2 号拿 0,但 $v_2(\{g_1\})=100>160/2=80$。说明放松判据是下限不是目标,满足它完全可能糟糕透顶。
- $\mathrm{MMS}_i\le\frac{1}{n}v_i(M)$ —— 分成 $n$ 堆时最小那堆不可能超过平均值。所以 MMS 是「打了折的比例性」。
-
$n=2$ 时,1 号按自己的最优最小值分两堆,2 号先挑自己认为更值钱的一堆。1 号保住 MMS,2 号至少拿到自己总估值的一半,因此也保住 MMS。$n\ge3$ 时有无精确解要看实例,不能保证总存在;近似保证为一般情况提供下限。
-
EF1 要对所有人、所有其他堆都成立。原来的 $A'$ 漏掉了 3 号对 2 号的比较,去一件后仍是 $2>1$,因此失败。修正的分法见逐对检查表。
本节回顾
⚡ 走神救援
- 本章假设:平等权益、非负可加、不可分物品全部分完。
- EF 和 EF1 跟别人的堆比;PROP、PROP1 和 MMS 跟自己的门槛比。
- EF1 总有解,但不保证 PROP 或 MMS;公平标准不是一条阶梯。
- 精确 MMS 可能不存在;“计算难”也不等于“小实例算不了”。
- 回来时从逐对检查 EF1开始,或直接去下一章找算法。
下一节 👉 20-公平分配的算法.md