🏠 总目录📚 本教程 18 · 住房市场与 TTC ← →

每个人已有一间房时,交换循环怎样同时完成?

读后可检查:先核对个体理性和效率,再按 TTC 步骤移除循环并检查结论的设定。

📑 本页目录(点开跳转)

18 · 住房市场与 TTC

⏱ 32 分钟 | ⭐ 人指向房、房指向主人,找环就成交


🎯 一句话

每个人手里已经有一套房、都想换更好的:让所有人指向自己最想要的房、每套房指向它的主人,图里一定会出现环 —— 环上的人原地互换,一轮锁定一批,这就是 TTC。

而且它是唯一同时做到「不亏、不能再改进、骗不动」的机制 —— 这个「唯一」是定理,不是修辞。


🧩 一、这次只有一边有偏好

上一章是双边匹配:学生挑学校,学校也挑学生。这一章换个设定:

住房市场(Shapley–Scarf, 1974):$(N, O, \succ, e)$ - $N$ 是 $n$ 个人,$O$ 是 $n$ 套房,房子没有偏好(它不是 agent,没有能动性) - $e_i = \{o_i\}$:每个人手里已经有一套房(初始禀赋 / 产权) - 每个人对所有房子有严格偏好 - 结果是一个匹配 $X$,每人恰好拿到一套房

和上一章的差别不只是「少了一边偏好」,更关键的是多了产权。房子已经是你的了,你可以随时掀桌子说「我不换了,我住我自己的」。这一条会直接长出一个新判据。

真实场景:宿舍/工位调换、二手车置换、肾脏配对捐赠(每个病人自带一个配型不合的亲属捐者 —— 那就是他的「初始禀赋」)。


🧩 二、什么算好结果:IR / PO / 核心

① 个体理性(IR):$X_i \succeq_i e_i$ —— 没有人比自己原来更差。

⚠️ 这是参与约束:违反它的机制根本没人会来。有了 IR,每个人甚至可以直接把「比自己那套还差的房」从列表里划掉,反正永远轮不到。

② 帕累托最优(PO):不存在另一个分配 $Y$,让所有人不变差、至少一个人严格变好。

③ 本章采用强核心(strong / strict core):不存在联盟 $S$,仅用成员的初始禀赋重分配,令所有成员不变差、至少一人严格变好。

另一种“弱核心”只排除让所有成员都严格变好的联盟。两种阻挡约定不同;下面“推出 PO、严格偏好时唯一”的结论对应强核心。两种定义与 TTC 的研究说明

本章强核心推出 IR 与 PO:单人联盟检查不比初始房屋差;大联盟检查所有人不差、至少一人改善的可行重分配。

为什么不能把“所有人严格改善”与“至少一人改善”混用?

三人初始分别拥有 $a,b,c$,偏好如下:

人 从好到坏
1 $b\succ a\succ c$
2 $a\succ c\succ b$
3 $a\succ b\succ c$

分配 $(b,c,a)$ 没有让联盟成员全部严格改善的阻挡:1、3 已拿最爱,2 单独拿回自己的 $b$ 反而更差。

但联盟 $\{1,2\}$ 可把自己的初始房屋 $a,b$ 分成 $(b,a)$:1 不变、2 变好。这就是强核心要排除的阻挡;联盟之外的 3 号不参与该联盟的改善条件。

这个例子只用来证明两种核心集合不同:TTC 得到 $(b,a,c)$,而 $(b,c,a)$ 仍在只排除全员严格改善的弱核心里。不能据此声称弱核心在严格偏好下一定唯一。

手算一个最小例子:两人两房,$1$ 拥有 $o_1$ 但想要 $o_2$,$2$ 拥有 $o_2$ 但想要 $o_1$。 - 「都不动」:IR ✓(没变差),但被 $\{1,2\}$ 阻挡 —— 他们一换双双变好。不在核心,也不 PO。 - 「互换」:两人都拿到最爱,任何联盟都造不了更好的反。在核心里。


🧩 三、TTC 手算套路

Gale 的顶级交易环算法(Top Trading Cycle)。四步:

  1. 建有向图:每个人指向当前图里他最想要的那套房;每套房指向它的主人
  2. 从任意一点出发沿着边走,一定会走出一个环
  3. 环上成交:环里每个人拿走他指着的那套房。把环上的人和房整个从图里删掉
  4. 剩下的人重新指向「剩余房子里最想要的那套」,回到第 2 步;图空了就结束

⭐ 为什么一定有环:图里每个点都恰好有一条出边(人指一套房,房指一个主人)。从任意点出发一直走,点是有限的,必然重复访问某个点 —— 那一刻环就闭合了。同理,因为出度都是 1,不同的环不会共用任何点,删掉一个环不会破坏别的环。

