📑 本页目录（点开跳转）
18 · 住房市场与 TTC
⏱ 40 分钟 ｜ ⭐⭐ 人指向房、房指向主人，找环就成交
🎯 一句话
每个人手里已经有一套房、都想换更好的：让所有人指向自己最想要的房、每套房指向它的主人，图里一定会出现环 —— 环上的人原地互换，一轮锁定一批，这就是 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$，让所有人不变差、至少一个人严格变好。
③ 核心（core）：不存在阻挡联盟 $S \subseteq N$ —— 也就是找不到一伙人，只用他们自己手里的那些房内部重新分配，就能让 $S$ 里每个人都严格变好。
三者的关系一句话讲清：核心 ⟹ IR + PO。取 $S=\{i\}$ 单人联盟就得到 IR；取 $S=N$ 全体联盟就得到 PO。核心是「任意规模的小团体都造不了反」，比另外两个都强。
手算一个最小例子：两人两房，$1$ 拥有 $o_1$ 但想要 $o_2$，$2$ 拥有 $o_2$ 但想要 $o_1$。 - 「都不动」：IR ✓（没变差），但被 $\{1,2\}$ 阻挡 —— 他们一换双双变好。不在核心，也不 PO。 - 「互换」：两人都拿到最爱，任何联盟都造不了更好的反。在核心里。
🧩 三、TTC 手算套路
Gale 的顶级交易环算法（Top Trading Cycle）。四步：
- 建有向图：每个人指向当前图里他最想要的那套房；每套房指向它的主人
- 从任意一点出发沿着边走，一定会走出一个环
- 环上成交：环里每个人拿走他指着的那套房。把环上的人和房整个从图里删掉
- 剩下的人重新指向「剩余房子里最想要的那套」，回到第 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)$。
⭐ 验一下 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 的结果同时是策略防伪、个体理性、帕累托最优、核心稳定的。
核心稳定的论证按轮次归纳，很直白：第 1 轮环上的人拿到的是全场最想要的房，他们不可能再变好，所以任何阻挡联盟都不会包含他们；而且他们的房也不会流到别人手里。把这批人整个划走，对剩下的人重复同样的话。PO 用完全一样的论证：任何帕累托改进都不能改动第 1 轮环上的人，于是问题递归到剩余部分。
策略防伪的直觉：假设 $i$ 谎报，指向第 $k$ 顺位的房 $h_k$ 而成了环。那说明图里存在一条从 $h_k$ 回到 $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）（链不需要同时手术，因为链头不用先付出，所以链可以做得很长）。
🧩 六、每人不止一件东西的时候，全塌了
上面所有好消息都建立在「一人一件」上。一旦每人手上有一堆东西要交换，三条性质就凑不齐了。
先得定义「怎么比较两堆东西」。最常用的是字典序偏好：两堆各自排好序，从最好的一件开始逐位比，第一个不同的位置说了算。例如 $a \succ b \succ c$ 时 $\{a,c\} \succ \{b,c\}$。
💀 定理：字典序偏好下，不存在同时满足策略防伪、个体理性、帕累托最优的交换规则。 反例只要 2 个人 3 件东西：$1$ 拥有 $\{a,b\}$、$2$ 拥有 $\{c\}$，真实偏好 $1: c \succ a \succ b$，$2: a \succ b \succ c$。三个 IR+PO 的结果里，不论机制选哪一个，总有一方能靠谎报换掉它。
三条只能挑两条，而且每一种组合都有个朴素得可笑的实现：
| 要哪两条 | 怎么做到 | 代价 |
|---|---|---|
| 策略防伪 + IR | 不交易，谁的东西还是谁的 | 完全没有效率 |
| IR + 帕累托最优 | 在当前分配上一路做帕累托改进直到改不动 | 可被操纵 |
| 帕累托最优 + 策略防伪 | 序列独裁：按固定顺序，每人从剩下的东西里挑走最想要的一整捆 | 排在后面的人可能被拿光，违反 IR |
⭐ 这张表值得记住的不是三行内容，而是这个形状：不可能定理不会告诉你「都做不到」，它告诉你「你必须先说清楚放弃哪一条」。 上一章的 Roth 1982 是这个形状，这里是，下一章的 EF 也会是。
🔗 这一章连到哪里
| 去哪 | 为什么 |
|---|---|
| 17-稳定匹配.md | 回头对照：那边两边都有偏好、判据是「无阻挡对」；这边只有一边有偏好但有产权，判据升级成「无阻挡联盟」（核心） |
| 19-怎么算公平.md | 下一章把「一人一件」放宽成「一人一堆」，并且承认 TTC 这条路走不通了 —— 于是判据从效率转向公平 |
| 16 · 机制设计在解什么 | Ma 1994 的唯一性定理是「刻画一类机制」的典型例子，回去看这类结论在机制设计里为什么值钱 |
| ../推荐算法/15b-广告-从推荐到竞价.html | 想看「策略防伪能不能靠钱买到」：那边的 VCG 用转移支付换来了防伪，这里没有钱，只能靠产权结构 |
✅ 检查点
- 住房市场和上一章的双边匹配，模型上最本质的两个差别是什么？
- 为什么「个体理性」在这个设定里是绕不开的，而上一章几乎不提它？
- 核心、IR、PO 三者的强弱关系是什么？分别取什么样的联盟能推出另外两个？
- TTC 的图里为什么一定存在环？为什么两个环不会共用点？
- 手算例子第 2 轮里，人 4 的指向为什么从 $o_2$ 变成了 $o_5$？
- 人 3 最后拿回了自己的 $o_3$。它有没有办法通过谎报偏好拿到 $o_4$？为什么？
- Ma 1994 的定理说的是什么？它和「TTC 是个好算法」这句话有什么区别？
- 肾脏交换里为什么要限制环长？限制之后计算复杂度发生了什么变化？
- 多份初始禀赋时，「策略防伪 + 个体理性」这一组的实现是什么？代价是什么？
👀 答案
- ① 只有一边有偏好 —— 房子不是 agent，没有能动性；② 有初始禀赋（产权），每个人手里已经有一套房，随时可以退出不换。
- 因为有产权：结果比自己原来那套还差的话，人直接不参加。所以 IR 是参与约束。上一章大家手上什么都没有（「宁可配上也不愿落单」），IR 几乎自动满足。
- 核心最强，核心 ⟹ IR + PO。取单人联盟 $S=\{i\}$ 推出 IR；取全体联盟 $S=N$ 推出 PO。
- 每个点恰好有一条出边（人指一套房、房指一个主人）。点有限，沿边一直走必然重复访问某点，环就闭合了。出度为 1 也意味着两条不同的环不可能共用点，所以删环是安全的。
- 因为第 1 轮成交时 $o_2$ 连同人 1、人 2、$o_1$ 一起被删掉了。4 的指向规则是「当前图里最想要的房」，$o_2$ 没了就顺着偏好往下取 $o_5$。
- 不能。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 报什么都改不了别人的指向。
- Ma 1994：满足「策略防伪 + IR + PO」的机制本质上只有 TTC。「TTC 是好算法」是充分性（它满足这三条）；这条定理是必要性 —— 你想要这三条，就没有别的机制可选了。
- 因为同一个环上的手术必须同时做（否则先捐的一方可能被后面的人反悔而白白失去一个肾），$k$ 人环要 $2k$ 组手术团队，现实上限通常是 2 或 3。而 $L=3$ 且允许并列时，判断是否存在「人人拿到最想要那类」的 $L$-分配是 NP 完全的（从 3-环覆盖归约）—— 无上限时 TTC 是多项式的。
- 实现是不交易：谁的东西还是谁的。显然骗不动也不会亏，但完全没有效率 —— 所有本可以双赢的交换全都不发生。
🛑 可以停在这里
⚡ 走神救援
这一章换了设定：只有一边有偏好（房子不是 agent），但每个人手里已经有一套房。多出来的产权带来一个新的参与约束 IR（个体理性）：结果不能比自己原来那套差，否则人直接不参加。判据一共三层：IR、PO（帕累托最优）、核心（core） —— 核心要求「找不到任何一伙人，只用他们自己手上的房内部重分配就能让每个人都严格变好」。核心最强：取单人联盟得到 IR，取全体联盟得到 PO。
算法是 TTC（顶级交易环），四步：人指向当前图里最想要的房、房指向它的主人 → 沿边走出一个环 → 环上每人拿走自己指的那套房，环整个删掉 → 剩下的人重新指向剩余房子里最想要的，重复。⭐ 一定有环，因为每个点恰好有一条出边，点有限、沿边走必然重复；也正因为出度是 1，不同的环不共用点，删环是安全的。
手算的 5 人例子跑了 3 轮：第 1 轮 $1 \to o_2 \to 2 \to o_1 \to 1$ 闭环，1 拿 $o_2$、2 拿 $o_1$（3、4、5 都指着环里的房，只能干看着）；第 2 轮 4 的目标 $o_2$ 已被删掉，改指 $o_5$，5 改指 $o_4$，闭出新环，4 拿 $o_5$、5 拿 $o_4$；第 3 轮只剩 3 和 $o_3$，自环，3 拿回自己的房。3 是全场唯一没换成的人，但它没亏 —— 这正是 IR。3 也无法靠谎报拿到 $o_4$，因为 4 和 5 在被匹配之前永远不会指向 $o_3$。
两条定理：Shapley–Scarf / Roth–Postlewaite —— 严格偏好下 TTC 同时是策略防伪、IR、PO、核心稳定的（核心和 PO 都按轮次归纳证明：第 1 轮环上的人拿到全场最想要的，不可能再改进，划走后递归）。Ma 1994 —— 满足「策略防伪 + IR + PO」的机制本质上只有 TTC，这是刻画定理不是夸奖。偏好有并列时唯一性就没了。
落地是肾脏配对捐赠：每个病人自带一位配型不合的亲属捐者作为禀赋。但现实加了一条约束 —— 环上所有手术必须同时做（防止有人先捐后被反悔），$k$ 人环需要 $2k$ 组团队，所以环长上限通常是 2 或 3。💀 而 $L=3$ 加上并列偏好，问题从多项式跳到 NP 完全（3-环覆盖归约）。实践用整数规划 + 利他捐者发起的链（链不用同时手术，可以做得很长）。最后：一旦每人持有多件东西（字典序偏好），策略防伪 + IR + PO 就不可能同时满足，只能三选二 —— 分别对应「不交易」「一路帕累托改进」「序列独裁」。
下一节 👉 19-怎么算公平.md