🏠 总目录📚 本教程 20 · 公平分配的算法 ← →

要得到某种公平保证,算法究竟维护了什么?

读后可检查:比较轮流选取、嫉妒图与最大 Nash 福利,按估值条件核对保证。

📑 本页目录(点开跳转)

20 · 公平分配的算法

⏱ 34 分钟 | 时间仅供参考,不限阅读时长;先看分配过程,证明按需展开


🎯 一句话

这一章比较三种分物品的方法:轮流挑、沿嫉妒图分配、最大化 Nash 福利。 它们保证什么、计算多难、允许什么估值,都不一样;不能只看名字里有没有“公平”。

先统一语境:有 $n$ 个人、$m$ 件不可分的好物品,没有额外容量约束。每件最终只归一个人;$A_i$ 是给 $i$ 的一堆,$v_i(A_j)$ 是 i 对 j 那堆的估值,不是 j 自己的满意度。

默认估值非负、可加,即一堆的价值等于其中单件价值之和。只有第二节会明确放宽到一般单调估值;这里不处理家务等负效用物品。

这章反复用的词 先记住什么
EF1 对每个比较对象,从对方那堆去掉至多一件后,自己就不再嫉妒;不是实际把物品丢掉
PO(帕累托最优) 不存在“没有人变差、至少一人变好”的另一个分配;不等于人人一样满意
MMS 自己分成 n 堆、最后拿最差一堆时,能保证的最高价值;第四节要保住它的一半

第一次读,先跟着轮流拿的表格走一遍,再看选择表。要核对定义,回到上一章;证明不必一次读完。


🧩 一、Round-Robin:轮流拿最爱

先看最直观的轮流选物品。本节的 EF1 保证针对不可分物品、非负可加估值、固定轮流顺序;每个人按自己的估值挑剩下最喜欢的物品。

  1. 随便定一个人的顺序 $i_1, i_2, \dots, i_n$
  2. 按顺序轮流叫号,轮到谁,谁就从剩下的物品里挑自己估值最高的一件
  3. 一圈叫完从头再来,直到物品分完

完整走一遍(顺序 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,不超过自己的 45

看第二行:EF1 允许仍然嫉妒,只要求一件物品足以解释差距。

并列选择会改变分配,但本例的两种选择都满足 EF1。 第 2 轮,2 号对 g₃、g₄ 都估 5 分:

2 号这一轮选什么 1 号最后拿到 1 号自己的估值 2 号自己的估值 两人估值之和
g₄(上面的走法) g₁、g₂、g₃ 100 + 30 + 5 = 135 40 + 5 = 45 180
g₃(另一条分支) g₁、g₂、g₄ 100 + 30 + 10 = 140 40 + 5 = 45 185

看最后一列:算法保证一种公平性质,不代表输出唯一或福利相同。下一段查 EF1 的理由,后面再比较 PO 与福利。

这里的并列规则不影响 EF1 保证,但仍以本节的非负可加估值为前提;不能直接推广到任意互补物品、负效用或额外配额约束。

⭐ 为什么它一定 EF1(论证很短,值得看)

关键是挑选顺序:我挑的时候,你以后会挑的物品还没被拿走。 我已经挑了最喜欢的,所以按我的估值,这一件不会比你后来挑的差。

按两种先后顺序核对 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$ 当时就该挑那件)。

顺带的好处:每个人拿到 $\lfloor m/n\rfloor$ 或 $\lceil m/n\rceil$ 件,件数差不超过 1。如果 $m=nk$,就正好每人 k 件。这是一个能实现均衡的办法,不是唯一办法。

朴素实现每次扫描剩余物品,最多花 $O(m^2)$ 次单件估值比较。若预先给每个人排好偏好表并维护指针,排序需 $O(nm\log m)$,之后扫描总量为 $O(nm)$;不能漏掉排序成本。

但 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 号变好。 所以第一行虽满足 EF1,却不是 PO。


🧩 二、嫉妒图算法:给「没人眼红的人」发东西

Round-Robin 固定轮流顺序。嫉妒图算法改成看当前分配:给还没有被别人嫉妒的人加一件,必要时轮换已经分好的整堆。 因此它不是“物品一发出去就绝不能收回”的在线分配算法。

本节只需估值单调、空集价值为 0:多给一件好物品不会降低估值;不要求一堆的价值等于单件价值之和。

嫉妒图 $G_A$:点是人,从 $i$ 画一条边到 $j$ 当且仅当 $v_i(A_i) < v_i(A_j)$($i$ 眼红 $j$)。 分配是 EF ⟺ 嫉妒图一条边都没有。