完整走一遍

5 个人,$i$ 拥有 $o_i$:

人 拥有 偏好(从最想要开始)
1 $o_1$ $o_2 \succ o_1 \succ o_3 \succ o_4 \succ o_5$
2 $o_2$ $o_1 \succ o_3 \succ o_2 \succ o_4 \succ o_5$
3 $o_3$ $o_4 \succ o_5 \succ o_2 \succ o_3 \succ o_1$
4 $o_4$ $o_2 \succ o_5 \succ o_4 \succ o_1 \succ o_3$
5 $o_5$ $o_1 \succ o_4 \succ o_5 \succ o_2 \succ o_3$

第 1 轮 指向:$1 \to o_2$、$2 \to o_1$、$3 \to o_4$、$4 \to o_2$、$5 \to o_1$。 从 3 出发走走看:$3 \to o_4 \to 4 \to o_2 \to 2 \to o_1 \to 1 \to o_2$ —— $o_2$ 重复了,环闭合在 $1 \to o_2 \to 2 \to o_1 \to 1$。

成交:1 拿 $o_2$,2 拿 $o_1$。删掉 $1,2,o_1,o_2$。 (注意 3、4、5 都指着环里的房子,只能干看着 —— 他们不在环上,什么都拿不到。)

第 2 轮 只剩 $3,4,5$ 和 $o_3,o_4,o_5$。4 原来指 $o_2$,$o_2$ 没了,改指剩余里最想要的 $o_5$;5 原来指 $o_1$,改指 $o_4$;3 还是指 $o_4$。 走一遍:$4 \to o_5 \to 5 \to o_4 \to 4$ —— 环闭合。

成交:4 拿 $o_5$,5 拿 $o_4$。删掉。

第 3 轮 只剩 3 和 $o_3$。3 想要的 $o_4$、$o_5$、$o_2$ 全被换走了,只能指自己的 $o_3$ —— 自环。3 拿回自己的房。

最终:$X = (o_2,\ o_1,\ o_3,\ o_5,\ o_4)$。

第 1 轮:找到环 1→o2→2→o1→1 人 1 o2 人 2 o1 第 2 轮:删掉后新环 4→o5→5→o4→4 人 4 o5 人 5 o4 人 3 o3 第 3 轮:自环 3 留着自己的房
TTC 的三轮:环上的人一次成交并整体退场,剩下的人重新指向剩余房子

⭐ 验一下 IR:1 拿 $o_2 \succ o_1$ ✓,2 拿 $o_1 \succ o_2$ ✓,4 拿 $o_5 \succ o_4$ ✓,5 拿 $o_4 \succ o_5$ ✓,3 拿回 $o_3$ —— 不比原来差,IR 成立。3 是全场唯一没换成的人,但它也没亏。


🧩 四、TTC 好在哪:两条定理

⭐ 定理(Shapley–Scarf 1974;Roth–Postlewaite 1977): 偏好严格时,TTC 的结果同时是策略防伪、个体理性、帕累托最优、核心稳定的。

强核心的论证要允许“有人不变”。 第一轮的人都拿到最喜欢的房,若他们参加一个不使任何成员变差的联盟交换,只能保留这套房。

房屋来自初始禀赋,因此它的原房主也必须在联盟中。沿 TTC 环追溯,会要求整个环在场且每人保留 TTC 所得;这个环的房屋不能再交给其他人。

删去这批已经锁定的人和房,对后续轮次重复。最终没有成员能严格改善,所以不存在强阻挡。以大联盟为特例也得到 PO。

策略防伪的直觉:假设 $i$ 谎报,指向第 $k$ 顺位的房 $h_k$ 而成了环。图里已经有一条从 $h_k$ 回到 $i$ 的路径。

关键观察:固定其他人的报告,$i$ 还没离开时,这条路径不会自己消失。一个点只在它指着的目标被移除后改出边;路径上的点若进入被移除的环,沿出边也会走到 $i$,因此 $i$ 也在这个环中。

所以,一旦这样的回路可用,$i$ 可以继续先指着更喜欢的可用房屋;要么更早拿到更好的,要么最终仍可与 $h_k$ 成环。完整策略防伪定理还需比较真实与谎报两个运行过程;这段只解释“为什么不必抢先指向较差房屋”的观察。

⭐ 定理(Ma 1994):满足策略防伪 + 个体理性 + 帕累托最优的机制,本质上只有 TTC。 这是个刻画定理,不是「TTC 表现好」,是「这三条一起要,你别无选择」。上一章 Roth 1982 告诉你稳定 + 双边防伪做不到;这里反过来 —— 单边设定下三条能同时做到,代价是机制被钉死了。

