🏠 总目录📚 本教程 21 · 有钱与随机分配 ← →

加入金钱或随机机会后,公平应怎样比较?

读后可检查:分别检查补偿可行性、排序下的随机支配与可分物品的设定。

📑 本页目录(点开跳转)

21 · 有钱与随机分配

⏱ 42 分钟 | 时间仅供参考,可分三次读:转账、抽签、可分物品


🎯 一句话

不能把东西切开,不代表只能接受眼前的分法:可以研究转账补偿,也可以比较抽签机会;如果东西本来就能切,则又是另一套问题。

三条路线的条件不同,按需要选一条,不必一次读完:


🧩 一、把钱加进来

上一章的不可分物品不保证存在 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$。

这一件物品的例子里,给货币估值较高的人才能补平。推广到多件物品后,准确条件是现有几堆之间重新换主人,能否提高总估值,而不是笼统地说“分配不浪费”或“已经 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)$,移项便是无嫉妒条件。

怎么真的算出来

⭐ 两个白送的构造: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,后续边可能把总和补成正数;本例是检查所有候选后才得到这个结果。

321+1+3直接走:+3 经 2 号:1 + 3 = 4,比直接走多 1
只看与 3 号最大路径有关的边:补贴必须覆盖间接比较,不能只补直接看见的差额。完整图的其他边见上面的边权表。

支付:$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 节

  1. 每轮每人最多拿一件;最后物品不足时,可以添对所有人都值 0 的虚拟物品。
  2. 每轮都选最大总权匹配,不是随便找一个匹配,也不是每个人同时选自己最喜欢的物品。
  3. 各轮发完后,删去虚拟物品,实际物品分配同时满足 EF1 和可无嫉妒化。
可选:两项保证分别依赖什么

可无嫉妒化:固定任意一个人的环。单轮若沿环换物品能增加总估值,就与该轮最大权匹配矛盾。每一轮对这个环的权重都不大于 0;可加性保证总分配中的环权重是各轮之和,因此仍不大于 0。

EF1:第 $t$ 轮给 $i$ 的物品,在 $i$ 看来,至少不比任何留到下一轮的物品差。否则只把 $i$ 的匹配边换到那件尚未发出的物品,就能提高本轮总权重。

所以可以把 $i$ 第 $t$ 轮所得,与 $j$ 第 $t+1$ 轮所得逐一比较。把这些不等式相加,就能覆盖 $j$ 除第一轮物品外的全部价值。这才是 EF1 的原因;只控制每轮件数,不能推出该结论。


固定分堆无正权环,就能在本章支付假设下补平。

下一节讨论抽签机会怎么分。若物品可分,后文介绍 AW。


🧩 三、不用钱,只报排序:比较抽签机会

换个场景:分宿舍、分实习岗位、分课程名额。不能收钱(政策不允许),而且只问得出排序问不出估值 —— 你可以让学生把宿舍排个序,但「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 的蛋糕:

  1. 所有人同时、以相同速度开吃自己当前最想要且还没吃完的那件
  2. 一件被吃光了,正在吃它的人立刻转向自己列表里下一件还没吃完的
  3. 全部吃光时停。每个人吃掉的份额就是他的概率

完整走一遍(还是上面那个实例):

第一步:从 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 支配所有谎报 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. 先逐件分。 每件给报分更高的一方,并列按事先固定规则处理。
  2. 找总分领先者。 比较双方对自己所得的评分。这里的“均等”指归一化报分相等,不是保证真实幸福感相等。
  3. 从领先者手中逐件转出。 按“领先者对此物的报分 ÷ 落后者对此物的报分”从小到大排列;转到将要反超时,只转出恰好平衡所需的份额。

把原来的 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 所在的任意可分物品模型”的定理。原论文摘要与模型

在本节可分、非负可加且没有其他限制的模型里,可以对照三种办法理解取舍:

原先的“空分配”虽然在允许丢弃的模型里容易无嫉妒,但违反本章物品全部分完的要求,不能拿来当这个模型的合法实现。上面是三个例子,不是对所有机制的不可能性证明。


🔗 这一章连到哪里