现在一件一件发。发给谁是安全的?

无环的有限图一定有 source;有环时,source 可能不存在。 但“有环”不等于“一定没有 source”,它可能还有独立的无入边节点。

两人互相嫉妒时就没有 source:取第一节的 $A_1=\{g_5\}$、$A_2=\{g_4\}$。1 号觉得自己 5、对方 10;2 号觉得自己 5、对方 40,所以两人都想换。

⭐ 破环的办法:沿着环轮换整堆物品。 环上每个人拿走他所眼红的那个人的整堆。

为什么轮换安全:整堆的集合没变,环上每个人的自有价值严格增加,其他人的自有价值不变。因此原来“去掉一件就不嫉妒”的比较仍能保住,EF1 不会丢。

真正下降的是嫉妒边总数,不是每条箭头都只能消失。 同一堆换了主人,环外人的箭头可能改指另一个人。

看一个“出现新箭头,但总数减少”的三人例子

每人起初拿一件:1 拿 a、2 拿 b、3 拿 c。估值如下。

谁估值 a b c
1 1 3 0
2 3 1 0
3 2 0 1
状态 整堆归谁 嫉妒关系 边数
轮换前 1 拿 a;2 拿 b;3 拿 c 1→2、2→1、3→1 3
1、2 交换后 1 拿 b;2 拿 a;3 拿 c 3→2 1
沿环交换后,新箭头出现,但总边数下降 交换前:3 条边 交换后:1 条边 1、2 互相嫉妒,形成环 1 拿 b,2 拿 a,3 仍拿 c 人 1拿 a人 2拿 b人 3拿 c人 1拿 b人 2拿 a人 3拿 c 3 想要 a:箭头指向 1 3 仍想要 a:改指向 2
看 3 号:它仍想要 a,箭头因 a 换了主人而改向;总边数从 3 降到 1。

3 号仍想要 a,只是 a 换到了 2 号手里。 新箭头 3→2 确实出现了,但总边数从 3 降到 1。

一般情况也一样:对每个人,把“有多少堆比我自己的更好”数一遍。环外人的数量不变,目标身份可换;环内人换到更好的堆后,至少少嫉妒原先想要的那一堆。总边数严格下降,所以连续消环会终止。原算法的计数论证见 Lipton 等(2004),引理 2.2。

算法

  1. 所有人从空手开始
  2. 只要还有没发的物品:找嫉妒图的一个 source,把任意一件物品发给他
  3. 发完检查是否成环,成环就沿环轮换整堆,重复到无环
  4. 回到第 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,两条边同时消失。这是本例的结果;一般轮换只保证总边数下降,不保证每个箭头的身份不变。

性质

为什么复杂度是多项式,而不是无限轮换?

发一件时,最多新增 $n-1$ 条指向收货人的边;收货人自己的出边不会因多拿好物品而增加。每次沿长度至少为 2 的环轮换,总边数至少减少 2。

从空图开始,m 次发物品带来的边数净增长预算不超过 $m(n-1)$,所以消环次数不超过 $m(n-1)/2$。用邻接矩阵更新图、DFS 找环,每次按 $O(n^2)$ 计,得到 $O(mn^3)$。

这里追踪的是总数的增减,不是声称每个身份固定的箭头最多出现一次。


🧩 三、最大 Nash 福利:一个目标函数换来两个性质

在非负可加估值、无额外配额的不可分好物品模型里,精确 MNW 能同时保证 EF1 和 PO。 它是一个优化目标及选解规则,不是像轮流拿那样已给出快速求解过程。

如果能让每个人同时得到正效用,就在所有完整分配中最大化效用乘积。Nash 福利有时写成几何平均;人数固定时,最大化它与最大化乘积选出的解相同。

如果无论怎么分,总有人效用为 0,不能直接比较全员乘积。 所有乘积都会是 0,要按下面的规则处理:

  1. 找一组能同时得到正效用、且人数最多的人 S;有多个同样大的集合时,可固定选其中一个。
  2. 把物品分给这个固定集合 S 中的人,最大化他们的效用乘积;S 外的人先拿空集。
  3. 若所有人对所有物品都估值为 0,任意完整分配即可。

这不是拿“不同人数的乘积”直接比大小,也不是保证资源不够时人人都能得到正效用。以下例子属于全员可得正效用的情况。

手算($n=2$,$m=4$):