⚠️ 允许偏好并列(indifference)时,不能直接套用上述严格偏好定理。 必须说明如何选最喜爱的房屋、采用哪种阻挡定义,再分别核对防伪、效率与核心;不是“一有并列,所有实例的全部性质都失败”。


🧩 五、真实落地:肾脏交换

肾脏配对捐赠几乎是为 TTC 量身定做的:每个病人自带一位愿意捐、但配型不合的亲属 —— 那就是他的初始禀赋。「病人 A 的亲属捐给病人 B,B 的亲属捐给 A」就是一个长度为 2 的环。

⚠️ 但现实加了一条算法里没有的约束:环不能太长。

因为同一个环上的所有手术必须同时做。理由很硬:只要有人先捐了、下一环节反悔,先捐的那一家就是白白失去一个肾。$k$ 个人的环要同时占用 $2k$ 间手术室、$2k$ 组团队 —— 现实中通常把环长上限设成 2 或 3。

而这一刀切下去,问题的难度整个变了:

💀 定理:环长上限 $L=3$、且偏好里允许并列时,判断「是否存在一个让每个人都拿到最想要的那类肾的 $L$-分配」是 NP 完全的。 (从 3-环覆盖问题 归约:图的每个顶点当一个人,$i$ 只接受它的邻居手上的东西。)

无上限的 TTC 是多项式的,加一条「环最长 3」就跳到 NP 完全 —— 这是「现实约束把易解问题变难」的一个非常干净的例子。实践中的解法:整数规划 + 利他捐者发起的链(chain)(链不需要同时手术,因为链头不用先付出,所以链可以做得很长)。


🧩 六、多份禀赋:先说清能报告什么

一人一房的 TTC 定理不能直接推广到每人拥有多件物品。需要先交代:每人最后能拿几件、怎样比较整堆,以及能否隐藏初始禀赋。

字典序偏好可以这样比较集合:找对称差中排名最高的物品,包含它的集合更好。例如 $a\succ b\succ c$ 时,$\{a,c\}\succ\{b,c\}$。这里假定物品是好物品,添入物品不变差。

一个明确的不可能性模型

Todo 等(2014)研究多份私有禀赋:参与者既能谎报偏好,也能隐藏自己的一部分物品。

此时策略防伪要求“真实偏好 + 披露全部禀赋”是占优报告,并已蕴含个体理性。该模型下,即使字典序偏好,策略防伪与帕累托效率也无法兼得。原论文模型与结论

不能把它缩成“所有多物品场景都三选二”。改变报告权限、配额或偏好域,就改变了定理前提。

两人三物例子:它能证明到哪里?

1 拥有 $\{a,b\}$,2 拥有 $\{c\}$;真实偏好为 $1:c\succ a\succ b$、$2:a\succ b\succ c$。

允许任意件数、物品完整分配时,可枚举出三个 IR + PO 结果:

1 号拿到 2 号拿到
$\{c\}$ $\{a,b\}$
$\{a,c\}$ $\{b\}$
$\{b,c\}$ $\{a\}$

这证明当前真实偏好下有多个候选结果。只列这一个轮廓,不能证明任意机制都可操纵;还需约束机制在谎报轮廓上的输出,或使用明确覆盖该报告模型的定理。

三种候选做法,不是同一个不可能性定理的证明

以下先固定公开禀赋、只允许报告偏好,不与上面的隐藏物品模型混用。

不可能定理用于说明一套明确规则的取舍,不是把“多拿几件”本身当作失败证明。


🔗 这一章连到哪里

去哪 为什么
17-稳定匹配.md 回头对照:那边两边都有偏好、判据是「无阻挡对」;这边只有一边有偏好但有产权,判据升级成「无阻挡联盟」(核心)
19-怎么算公平.md 下一章把「一人一件」放宽成「一人一堆」,并且承认 TTC 这条路走不通了 —— 于是判据从效率转向公平
16 · 机制设计在解什么 Ma 1994 的唯一性定理是「刻画一类机制」的典型例子,回去看这类结论在机制设计里为什么值钱
推荐算法 15b · 广告:从推荐到竞价 想看「策略防伪能不能靠钱买到」:那边的 VCG 用转移支付换来了防伪,这里没有钱,只能靠产权结构