去哪 为什么
20-公平分配的算法.md 本章的带权嫉妒图就是那一章嫉妒图的加权版:那边只问「有没有边」,这边问「这条边值多少钱」
19-怎么算公平.md 对照物品本身的 EF、EF1,与本章“含支付结果的 EF”和“概率行的 SD-无嫉妒”;三者检验对象不同
18-住房市场与TTC.md 序列独裁在那一章出现过(多份禀赋时「PO + 防伪」的实现),这里给它套上随机化,就成了 RSD
22-联盟博弈与核心.md 下一章问的是另一半问题:收益已经赚到了,怎么在联盟内部分。第 18 章的「核心」会在那里被正式展开
推荐算法 15b · 广告:从推荐到竞价 那边是「有钱」的另一种用法:不是补偿嫉妒,而是用支付换取说真话(VCG)。同样的准线性效用假设,不同的目的

✅ 检查点

  1. 估值与支付为什么必须用同一单位?准线性假设是否自动解决预算问题?
  2. 一件物品两个人(估值 10 和 5),为什么「给估值低的人」这个分配怎么补钱都救不回来?
  3. 「可无嫉妒化」为什么是分配的性质而不是结果的性质?
  4. 带权嫉妒图的边权怎么定义?正权环意味着什么?
  5. (1) ⟹ (2) 的证明里,为什么求和之后右边等于 0?
  6. 手算例子里 $\ell(3)=4$ 为什么不是 3?说 $(0,3,4)$ 是最小支付,还要加什么条件?
  7. 哪两种分配是白送的「一定可无嫉妒化」?
  8. PS 的「吃蛋糕」过程里,$o_2$ 为什么在 $t=1/2$ 就被吃光?
  9. 1 号和 2 号分别更喜欢 RSD 还是 PS?用累计概率说明。
  10. SD 为什么是「问不出基数估值」时能给的最强承诺?它的局限是什么?
  11. RSD 和 PS 分别保证哪些 SD 性质?PS 的谎报例子为什么已经违反 SD-策略防伪?
  12. AW 最后为什么恰好切了 $o_1$ 的 $1/101$?
👀 答案
  1. 模型把物品价值与钱相加,因此估值须用货币单位。准线性表示钱线性进入效用、物品估值不随财富改变;它不自动证明跨人幸福感可比,也不排除预算约束。本章另行假设没有支付能力限制。
  2. 给估值 5 的人时,两人的要求分别是 $p_1-p_2\ge10$ 和 $p_1-p_2\le5$,不可能同时满足。这是对任意支付差的矛盾,不只是“试补 10 元失败”。
  3. 它问的是「存在一组支付让它无嫉妒吗」,即「这个分法有没有救」;「结果无嫉妒」问的才是「这一组具体的钱够不够」。
  4. $w(i,j)=v_i(X_j)-v_i(X_i)$,$i$ 对 $j$ 的嫉妒量(可为负)。正权环意味着沿环轮换整堆能让总福利严格变高 —— 这几堆分错了人,不是重分配稳定,因而不可无嫉妒化。
  5. 因为 $\pi$ 是排列,$\sum_i(p_i-p_{\pi(i)})$ 里每个 $p$ 被加恰好一次、减恰好一次,整体抵消为 0。
  6. $3\to2\to1$ 的权重为 $1+3=4$,大于直接去 1 号的 3;检查其他简单路径后,最大值是 4。最小性还要求所有补贴非负;允许收费时,可以共同平移支付,原向量不再是无约束的“最小”。
  7. ① USW 最大的分配(任何重指派都不可能更好);② 把所有物品打成一捆给最看重它的那个人。
  8. 因为 2 号和 3 号的第一志愿都是 $o_2$,两人同时以相同速度吃同一块重量为 1 的蛋糕,$\frac12$ 时刻正好吃光,各得 $1/2$。
  9. 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$。两张表互不支配。
  10. 因为 $p\succeq^{SD}_i q$ 等价于「对每一个与 $i$ 排序相容的效用函数,$p$ 的期望效用都不低于 $q$」—— 不管真实数字是多少都不会更差。局限是它只是偏序:$(1/2,0,1/2)$ 与 $(1/3,1/2,1/6)$ 第一层前者赢、第二层后者赢,不可比(对应「搏一把」与「求稳妥」的取舍,而序数偏好里没有决定它的信息)。
  11. RSD 保证 SD-策略防伪,但一般不保证 SD-有效、SD-无嫉妒;PS 保证后两者,却不保证 SD-策略防伪。例子中诚实报告与谎报所得互不 SD 支配,已经不满足“诚实报告 SD 支配每次谎报”的定义;效用 $(7,6,0)$ 进一步展示谎报获利。
  12. 转完 $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

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