$o_1$ $o_2$ $o_3$ $o_4$
1 6 2 3 1
2 4 1 2 3

两人四件物品一共只有 $2^4=16$ 种完整分配。逐一核对后,最大乘积为 40;下面列出其中 5 种,方便手算比较。

$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 对照: 让 1 号拿前三件、2 号拿 $o_4$,效用为 11 和 3,总和是 14;MNW 解是 8 和 5,总和只有 13。

本例中,较高总和对应了较大的数值差距。但不能推广成“求和必然拉大差距,乘积必然让人人一样”。不同人的估值标尺也不一定可直接比较;全员正效用时,MNW 关心的是效用变化的相对比例。

定理的前提和零值规则见 Caragiannis 等的原始论文,定义 3.1 与定理 3.2。“任何 MNW 解”指精确全局最优解,并非任意求解器返回的候选或近似解。

为什么它是 PO? 全员正效用时,不伤害任何人的严格改进会使乘积增加,与最优矛盾。零值情况下,改进要么增加能得到正效用的人数,要么增加固定集合 S 的乘积,也分别违反前两步的最优性。

EF1 的直觉: 如果某人嫉妒得太厉害,连去掉对方任何一件都无法消除嫉妒,就能找到一次搬物品的机会,让乘积更大。因此这种分配不可能已经达到 MNW。

那件物品怎么挑?把乘积比较的缺失步骤补全

先考虑两人都得到正效用。假设 i 对 j 不满足 EF1,从 j 的物品中,选“j 的损失 / i 的收益”最小的一件:

$$g^{*} = \arg\min_{g\in A_j,\ v_i(g)>0} \frac{v_j(g)}{v_i(g)}$$

注意比较的是比值,不是要求这件物品同时是 j 最不喜欢、i 最喜欢的那件。

为看清乘积,记 $u=v_i(A_i)$、$v=v_j(A_j)$,搬走这件带来的收益是 $a=v_i(g^*)>0$,损失是 $b=v_j(g^*)\ge0$。

状态 i 的效用 j 的效用 两人的乘积
搬之前 u v uv
从 j 搬给 i 之后 u+a v−b (u+a)(v−b)

展开乘积可知,要让新乘积更大,需要:

$$av>b(u+a)$$

只说“涨的百分比大于跌的百分比”不够。 例如一人涨 20%、另一人跌 19%,乘积变成原来的 $1.2\times0.81=0.972$,反而下降。

再记 $T=v_i(A_j)$,即 i 对 j 整堆的估值。选最小比值保证第一条;“去掉任何一件仍嫉妒”保证第二条:

$$\frac{b}{a}\le\frac{v}{T},\qquad T>u+a$$

第一条可看作加权平均:物品比值中的最小值,不大于整堆的“j 估值 / i 估值”;对 i 估值为 0 的物品只会增大右侧分子,不影响这个方向。

因此 $b/a\le v/T<v/(u+a)$,恰好推出上面的 $av>b(u+a)$。其他人的效用不变,总乘积增大,与 MNW 矛盾。

如果有人效用为 0 呢? S 内的人按上面的证明互相满足 EF1。S 外的人拿空集,别人不会嫉妒他;若他对 S 内某人不满足 EF1,就能在保留对方一件正价值物品的同时,拿走另一件让自己也变成正效用。

这样正效用人数增加,违反 S 已经人数最多的前提。因此零值情况也不会漏掉 EF1。

计算代价:精确求 MNW 是 NP 难的。 小规模可以用枚举或适当的优化求解器,但应区分“找到一个解”和“已证明全局最优”;只找到近似候选时,要另查公平保证。

Nash 社会福利的几何平均目标已有多项式时间常数近似算法,不能把 NP 难写成“常数近似也做不了”。见 Cole 与 Gkatzelis 的原始工作。

Spliddit 是原 MNW 论文中的应用背景之一。但房租含金钱、家务可能是负效用,不能据此把本节好物品定理直接套到它们;相关模型去看下一章。


🧩 四、顺手把 MMS 也解决一半

非负可加估值下,可以用“先处理大件,再轮流拿”保证每个人至少得到原实例 MMS 的一半。 这里给的是容易理解的保证,不声称是一切算法的最佳近似比,也不要求先求出难算的精确 MMS。