✅ 检查点

  1. 住房市场和上一章的双边匹配,模型上最本质的两个差别是什么?
  2. 为什么「个体理性」在这个设定里是绕不开的,而上一章几乎不提它?
  3. 核心、IR、PO 三者的强弱关系是什么?分别取什么样的联盟能推出另外两个?
  4. TTC 的图里为什么一定存在环?为什么两个环不会共用点?
  5. 手算例子第 2 轮里,人 4 的指向为什么从 $o_2$ 变成了 $o_5$?
  6. 人 3 最后拿回了自己的 $o_3$。它有没有办法通过谎报偏好拿到 $o_4$?为什么?
  7. Ma 1994 的定理说的是什么?它和「TTC 是个好算法」这句话有什么区别?
  8. 肾脏交换里为什么要限制环长?限制之后计算复杂度发生了什么变化?
  9. 多份初始禀赋时,「策略防伪 + 个体理性」这一组的实现是什么?代价是什么?
👀 答案
  1. ① 只有一边有偏好 —— 房子不是 agent,没有能动性;② 有初始禀赋(产权),每个人手里已经有一套房,随时可以退出不换。
  2. 因为有产权:结果比自己原来那套还差的话,人直接不参加。所以 IR 是参与约束。上一章大家手上什么都没有(「宁可配上也不愿落单」),IR 几乎自动满足。
  3. 核心最强,核心 ⟹ IR + PO。取单人联盟 $S=\{i\}$ 推出 IR;取全体联盟 $S=N$ 推出 PO。
  4. 每个点恰好有一条出边(人指一套房、房指一个主人)。点有限,沿边一直走必然重复访问某点,环就闭合了。出度为 1 也意味着两条不同的环不可能共用点,所以删环是安全的。
  5. 因为第 1 轮成交时 $o_2$ 连同人 1、人 2、$o_1$ 一起被删掉了。4 的指向规则是「当前图里最想要的房」,$o_2$ 没了就顺着偏好往下取 $o_5$。
  6. 不能。3 想要的是 $o_4$(或 $o_5$),要拿到就必须和 4(或 5)在同一个环上,也就是需要 4 或 5 在某一轮指向 $o_3$。但 4 的偏好是 $o_2 \succ o_5 \succ o_4$,5 的是 $o_1 \succ o_4 \succ o_5$,两人在轮到自己之前都能指到更好的房,永远不会指向 $o_3$。3 报什么都改不了别人的指向。
  7. Ma 1994:满足「策略防伪 + IR + PO」的机制本质上只有 TTC。「TTC 是好算法」是充分性(它满足这三条);这条定理是必要性 —— 你想要这三条,就没有别的机制可选了。
  8. 因为同一个环上的手术必须同时做(否则先捐的一方可能被后面的人反悔而白白失去一个肾),$k$ 人环要 $2k$ 组手术团队,现实上限通常是 2 或 3。而 $L=3$ 且允许并列时,判断是否存在「人人拿到最想要那类」的 $L$-分配是 NP 完全的(从 3-环覆盖归约)—— 无上限时 TTC 是多项式的。
  9. 在公开固定禀赋、仅报告偏好的候选设计中,不交易保证 SP 与 IR,但不保证 PO。多份私有禀赋的定理还允许隐藏物品,不能把两种报告模型混为一谈。

本节回顾

⚡ 走神救援

这一章换了设定:只有一边有偏好,但每个人手里已经有一套房。多出来的产权带来一个新约束——⭐ 结果不能比自己原来那套差,否则人直接不参加。

本章采用强核心:排除所有成员不差、至少一人改善的联盟重分配。单人联盟给 IR,大联盟给 PO。

算法是 TTC(顶级交易环):人指向最想要的房、房指向它的主人,沿边走出一个环就整环成交并删掉,剩下的重新指。⭐ 一定有环,因为每个点恰好有一条出边;也正因为出度是 1,不同的环不共用点,删环是安全的。

手算例子里有个人从头到尾没换成,但他没亏——⭐ 这正是个体理性。而他也无法靠谎报捞到好处,因为别人在被匹配之前根本不会指向他的房。

两条定理:TTC 同时满足策略防伪、个体理性、帕累托最优和核心稳定;⭐ 而满足前三条的机制本质上只有 TTC——这是刻画定理,不是夸奖。 ⚠️ 偏好允许并列时,唯一性就没了。

落地是肾脏配对捐赠:每个病人自带一位配型不合的亲属,本质就是「手里已有一套房」。

⚠️ 和上一章的分界值得记一句:稳定匹配是两边都有偏好、谁都没有存货;这一章是一边有偏好、而每个人都有存货——⭐ 正是「存货」让个体理性成为硬约束,也正是它让核心这个更强的判据变得可达。

下一节 👉 19-怎么算公平.md

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