要得到某种公平保证,算法究竟维护了什么?
读后可检查:比较轮流选取、嫉妒图与最大 Nash 福利,按估值条件核对保证。
📑 本页目录(点开跳转)
20 · 公平分配的算法
⏱ 34 分钟 | 时间仅供参考,不限阅读时长;先看分配过程,证明按需展开
🎯 一句话
这一章比较三种分物品的方法:轮流挑、沿嫉妒图分配、最大化 Nash 福利。 它们保证什么、计算多难、允许什么估值,都不一样;不能只看名字里有没有“公平”。
先统一语境:有 $n$ 个人、$m$ 件不可分的好物品,没有额外容量约束。每件最终只归一个人;$A_i$ 是给 $i$ 的一堆,$v_i(A_j)$ 是 i 对 j 那堆的估值,不是 j 自己的满意度。
默认估值非负、可加,即一堆的价值等于其中单件价值之和。只有第二节会明确放宽到一般单调估值;这里不处理家务等负效用物品。
| 这章反复用的词 | 先记住什么 |
|---|---|
| EF1 | 对每个比较对象,从对方那堆去掉至多一件后,自己就不再嫉妒;不是实际把物品丢掉 |
| PO(帕累托最优) | 不存在“没有人变差、至少一人变好”的另一个分配;不等于人人一样满意 |
| MMS | 自己分成 n 堆、最后拿最差一堆时,能保证的最高价值;第四节要保住它的一半 |
第一次读,先跟着轮流拿的表格走一遍,再看选择表。要核对定义,回到上一章;证明不必一次读完。
🧩 一、Round-Robin:轮流拿最爱
先看最直观的轮流选物品。本节的 EF1 保证针对不可分物品、非负可加估值、固定轮流顺序;每个人按自己的估值挑剩下最喜欢的物品。
- 随便定一个人的顺序 $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,不超过自己的 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$ 当时就该挑那件)。
- 情况 1:$i$ 排在 $j$ 前面。 每一轮 i 都先挑,且件数不会更少。逐轮有 $v_i(g^i_t) \ge v_i(g^j_t)$,加起来得到 $v_i(A_i)\ge v_i(A_j)$。这是 i 对 j 不嫉妒,不是整个分配都满足 EF。
- 情况 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$ 件,件数差不超过 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 ⟺ 嫉妒图一条边都没有。
现在一件一件发。发给谁是安全的?
- 给一个被人眼红的人再加东西 → 新分配可能失去 EF1,不能直接沿用下面的保证
- 给一个没有入边的人(source,谁都不眼红他)加一件 → 别人本来就不眼红他,加了这一件之后去掉这一件就回到原状,EF1 一定保住 ✓
无环的有限图一定有 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 号仍想要 a,只是 a 换到了 2 号手里。 新箭头 3→2 确实出现了,但总边数从 3 降到 1。
一般情况也一样:对每个人,把“有多少堆比我自己的更好”数一遍。环外人的数量不变,目标身份可换;环内人换到更好的堆后,至少少嫉妒原先想要的那一堆。总边数严格下降,所以连续消环会终止。原算法的计数论证见 Lipton 等(2004),引理 2.2。
算法
- 所有人从空手开始
- 只要还有没发的物品:找嫉妒图的一个 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。∎
- 复杂度:在每次整堆估值查询按常数成本计的模型下,朴素嫉妒图实现为 $O(mn^3)$。若计算估值本身很贵,还要计入查询成本。
- ⭐ 适用面比 Round-Robin 宽:它不需要可加估值,只要单调($v(S\cup\{g\}) \ge v(S)$)就成立
- 额外配额不能直接套用:本算法不保证每人件数相同。若只允许给未满额的人发,可能找不到合适的 source;带配额的问题要另选或另证算法。
- 逐件发,不代表不可撤回:轮换会改变已经分配的物品归属。实际系统若不允许换回整堆,就不满足这套流程的前提。
为什么复杂度是多项式,而不是无限轮换?
发一件时,最多新增 $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,要按下面的规则处理:
- 找一组能同时得到正效用、且人数最多的人 S;有多个同样大的集合时,可固定选其中一个。
- 把物品分给这个固定集合 S 中的人,最大化他们的效用乘积;S 外的人先拿空集。
- 若所有人对所有物品都估值为 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$ 是剩余物品;每次移除人和物品后都重新计算平均份额。
- 记 $\beta_i = v_i(P)/|I|$($P$ 是剩余物品、$I$ 是剩余的人)
- 只要人和物品都还有,且存在 $v_i(g) \ge \beta_i/2$:把 g 单独给 i,把 i 和 g 一起从剩余集合移除,重算所有人的 $\beta$
- 剩下的人和物品跑普通 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 福利是两种截然不同的「总目标」。那边讲的正是「优化了一个加总指标却毁掉分布」这类事故 |
✅ 检查点
- 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?
👀 答案
- 只能推出 i 对 j 不嫉妒:逐轮比较后有 $v_i(A_i)\ge v_i(A_j)$。j 对 i 仍可能嫉妒,所以不是说整个分配完全 EF。
- j 的第一件没有更早的 i 的物品与它配对。去掉后,j 的第 t 件可与 i 的第 t−1 件比较。去掉第二件不能直接沿用这条证明;某个具体实例中其他删法也可能有效。
- 说明 Round-Robin 不保证 PO。1 号先挑(两件并列,取 $g_1$),2 号只剩 $g_2$,效用 $(1,0)$;换成 1 拿 $g_2$、2 拿 $g_1$ 就是 $(1,1)$ —— 1 号一点不亏、2 号白赚,原分配被帕累托支配。
- source 是没有入边的点:谁都不眼红他。给他加一件之后,别人对他的嫉妒「去掉这一件」就回到了原来的无嫉妒状态,EF1 天然保住。给被眼红的人加东西则会把已有的嫉妒继续放大,可能一件都减不回来。
- 会出现,例如正文中 3→1 变成 3→2。整堆换了主人,但环外人的嫉妒堆数不变,环上人的嫉妒堆数减少,因此总边数严格下降。
- 轮换前 $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 条。
- 宽在支持一般单调估值;限制是需要允许轮换旧物品,不自动保证均衡,也不直接适配额外配额。按常数成本估值查询计,朴素嫉妒图实现为 $O(mn^3)$。
- 无法全员得正效用时,全员乘积恒为 0。先固定一个人数最大的可同时得正效用集合 S,再在 S 上最大化乘积,才能区分零值情况下的解;不保证资源不足时人人有正效用。
- 挑的是“j 的损失 / i 的收益”最小的比值。再结合“去掉任何一件仍嫉妒”,才能推出 $av>b(u+a)$,从而使搬动后的乘积增加;只比较涨跌百分比不够。
- 提前退出者由大件门槛保证;留下者由 EF1 加上单件小于平均份额一半,求和后保证。两处都用“移除一个人和一件物品,不降低留下者 MMS”的引理连接回原实例。
本节回顾
先带走这四点
- Round-Robin 简单且件数均衡;非负可加估值下保 EF1,不保 PO。
- 嫉妒图支持单调估值,但允许换回整堆;轮换后下降的是总边数。
- 精确 MNW 在本章条件下保 EF1 与 PO;零效用和求解质量要单独处理。
- 一半 MMS 的算法先处理大件,再对剩余物品轮流拿,不需要先求精确 MMS。
下一节 👉 21-有钱与随机分配.md