加入金钱或随机机会后,公平应怎样比较?
读后可检查:分别检查补偿可行性、排序下的随机支配与可分物品的设定。
📑 本页目录(点开跳转)
21 · 有钱与随机分配
⏱ 42 分钟 | 时间仅供参考,可分三次读:转账、抽签、可分物品
🎯 一句话
不能把东西切开,不代表只能接受眼前的分法:可以研究转账补偿,也可以比较抽签机会;如果东西本来就能切,则又是另一套问题。
三条路线的条件不同,按需要选一条,不必一次读完:
- 能收钱或发补贴,物品价值可用钱衡量:从最小转账例子看固定分堆能否补平。
- 不能用钱,只问排序,每人一件:到随机分配比较 RSD、PS 的抽签机会。
- 两人分可切割的物品,价值随份额线性增加:到调整赢家法看怎样平衡双方报分。
🧩 一、把钱加进来
上一章的不可分物品不保证存在 EF 分配。现在允许附带转账,但先要讲清:我们使用准线性效用,且暂不施加个人付款上限或补贴预算限制。
带钱的结果是一对 $(X, p)$:$X$ 是分配,$p_i$ 是付给 $i$ 的钱(可为负,即 $i$ 掏钱)。
准线性效用:$u_i(X_j,p_j)=v_i(X_j)+p_j$。人在评价别人的整份结果时,也要把对方的钱一起算进去。
结果 $(X,p)$ 无嫉妒:对所有 $i,j$,$v_i(X_i)+p_i \ \ge\ v_i(X_j)+p_j$。
这里的 $v_i$ 必须是与支付同单位的货币估值,不能把上一章任意打的 100 分直接当成 100 元。准线性假设表示:在考虑的范围内,钱线性进入效用,物品估值不随剩余财富改变。
这不证明不同人的幸福感可以直接比较,也不自动排除预算约束。房租分摊等场景仍可能存在“理论上应付款,但这个人付不起”的问题;此处只是先研究没有这些额外限制的模型。
⭐ 关键的新概念 —— 注意它是分配的性质,不是结果的性质,问的是「这个分法有没有救」而不是「这一组钱够不够」:
分配 $X$ 是可无嫉妒化的(envy-freeable):存在一组支付 $p$ 使 $(X,p)$ 无嫉妒。
手算两个最小例子:一件物品 $g_1$,$v_1(g_1)=10$,$v_2(g_1)=5$。
- 分法 A(给 2 号):1 号要求 $p_1-p_2\ge10$;2 号要求 $p_1-p_2\le5$。同一笔支付差不能同时满足两条,所以无论收钱还是发钱,都无法让这个固定分法无嫉妒。
- 分法 B(给 1 号):取 $p_1=0,p_2=5$。2 号看自己是 5,看 1 号也是 $5+0=5$;1 号看自己是 10,看 2 号是 5。两人都不嫉妒。
这一件物品的例子里,给货币估值较高的人才能补平。推广到多件物品后,准确条件是现有几堆之间重新换主人,能否提高总估值,而不是笼统地说“分配不浪费”或“已经 PO”。
🧩 二、带权嫉妒图与三条等价条件
上一章的嫉妒图只记「有没有嫉妒」,现在给边加上权重 = 嫉妒了多少:
带权嫉妒图:完全有向图,点集是 $N$,边权 $$w(i,j) = v_i(X_j) - v_i(X_i)$$ (正数表示 $i$ 真的眼红 $j$,负数表示 $i$ 觉得自己那堆更好。)路径/环的权重就是边权之和。
还需要一个概念:
重分配稳定(reassignment-stable):把现有的这几堆东西整体换个人来分,总福利不会更高: 对每一个重新安排各堆归属的排列 $\pi$,都有:
$$\sum_i v_i(X_i)\ge\sum_i v_i(X_{\pi(i)})$$
—— 堆已经分好了,问的只是「谁拿哪一堆」有没有分错。
不允许在这个检验里拆散旧堆、重新装堆。 因此“重分配稳定”不等于在所有分法中 USW 最大,也不等于 PO。
例如两件物品的估值为:1 号 $(3,0)$,2 号 $(0,1)$。全给 1 号时,整堆值 3,比整堆给 2 号的 1 高,满足重分配稳定;但把第二件单独给 2 号,可以让 1 号不变、2 号变好,所以原分配不是 PO。
定理(可无嫉妒化的刻画):在本章没有额外支付限制的准线性模型下,下面三条等价: 1. $X$ 是可无嫉妒化的 2. $X$ 是重分配稳定的 3. $X$ 的带权嫉妒图里没有正权环
先记用途:无正权环,就能构造补贴;有正权环,固定分法就补不平。 这个固定分堆的刻画本身不要求估值可加;后面的逐轮分物品算法才使用非负可加假设。定理与构造出处
可选推导:为什么这三个条件等价
① 有无嫉妒支付,就重分配稳定。 无嫉妒给出 $w(i,j)\le p_i-p_j$。对一个排列 $\pi$ 逐人求和:
$$\sum_i w(i,\pi(i))\le \sum_i(p_i-p_{\pi(i)})$$
$$\sum_i(p_i-p_{\pi(i)})=0$$ 最后等于 0 是因为每个 $p$ 都被加一次减一次,整体抵消。∎
② 重分配稳定,就没有正权环。 否则让环上的每个人接收下一个人的整堆、环外不动,总估值的增量恰好是正的环权重,与稳定矛盾。注意:总分变高不表示每个人都变好。
③ 没有正权环,就能构造无嫉妒补贴。 令 $\ell(i)$ 为从 $i$ 出发、可停在任意顶点的最大游走权重,允许什么都不走,权重为 0。
无正权环时,绕环不会提高权重,删去重复的环可得到同样好或更好的简单路径,因此最大值有限,而且 $\ell(i)\ge0$。
取 $p_i=\ell(i)$。先走边 $(i,j)$ 再接上 $j$ 的最优游走,是一个可选走法,所以:
$$\ell(i)\ge w(i,j)+\ell(j)$$
这就是 $p_i-p_j\ge w(i,j)$,移项便是无嫉妒条件。
怎么真的算出来
- 查正权环 / 求支付:先取反边权,再加一个终点 $s$,每个人都可以经权重 0 的边到 $s$。求各点到 $s$ 的最短距离 $d(i,s)$,然后取 $p_i=-d(i,s)$。若使用单源 Bellman–Ford,则反转这些边,从 $s$ 出发;它也能检测负环。
- 查重分配稳定:建一个完全二部图,一边是人、一边是现有的那几堆,边权 $w(i,X_j)=v_i(X_j)$。$X$ 重分配稳定 ⟺ 最大权匹配的权重不超过当前的 USW。
⭐ 两个白送的构造:USW 最大的分配一定可无嫉妒化(任何重指派都不可能更好);把所有物品打成一捆给最看重它的那个人也一定可以。
完整手算
三人三物,每人各拿一件:$X_1=\{g_1\}$、$X_2=\{g_2\}$、$X_3=\{g_3\}$。
| $g_1$ | $g_2$ | $g_3$ | |
|---|---|---|---|
| 1 | 7 | 2 | 1 |
| 2 | 6 | 3 | 1 |
| 3 | 5 | 3 | 2 |
第一步,算六条边权 $w(i,j)=v_i(X_j)-v_i(X_i)$:
| $w(\cdot,1)$ | $w(\cdot,2)$ | $w(\cdot,3)$ | |
|---|---|---|---|
| 1(自己 7) | — | $2-7=-5$ | $1-7=-6$ |
| 2(自己 3) | $6-3=+3$ | — | $1-3=-2$ |
| 3(自己 2) | $5-2=+3$ | $3-2=+1$ | — |
(读法:2 号和 3 号都眼红 1 号,3 号还眼红 2 号;1 号谁都不眼红。)
第二步,查正权环。 三个两人环、两个方向的三人环都不为正:
| 环 | 加起来是多少 |
|---|---|
| $1\to2\to1$ | $-5+3=-2$ |
| $1\to3\to1$ | $-6+3=-3$ |
| $2\to3\to2$ | $-2+1=-1$ |
| $1\to2\to3\to1$ | $-5-2+3=-4$ |
| $1\to3\to2\to1$ | $-6+1+3=-2$ |
本例所有简单环都检查完了,所以可无嫉妒化。一般人数多时不枚举全部环,而用上面的图算法。
第三步,比较可走的路径。 无正权环意味着绕圈不会更好;三个人最多需要检查两条边的简单路径,并保留权重为 0 的空路径。
| 从谁出发 | 空路径 | 直接到另两人 | 经一人再到另一人 | 最大值 |
|---|---|---|---|---|
| 1 | 0 | $-5,-6$ | $-7,-5$ | 0 |
| 2 | 0 | $3,-2$ | $-3,1$ | 3 |
| 3 | 0 | $3,1$ | $-2,4$ | 4 |
3 号直接去 1 号是 3;经 2 号再去 1 号是 $1+3=4$,所以需要补 4。不能只凭“起点出边都是负数”就断言最长路径是 0,后续边可能把总和补成正数;本例是检查所有候选后才得到这个结果。
支付:$p_1 = 0,\ p_2 = 3,\ p_3 = 4$。
第四步,连物品带钱一起比。 每行仍固定一个人的估值,不能拿三人的自评分数直接相互比较。
| 谁在看 | 自己的整份 | 看 1 号 | 看 2 号 | 看 3 号 |
|---|---|---|---|---|
| 1 | $7+0=7$ | 自己 | $2+3=5$ | $1+4=5$ |
| 2 | $3+3=6$ | $6+0=6$ | 自己 | $1+4=5$ |
| 3 | $2+4=6$ | $5+0=5$ | $3+3=6$ | 自己 |
每人的自己一栏都不低于另外两栏,六个比较全部通过。
“最小支付”要先说能不能收费
若要求 $p_i\ge0$,即只能发补贴、不能向任何人收费,最长路径给出的 $(0,3,4)$ 是逐人最小补贴,总支出为 7。
原因是:沿任意路径把 $p_i-p_j\ge w(i,j)$ 相加,得到起点补贴至少为“路径权重 + 终点补贴”。终点补贴非负,因此起点必须覆盖所有路径权重;取最大值恰好达到下界。
若允许收费,给所有人的支付同时减去同一个数,不会改变任何两人的支付差。本例每人减 $7/3$,得到:
$$p'=\left(-\frac73,\frac23,\frac53\right)$$
仍然无嫉妒,并且总支付为 0。此时不能不加约束地宣称原来那组是“最小支付”;若给所有人继续减同一个数,总支付还能继续下降。现实中的支付能力或预算限制需要另行检查。
想同时要 EF1 和可无嫉妒化?
可以,但不是“每轮每人一件”就够。 Brustle 等(2019)的算法在非负可加估值下,每轮求“人 × 剩余物品”的最大总权匹配,把匹配到的物品发出,再进入下一轮。原论文第 3 节
- 每轮每人最多拿一件;最后物品不足时,可以添对所有人都值 0 的虚拟物品。
- 每轮都选最大总权匹配,不是随便找一个匹配,也不是每个人同时选自己最喜欢的物品。
- 各轮发完后,删去虚拟物品,实际物品分配同时满足 EF1 和可无嫉妒化。
可选:两项保证分别依赖什么
可无嫉妒化:固定任意一个人的环。单轮若沿环换物品能增加总估值,就与该轮最大权匹配矛盾。每一轮对这个环的权重都不大于 0;可加性保证总分配中的环权重是各轮之和,因此仍不大于 0。
EF1:第 $t$ 轮给 $i$ 的物品,在 $i$ 看来,至少不比任何留到下一轮的物品差。否则只把 $i$ 的匹配边换到那件尚未发出的物品,就能提高本轮总权重。
所以可以把 $i$ 第 $t$ 轮所得,与 $j$ 第 $t+1$ 轮所得逐一比较。把这些不等式相加,就能覆盖 $j$ 除第一轮物品外的全部价值。这才是 EF1 的原因;只控制每轮件数,不能推出该结论。
固定分堆无正权环,就能在本章支付假设下补平。
🧩 三、不用钱,只报排序:比较抽签机会
换个场景:分宿舍、分实习岗位、分课程名额。不能收钱(政策不允许),而且只问得出排序问不出估值 —— 你可以让学生把宿舍排个序,但「A 宿舍值 80 分」这种话没人报得准,报了也没法核实。
这里另换模型:$n$ 个人、$n$ 件物品、每人恰好一件,所有物品都可接受,偏好是严格排序,没有初始所有权、优先权或其他资格限制。
确定性分配不是一定不公平:如果每人的第一志愿各不相同,都分到第一志愿就没有嫉妒。但多人争同一物品时,抽签能让我们讨论“事前机会是否公平”,而不只是看抽完后的输赢。
随机分配 $p$ 是一个矩阵,$p_i(o)$ 表示 $i$ 拿到 $o$ 的概率。每行和为 1(每人恰好一件),每列和为 1(每件恰好给一人)。
还要求每格非负,这叫双随机矩阵。它记录边际概率;具体实施时要联合抽一个完整匹配,不能让每个人独立抽,导致同一件物品重复中奖。这样的矩阵可分解为完整匹配的概率混合(Birkhoff–von Neumann 分解)。
本节从头到尾用同一个实例(3 人 3 物):
| 人 | 第一志愿 | 第二志愿 | 第三志愿 |
|---|---|---|---|
| 1 | $o_1$ | $o_2$ | $o_3$ |
| 2 | $o_2$ | $o_1$ | $o_3$ |
| 3 | $o_2$ | $o_3$ | $o_1$ |
算法一:RSD(随机序列独裁)
等概率抽一个人的顺序,按顺序让每人从剩下的物品中选最喜欢的。 三个人共有六个顺序,每个出现概率都是 $1/6$。
| 抽到的顺序 | 按人 1、2、3 记录最终所得 | 出现次数 |
|---|---|---|
| 123、213、231 | $(o_1,o_2,o_3)$ | 3 |
| 132、312 | $(o_1,o_3,o_2)$ | 2 |
| 321 | $(o_3,o_1,o_2)$ | 1 |
把每个人拿到各物品的次数除以 6,就是概率矩阵。下面用原生表格标清行列:
| RSD | $o_1$ | $o_2$ | $o_3$ |
|---|---|---|---|
| 1 号 | $5/6$ | 0 | $1/6$ |
| 2 号 | $1/6$ | $1/2$ | $1/3$ |
| 3 号 | 0 | $1/2$ | $1/2$ |
(行是人 1/2/3,列是 $o_1/o_2/o_3$。⭐ 自查:每行每列都加到 1。)
RSD 可以方便地抽一次结果,而且策略防伪:顺序与报出的偏好无关,轮到自己时,诚实排序会选中剩余物品里真正最喜欢的那件。
但精确算出全部概率是另一项任务。一般情形下它涉及困难的计数问题(#P-complete),不能因为抽一次很容易,就认为整张精确概率表也容易计算。大实例可以重复抽样估计概率,但要报告估计误差,不能冒充精确值。计算复杂度原论文
算法二:PS(概率序列 / 「吃」算法)
⭐ 把每件物品想成一块重量为 1 的蛋糕:
- 所有人同时、以相同速度开吃自己当前最想要且还没吃完的那件
- 一件被吃光了,正在吃它的人立刻转向自己列表里下一件还没吃完的
- 全部吃光时停。每个人吃掉的份额就是他的概率
完整走一遍(还是上面那个实例):
第一步:从 0 到 1/2
1 号独自吃 $o_1$;2、3 号同时吃 $o_2$。每个人每单位时间吃 1 份,$o_2$ 的消耗速度是 2,因此在 $t=1/2$ 时先吃完。
此时 1 号已得到 $o_1$ 的一半,2、3 号各得到 $o_2$ 的一半。
第二步:从 1/2 到 3/4
$o_2$ 没了。2 号转向 $o_1$,与 1 号分享剩余的一半;3 号转向 $o_3$。
剩余半份 $o_1$ 由两人一起吃,再过 $1/4$ 单位时间就吃完。1、2 号各再得到 $o_1$ 的 $1/4$,3 号得到 $o_3$ 的 $1/4$。
第三步:从 3/4 到 1
只剩 $o_3$ 的 $3/4$,三人一起吃,每人再得到 $1/4$。到 $t=1$ 全部吃完。
1 号一共得到 $o_1$ 的 $3/4$、$o_3$ 的 $1/4$。其他人同样按列累加,得到下表:
| PS | $o_1$ | $o_2$ | $o_3$ |
|---|---|---|---|
| 1 号 | $3/4$ | 0 | $1/4$ |
| 2 号 | $1/4$ | $1/2$ | $1/4$ |
| 3 号 | 0 | $1/2$ | $1/2$ |
“吃掉的份额”只是计算概率的办法。真实宿舍仍是一人一间,最终需要按这个概率矩阵联合抽出一个完整匹配。
⭐ 对比一下 RSD 和 PS:1 号在 RSD 下拿到 $o_1$ 的概率是 $5/6$,在 PS 下只有 $3/4$ —— 1 号更喜欢 RSD。而 2 号呢?两者拿到最爱 $o_2$ 的概率都是 $1/2$,但第二志愿 $o_1$:PS 给 $1/4$、RSD 只给 $1/6$ —— 2 号更喜欢 PS。
本例 1 号受益于 RSD,2 号受益于 PS,3 号的概率相同;不能说其中一张表让所有人都更好。下面用累计概率把这种比较说准确。
🧩 四、一阶随机支配(SD):概率表怎么比
只有排序、没有数字,怎么说「这张概率表比那张好」?
⭐ SD(stochastic dominance):$i$ 认为 $p$ 支配 $q$,记 $p(i) \succeq_i^{SD} q(i)$,当且仅当对每一件物品 $o$: $$\sum_{o' \succeq_i o} p_i(o')\ \ \ge \sum_{o' \succeq_i o} q_i(o')$$
直觉就一句话:从最爱往下累计概率,每一层 $p$ 都不比 $q$ 少。「拿到第 1 名的概率」不少、「拿到前 2 名的概率」不少、「拿到前 3 名的概率」不少……
⭐ 它为什么是对的标尺:$p \succeq^{SD}_i q$ 当且仅当 对每一个与 $i$ 的排序相容的效用函数,$p$ 的期望效用都不低于 $q$。也就是说 —— 不管这个人心里的真实数字是多少,只要排序是这个,他就一定不会更差。 这正是「问不出基数估值」时能给出的最强承诺。
手算比较(1 号,偏好 $o_1 \succ o_2 \succ o_3$):
| 累计到 | RSD | PS |
|---|---|---|
| $o_1$ | $5/6$ | $3/4$ |
| $o_1,o_2$ | $5/6$ | $3/4$ |
| $o_1,o_2,o_3$ | $1$ | $1$ |
每一层 RSD 都 $\ge$ PS ⟹ 1 号在 SD 意义下严格更喜欢 RSD ✓
2 号(偏好 $o_2 \succ o_1 \succ o_3$):PS 累计是 $1/2,\ 3/4,\ 1$;RSD 是 $1/2,\ 2/3,\ 1$。⟹ 2 号在 SD 意义下更喜欢 PS ✓
⚠️ SD 是偏序,有些结果不可比
设某人偏好 $o_1\succ o_2\succ o_3$,比较两行概率 $p=(1/2,0,1/2)$ 和 $q=(1/3,1/2,1/6)$:
| 累计范围 | $p$ | $q$ |
|---|---|---|
| 最爱的一件 | $1/2$ | $1/3$ |
| 最爱的两件 | $1/2$ | $5/6$ |
| 全部三件 | 1 | 1 |
第一层 $p$ 赢($1/2>1/3$),第二层 $q$ 赢($5/6>1/2$) —— 谁都不支配谁。它们在 SD 下不可比。
这不是理论洁癖:$p$ 是「要么最好要么最差」的赌博,$q$ 是「大概率拿到前二」的稳妥。哪个更好取决于这个人心里的真实数字,而序数偏好里根本没有这个信息。 SD 拒绝在这种时候下结论 —— 这是它的诚实,也是它的局限:基于 SD 的「最优」往往一大堆,选哪个还得另找理由。
三个 SD 版的性质
- SD-无嫉妒:按 $i$ 自己的排序,我这一行 SD 支配每个别人的行。要求的是“自己的行在每个累计门槛都不差”,不只是“别人没有严格支配我”;不可比也不能算通过。
- SD-有效:不存在另一张表让所有人 SD 上不差、至少一人严格更好
- SD-策略防伪:报真话得到的表,SD 支配任何谎报得到的表
| 机制 | 诚实报告 SD 支配所有谎报 | SD-有效 | SD-无嫉妒 |
|---|---|---|---|
| RSD | 保证 | 一般不保证 | 一般不保证 |
| PS | 不保证 | 保证 | 保证 |
这是对机制在所有合法输入上的保证的比较。“不保证”不等于每次输出都失败。RSD 每次实际抽出的匹配仍然是 PO,叫事后有效;但这不等于整个概率分配 SD-有效。Bogomolnaia 与 Moulin(2001)
特别地,标准三人三物、严格排序的 RSD 仍然 SD-有效。因此不能拿本章的三人算例,来证明 RSD 的一般性效率缺陷;它在这里展示的是人与人对两种机制的取舍不同。
这两个机制各缺一项性质,本身还不足以证明“任何机制都不能兼得”。该论文另有不可能性定理:在 $n\ge4$ 的标准严格排序随机分配模型中,SD-有效、SD-策略防伪和同偏好同待遇无法同时保证;SD-无嫉妒会要求同偏好同待遇,因此更强的三项要求也无法兼得。
PS 的谎报例子:不保证诚实最优
保留前面的实例。1 号真实排序是 $o_1\succ o_2\succ o_3$,却报成 $o_2\succ o_1\succ o_3$。重新运行 PS,他得到的行变为 $(1/2,1/3,1/6)$。
| 累计范围 | 诚实 | 谎报 |
|---|---|---|
| 最爱的一件 | $3/4$ | $1/2$ |
| 最爱的两件 | $3/4$ | $5/6$ |
| 全部 | 1 | 1 |
诚实时拿第一志愿的机会更高,谎报时拿前两志愿的机会更高。两行互不 SD 支配,所以诚实报告并没有 SD 支配这次谎报,已经违反上面“SD-策略防伪”的要求。
如果 1 号心中的效用为 $(7,6,0)$,诚实的期望是 $\tfrac34\times7=5.25$,谎报则是 $\tfrac12\times7+\tfrac13\times6=5.5$,确实获利。
若效用改成同样符合真实排序的 $(7,1,0)$,谎报期望只有约 3.83,反而低于 5.25。数字决定这次谎报是否获利,但不需要知道数字,也能判定“诚实并不 SD 支配谎报”。 不能把它说成与序数策略防伪无关。
SD 看的是每一层累计概率,不是只看第一志愿。
下一节讨论可切割的物品。用检查点核对本章的条件。
🧩 五、如果东西可以切:AW 与它的代价
最后换成两人、可分物品、价值随份额线性增加的模型,没有转账,也不要求每人只能拿一件。每件均分就能做到 EF;我们还希望兼顾效率、双方报分相等,并尽量少切物品。
调整赢家法(Adjusted Winner,AW)由 Brams 与 Taylor 提出。先采用所有单件估值都严格为正的基本版本,避免比值除以 0;每人的总报分都归一化为 100。
- 先逐件分。 每件给报分更高的一方,并列按事先固定规则处理。
- 找总分领先者。 比较双方对自己所得的评分。这里的“均等”指归一化报分相等,不是保证真实幸福感相等。
- 从领先者手中逐件转出。 按“领先者对此物的报分 ÷ 落后者对此物的报分”从小到大排列;转到将要反超时,只转出恰好平衡所需的份额。
把原来的 1/101 算出来
| 人 | $o_1$ | $o_2$ | $o_3$ | 总分 |
|---|---|---|---|---|
| 1 | 67 | 6 | 27 | 100 |
| 2 | 34 | 5 | 61 | 100 |
初分给 1 号 $o_1,o_2$,给 2 号 $o_3$,自己的分数为 73 与 61。1 号领先;他手上的比值为 $6/5=1.2$ 和 $67/34\approx1.97$,因此先转 $o_2$。
整件转出 $o_2$ 后,两人分数变成 67 与 66。再把 $o_1$ 的份额 $t$ 给 2 号:
$$67(1-t)=66+34t$$
$$t=\frac1{101}$$
最终 1 号保留 $o_1$ 的 $100/101$;2 号拿 $o_1$ 的 $1/101$,以及完整的 $o_2,o_3$。两人的归一化所得均为 $6700/101\approx66.34$,只切开了 $o_1$。
在这些假设下,按真实估值诚实报分的 AW 结果具有 PO、均等、EF 和 PROP,并且最多切开一件物品。 若参与者谎报,针对报分的保证不能自动当作针对真实偏好的保证。AW 本身不保证诚实报告是最优策略。AW 的性质与策略分析
可选:关于“唯一”和“不可能”的条件,不能混着用
“AW 唯一”说的是一个带条件的刻画。 Aziz 等(2015)刻画了同时 PO、均等且最多切一件的结果:它们可由合适的并列处理下的 AW 得到。若各物品的双方估值比两两不同,论文进一步保证 PO 且均等的分配唯一;有比值并列时,不能一般保证物品分法也唯一。
Zhou(1990)的经典结论属于另一模型。 它讨论 $n\ge3$ 时,$n$ 件物品随机分给 $n$ 个人、每人一件、报告完整基数效用的单边匹配;效率、策略防伪、同效用类型的对称待遇不能同时保证。不能把它直接写成“两人 AW 所在的任意可分物品模型”的定理。原论文摘要与模型
在本节可分、非负可加且没有其他限制的模型里,可以对照三种办法理解取舍:
- 全给预先指定的一人:不依赖报分,因而策略防伪。若他对每件都有正价值,这也是 PO;但不保证 EF。有零估值时,PO 还须另查。
- 每件固定各分一半:不依赖报分,而且 EF,所有物品都分完;但不保证 PO。
- 正总估值下的可分 Nash 福利最大化:平等权益模型中可兼顾 EF 与 PO;不自动保证策略防伪。
原先的“空分配”虽然在允许丢弃的模型里容易无嫉妒,但违反本章物品全部分完的要求,不能拿来当这个模型的合法实现。上面是三个例子,不是对所有机制的不可能性证明。
🔗 这一章连到哪里
| 去哪 | 为什么 |
|---|---|
| 20-公平分配的算法.md | 本章的带权嫉妒图就是那一章嫉妒图的加权版:那边只问「有没有边」,这边问「这条边值多少钱」 |
| 19-怎么算公平.md | 对照物品本身的 EF、EF1,与本章“含支付结果的 EF”和“概率行的 SD-无嫉妒”;三者检验对象不同 |
| 18-住房市场与TTC.md | 序列独裁在那一章出现过(多份禀赋时「PO + 防伪」的实现),这里给它套上随机化,就成了 RSD |
| 22-联盟博弈与核心.md | 下一章问的是另一半问题:收益已经赚到了,怎么在联盟内部分。第 18 章的「核心」会在那里被正式展开 |
| 推荐算法 15b · 广告:从推荐到竞价 | 那边是「有钱」的另一种用法:不是补偿嫉妒,而是用支付换取说真话(VCG)。同样的准线性效用假设,不同的目的 |
✅ 检查点
- 估值与支付为什么必须用同一单位?准线性假设是否自动解决预算问题?
- 一件物品两个人(估值 10 和 5),为什么「给估值低的人」这个分配怎么补钱都救不回来?
- 「可无嫉妒化」为什么是分配的性质而不是结果的性质?
- 带权嫉妒图的边权怎么定义?正权环意味着什么?
- (1) ⟹ (2) 的证明里,为什么求和之后右边等于 0?
- 手算例子里 $\ell(3)=4$ 为什么不是 3?说 $(0,3,4)$ 是最小支付,还要加什么条件?
- 哪两种分配是白送的「一定可无嫉妒化」?
- PS 的「吃蛋糕」过程里,$o_2$ 为什么在 $t=1/2$ 就被吃光?
- 1 号和 2 号分别更喜欢 RSD 还是 PS?用累计概率说明。
- SD 为什么是「问不出基数估值」时能给的最强承诺?它的局限是什么?
- RSD 和 PS 分别保证哪些 SD 性质?PS 的谎报例子为什么已经违反 SD-策略防伪?
- AW 最后为什么恰好切了 $o_1$ 的 $1/101$?
👀 答案
- 模型把物品价值与钱相加,因此估值须用货币单位。准线性表示钱线性进入效用、物品估值不随财富改变;它不自动证明跨人幸福感可比,也不排除预算约束。本章另行假设没有支付能力限制。
- 给估值 5 的人时,两人的要求分别是 $p_1-p_2\ge10$ 和 $p_1-p_2\le5$,不可能同时满足。这是对任意支付差的矛盾,不只是“试补 10 元失败”。
- 它问的是「存在一组支付让它无嫉妒吗」,即「这个分法有没有救」;「结果无嫉妒」问的才是「这一组具体的钱够不够」。
- $w(i,j)=v_i(X_j)-v_i(X_i)$,$i$ 对 $j$ 的嫉妒量(可为负)。正权环意味着沿环轮换整堆能让总福利严格变高 —— 这几堆分错了人,不是重分配稳定,因而不可无嫉妒化。
- 因为 $\pi$ 是排列,$\sum_i(p_i-p_{\pi(i)})$ 里每个 $p$ 被加恰好一次、减恰好一次,整体抵消为 0。
- $3\to2\to1$ 的权重为 $1+3=4$,大于直接去 1 号的 3;检查其他简单路径后,最大值是 4。最小性还要求所有补贴非负;允许收费时,可以共同平移支付,原向量不再是无约束的“最小”。
- ① USW 最大的分配(任何重指派都不可能更好);② 把所有物品打成一捆给最看重它的那个人。
- 因为 2 号和 3 号的第一志愿都是 $o_2$,两人同时以相同速度吃同一块重量为 1 的蛋糕,$\frac12$ 时刻正好吃光,各得 $1/2$。
- 1 号更喜欢 RSD:累计 $5/6,\,5/6,\,1$ 对 PS 的 $3/4,\,3/4,\,1$,每层都不少。2 号更喜欢 PS:累计 $1/2,\,3/4,\,1$ 对 RSD 的 $1/2,\,2/3,\,1$。两张表互不支配。
- 因为 $p\succeq^{SD}_i q$ 等价于「对每一个与 $i$ 排序相容的效用函数,$p$ 的期望效用都不低于 $q$」—— 不管真实数字是多少都不会更差。局限是它只是偏序:$(1/2,0,1/2)$ 与 $(1/3,1/2,1/6)$ 第一层前者赢、第二层后者赢,不可比(对应「搏一把」与「求稳妥」的取舍,而序数偏好里没有决定它的信息)。
- RSD 保证 SD-策略防伪,但一般不保证 SD-有效、SD-无嫉妒;PS 保证后两者,却不保证 SD-策略防伪。例子中诚实报告与谎报所得互不 SD 支配,已经不满足“诚实报告 SD 支配每次谎报”的定义;效用 $(7,6,0)$ 进一步展示谎报获利。
- 转完 $o_2$ 后是 67 : 66,还差一点。设 2 号拿到 $o_1$ 的比例 $t$,令 $67(1-t)=66+34t$ 得 $t=1/101$,两人最终都是 $67\times\frac{100}{101}\approx66.34$ 分 —— 均等。
本节回顾
⚡ 走神救援
下一节 👉 22-联盟博弈与核心.md