先约定 $I$ 是剩余的人,$P$ 是剩余物品;每次移除人和物品后都重新计算平均份额。

  1. 记 $\beta_i = v_i(P)/|I|$($P$ 是剩余物品、$I$ 是剩余的人)
  2. 只要人和物品都还有,且存在 $v_i(g) \ge \beta_i/2$:把 g 单独给 i,把 i 和 g 一起从剩余集合移除,重算所有人的 $\beta$
  3. 剩下的人和物品跑普通 Round-Robin

若人先分完,剩余非负物品任意补给已有的人;若物品先分完,剩余人拿空集。不要在没有剩余人时继续除以 $|I|$。

看一个过程例子: 三人对七件物品的估值都为 12、2、2、2、2、2、2。

进到哪一步 平均份额 β 本轮判断 得到什么
3 人、总值 24 8 大件 12 ≥ 8/2 给一人 12,移除这人和这件
剩 2 人、总值 12 6 每件 2 < 6/2 轮流拿,另外两人各得 3 件、总值 6

原实例每人的 MMS 是 6:可以切成 12、6、6,且两个不含大件的堆中至少一个不超过 6。最终是 12、6、6,每人都超过所需下限 3。

证明只分两类人: 提前退出的人靠一件大物品达标;留到最后的人靠 EF1 加上“没有大件”的条件达标。下面补上两处关键不等式。

为什么拿走一个人和一件物品后,MMS 下限还有效?

不是“人数少了、物品变多了”——这里人和物品都少了。真正用到的是:移除一位其他人和任意一件物品,不会降低留下者的 MMS。

对留下的 i,设他原来把当前物品切成 r 堆,每堆至少为当前 MMS。去掉含 g 的那一堆,把其中除 g 外的物品补进其余 r−1 堆。好物品的单调性保证这些堆不变差。

于是,当 r≥2 时,剩余 r−1 人、剩余物品仍能形成不低于原门槛的分堆。反复使用这个论证,再用“最小堆不超过平均堆”,得到:

$$\begin{gathered}\frac{v_i(P)}{|I|}\ge\mathrm{MMS}_i(|I|,P)\\\mathrm{MMS}_i(|I|,P)\ge\mathrm{MMS}_i(n,M)\end{gathered}$$

这里平均份额是剩余实例 MMS 的上界;整个不等式链又保证它不低于原实例 MMS。不是把平均份额叫成 MMS 的下界。

因此提前退出的人,拿到的一件至少值 $\beta_i/2$,也就至少达到原实例 MMS 的一半。

留下的人为什么也能拿到一半?

设最后剩 r 个人。对其中的 i,剩余总价值为 $T=v_i(P)$,平均份额为 $\beta_i=T/r$。每一件在 i 眼中都小于 $\beta_i/2$。

设轮流拿后 i 自己的价值为 u。EF1 告诉我们:任何别人的堆,在去掉一件小物品后都不超过 u。因此对每个别人 j:

$$v_i(A_j)\le u+\frac{\beta_i}{2}$$

把所有 r 堆按 i 的估值相加(若只有 i 一人,直接拿到全部即可):

$$T\le ru+(r-1)\frac{\beta_i}{2}$$

又因为 $T=r\beta_i$,整理得到 $u\ge\frac{r+1}{2r}\beta_i\ge\beta_i/2$。结合前一个折叠里的 MMS 不等式链,就达到原实例 MMS 的一半。

所以理由不是“EF1 自动保一半”,而是 EF1 与每件物品都足够小一起起作用。

如果此时物品已经为空,留下者的剩余 MMS 为 0;上述移除引理也说明其原 MMS 为 0,所以拿空集不会违反一半保证。


🧩 五、三个算法怎么选

Round-Robin 嫉妒图 MNW
保证 EF1、PROP1;件数差不超过 1 一般单调估值下保 EF1;不自动保均衡 在本章条件下,精确解保 EF1 + PO
计算成本 朴素扫描 $O(m^2)$;预排序另计 $O(mn^3)$,按常数成本估值查询计 精确优化 NP 难
估值要求 非负可加 单调,空集价值为 0 非负可加
适用场景 想先得到简单、件数均衡的 EF1 分配 估值可能不可加,且允许轮换已经分好的整堆 想同时保 EF1 与 PO,且愿意核对求解质量

别把条件混在一起:EF1 推出 PROP1 需要本章的非负可加条件。 嫉妒图支持一般单调估值,不代表这个更宽的范围也自动保证 PROP1。

不可加估值下,EF1 为什么不一定推出 PROP1?

两人对三件物品有相同估值:空集和任一单件值 0,任意两件合起来值 1,三件合起来值 100。这是单调估值,但不可加。

分成一件和两件:拿一件者值 0;从对方两件中去掉一件,对方也值 0,所以满足 EF1。可是给他补一件后只值 1,远低于总价值一半 50,不满足 PROP1。

先问自己要保什么,再选算法。 简单均衡选 Round-Robin;一般单调估值且可重新分配,考虑嫉妒图;需要 EF1 与 PO,可研究精确 MNW。它们不是全部可能的算法,带配额、负效用或不可撤回的任务都要重新核对模型。


🔗 这一章连到哪里

去哪 为什么
19-怎么算公平.md EF1 / PROP1 / MMS 的定义和「为什么必须放松」都在那儿。本章只负责把它们算出来
21-有钱与随机分配.md 嫉妒图在下一章会长出边权:权重变成「嫉妒了多少」,于是能算出「补多少钱才不嫉妒」
模型上线之后 15 · 长期效应与代理指标 USW 和 Nash 福利是两种截然不同的「总目标」。那边讲的正是「优化了一个加总指标却毁掉分布」这类事故

✅ 检查点

  1. Round-Robin 里,「$i$ 排在 $j$ 前面」这种情况得到的结论比 EF1 更强,强在哪?
  2. 情况 2 的证明为什么要专门划掉 $j$ 第一轮挑的那件?划第二轮的行不行?
  3. $v_1=(1,1)$、$v_2=(1,0)$ 这个反例说明了 Round-Robin 的什么缺陷?帕累托改进具体是怎么换的?
  4. 嫉妒图里为什么给 source 发东西是安全的,给被眼红的人发就不安全?
  5. 沿环轮换整堆之后,会不会出现指向新人的嫉妒边?真正严格下降的是什么?
  6. 手算例子第 3 步轮换后两个人的值分别变成了多少?边数怎么变的?
  7. 嫉妒图算法比 Round-Robin 宽在哪、窄在哪?
  8. MNW 的定义为什么要先最大化「拿到正效用的人数」?
  9. MNW ⟹ EF1 的论证里,那个被挪走的 $g^*$ 是按什么标准挑的?为什么是这个标准?
  10. 贪心 Round-Robin 里第 2 步出局的人和第 3 步留下的人,分别靠什么论证拿到 $\frac12$-MMS?
👀 答案
  1. 只能推出 i 对 j 不嫉妒:逐轮比较后有 $v_i(A_i)\ge v_i(A_j)$。j 对 i 仍可能嫉妒,所以不是说整个分配完全 EF。
  2. j 的第一件没有更早的 i 的物品与它配对。去掉后,j 的第 t 件可与 i 的第 t−1 件比较。去掉第二件不能直接沿用这条证明;某个具体实例中其他删法也可能有效。
  3. 说明 Round-Robin 不保证 PO。1 号先挑(两件并列,取 $g_1$),2 号只剩 $g_2$,效用 $(1,0)$;换成 1 拿 $g_2$、2 拿 $g_1$ 就是 $(1,1)$ —— 1 号一点不亏、2 号白赚,原分配被帕累托支配。
  4. source 是没有入边的点:谁都不眼红他。给他加一件之后,别人对他的嫉妒「去掉这一件」就回到了原来的无嫉妒状态,EF1 天然保住。给被眼红的人加东西则会把已有的嫉妒继续放大,可能一件都减不回来。
  5. 会出现,例如正文中 3→1 变成 3→2。整堆换了主人,但环外人的嫉妒堆数不变,环上人的嫉妒堆数减少,因此总边数严格下降。
  6. 轮换前 $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 条。
  7. 宽在支持一般单调估值;限制是需要允许轮换旧物品,不自动保证均衡,也不直接适配额外配额。按常数成本估值查询计,朴素嫉妒图实现为 $O(mn^3)$。
  8. 无法全员得正效用时,全员乘积恒为 0。先固定一个人数最大的可同时得正效用集合 S,再在 S 上最大化乘积,才能区分零值情况下的解;不保证资源不足时人人有正效用。
  9. 挑的是“j 的损失 / i 的收益”最小的比值。再结合“去掉任何一件仍嫉妒”,才能推出 $av>b(u+a)$,从而使搬动后的乘积增加;只比较涨跌百分比不够。
  10. 提前退出者由大件门槛保证;留下者由 EF1 加上单件小于平均份额一半,求和后保证。两处都用“移除一个人和一件物品,不降低留下者 MMS”的引理连接回原实例。

本节回顾

先带走这四点

下一节 👉 21-有钱与随机分配.md

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