市场设计与匹配理论

稳定匹配、延迟接受算法、学校选择、器官交换与市场设计原则

第 11 讲：市场设计与匹配理论

本章导学

有些重要资源不能靠“谁出价高就给谁”来分配：学校名额、住院医职位、器官移植和部分平台匹配都受到法律、伦理或制度约束。本章讨论当价格机制退居次要位置时，如何用稳定性、策略性和可操作性来评价分配规则。

学完本章后，你应当能够：

定义匹配、阻塞对、稳定匹配和策略不可操纵性。
执行 Gale-Shapley 延迟接受算法，并解释学生最优或医院最优的含义。
分析学校选择、医生匹配和肾脏交换中的机制设计取舍。
理解市场厚度、拥堵控制和安全性为什么是市场设计的实践原则。

常见考查会给出偏好表，要求你运行算法、判断匹配是否稳定，或比较不同提议方下的结果。答题时要一步步记录暂时接受和拒绝过程，否则很容易在算法细节上出错。

本章延续第 8 章的机制设计思想，也回应第 10 章中的非价格配置问题。学完后再进入第 12 章，会更容易理解数字平台为什么既是市场，也是被设计出来的制度。

经济动机 (Economic Motivation)

在许多市场中，价格并不是唯一的分配机制，甚至不起主要作用：

学校选择：学生如何被分配到学校？（不能按价格）
医生-医院匹配：实习医生如何匹配到医院？
器官捐赠：肾脏捐赠者和患者如何配对？（禁止买卖）
婚姻市场：谁和谁结婚？（文化、道德约束）

这些都是匹配市场 (Matching Markets) 的例子。特点：

双边匹配：两组参与者相互选择
无价格或价格受限：道德、法律、实践原因
偏好异质：不同参与者有不同偏好
稳定性重要：不稳定的匹配会自行瓦解

市场设计 (Market Design) 将经济理论（博弈论、机制设计）应用于解决现实世界中的匹配问题，旨在创造更有效、公平、简单的市场。

诺贝尔奖认可

2012年：Alvin Roth 和 Lloyd Shapley
- Shapley：稳定匹配理论（1962）
- Roth：应用于医生匹配、学校选择、器官交换

一、稳定匹配问题 (Stable Matching Problem)

1.1 问题设定

稳定婚姻问题 (Stable Marriage Problem, Gale & Shapley 1962)：

$N$ 个男性： $M = \{m_1, m_2, \ldots, m_N\}$
$N$ 个女性： $W = \{w_1, w_2, \ldots, w_N\}$
每个男性有对所有女性的严格偏好排序
每个女性有对所有男性的严格偏好排序

目标：找到一个匹配 $\mu$ ，即男性和女性之间的一一对应。

匹配 $\mu$ ：

$\mu(m_i) = w_j$ 表示 $m_i$ 匹配到 $w_j$
$\mu(w_j) = m_i$ 表示 $w_j$ 匹配到 $m_i$
每个人都被匹配（一夫一妻制）

1.2 稳定性概念

阻塞对 (Blocking Pair)：一对 $(m_i, w_j)$ 是阻塞对，如果：

$m_i$ 偏好 $w_j$ 超过其当前配偶 $\mu(m_i)$
$w_j$ 偏好 $m_i$ 超过其当前配偶 $\mu(w_j)$

即两人都愿意抛弃当前配偶而结合。

稳定匹配 (Stable Matching)：没有阻塞对的匹配。

为什么稳定性重要？

不稳定的匹配会瓦解（当事人自行重新匹配）
实践中：医生跳槽、学生转学
稳定匹配是"自我实施"的均衡

1.3 示例

偏好表（ $m_1, m_2$ 是男性， $w_1, w_2$ 是女性）：

男性偏好（从左到右偏好递减）：

$m_1: w_1 \succ w_2$
$m_2: w_2 \succ w_1$

女性偏好：

$w_1: m_2 \succ m_1$
$w_2: m_1 \succ m_2$

候选匹配1： $\mu_1 = \{(m_1, w_1), (m_2, w_2)\}$

检查 $(m_1, w_2)$ ： $m_1$ 偏好 $w_1$ over $w_2$ ✗
检查 $(m_2, w_1)$ ： $m_2$ 偏好 $w_2$ over $w_1$ ✗
无阻塞对 → 稳定

候选匹配2： $\mu_2 = \{(m_1, w_2), (m_2, w_1)\}$

检查 $(m_1, w_1)$ $(m_{1}, w_{1})$ ：
- $m_1$ 偏好 $w_1$ over $w_2$ ✓
- $w_1$ 偏好 $m_2$ over $m_1$ ✗
- 不是阻塞对
检查 $(m_2, w_2)$ $(m_{2}, w_{2})$ ：
- $m_2$ 偏好 $w_2$ over $w_1$ ✓
- $w_2$ 偏好 $m_1$ over $m_2$ ✗
- 不是阻塞对
无阻塞对 → 稳定

结论：两个匹配都稳定！（一般情况下可能有多个稳定匹配）

二、Gale-Shapley算法 (Deferred Acceptance Algorithm)

2.1 算法描述

男性求婚版本 (Male-Proposing DA)：

初始化：所有人都未匹配
while 存在未匹配的男性 m:
    m 向他偏好列表中尚未拒绝他的最偏好女性 w 求婚
    if w 当前未匹配:
        w 暂时接受 m
    else:
        设当前持有者为 m'
        if w 偏好 m over m':
            w 拒绝 m'，暂时接受 m
            m' 变为未匹配
        else:
            w 拒绝 m
返回：最终的匹配

关键特征：

延迟接受：女性暂时接受，但可能后续拒绝
单调性：女性的匹配对象只会越来越好
男性降级：被拒绝的男性向次优选择求婚

2.2 算法执行示例

3男3女的例子：

男性偏好：

$m_1: w_2 \succ w_1 \succ w_3$
$m_2: w_1 \succ w_2 \succ w_3$
$m_3: w_1 \succ w_2 \succ w_3$

女性偏好：

$w_1: m_2 \succ m_3 \succ m_1$
$w_2: m_1 \succ m_2 \succ m_3$
$w_3: m_1 \succ m_2 \succ m_3$

第1轮：

$m_1 \to w_2$ ： $w_2$ 接受（当前最优）
$m_2 \to w_1$ ： $w_1$ 接受
$m_3 \to w_1$ ： $w_1$ 比较 $m_2$ vs. $m_3$ ，偏好 $m_2$ ，拒绝 $m_3$

当前匹配： $(m_1, w_2), (m_2, w_1)$ ， $m_3$ 未匹配

第2轮：

$m_3$ 向次优 $w_2$ 求婚
$w_2$ 比较 $m_1$ vs. $m_3$ ，偏好 $m_1$ ，拒绝 $m_3$

当前匹配： $(m_1, w_2), (m_2, w_1)$ ， $m_3$ 未匹配

第3轮：

$m_3$ 向再次优 $w_3$ 求婚
$w_3$ 接受（当前未匹配）

最终匹配： $\mu = \{(m_1, w_2), (m_2, w_1), (m_3, w_3)\}$

2.3 算法的性质

定理1（终止性）：算法在有限步内终止。

证明：

每轮至少有一个新的拒绝
每个男性最多被每个女性拒绝一次
最多 $N^2$ 次拒绝
因此算法必然终止

定理2（稳定性）：算法产生的匹配是稳定的。

证明（反证法）：假设存在阻塞对 $(m, w)$ ，即：

$m$ 偏好 $w$ over $\mu(m)$
$w$ 偏好 $m$ over $\mu(w)$

由于算法中 $m$ 按偏好顺序求婚：

如果 $m$ 偏好 $w$ over $\mu(m)$ ，则 $m$ 一定在求婚 $\mu(m)$ 之前向 $w$ 求过婚
那么为什么 $m$ 最终没有和 $w$ 匹配？

情况1： $w$ 当时拒绝了 $m$

说明 $w$ 当时已有更好的持有者 $m'$ （ $w$ 偏好 $m'$ over $m$ ）
由于女性的持有者只会越来越好， $\mu(w)$ 至少和 $m'$ 一样好
因此 $w$ 偏好 $\mu(w)$ over $m$ ，矛盾！

情况2： $w$ 当时接受了 $m$ 但后来换人

说明后来有更好的 $m''$ 求婚（ $w$ 偏好 $m''$ over $m$ ）
同样， $\mu(w)$ 至少和 $m''$ 一样好
因此 $w$ 偏好 $\mu(w)$ over $m$ ，矛盾！

结论：不存在阻塞对，匹配稳定。

定理3（男性最优）：男性求婚版本产生的稳定匹配是所有稳定匹配中对所有男性最优的。

证明思路：

定义"可行"女性：在某个稳定匹配中能匹配到该男性的女性
算法保证每个男性得到他的最优可行女性
反过来，女性得到她的最差可行男性（女性悲观）

对称性：女性求婚版本产生对所有女性最优的稳定匹配。

2.4 复杂度

时间复杂度： $O(N^2)$

最多 $N^2$ 次求婚
每次求婚需要 $O(1)$ 时间（假设偏好表已构建）

空间复杂度： $O(N^2)$ （存储偏好表）

三、多对一匹配：医院-医生问题 (Many-to-One Matching)

3.1 问题设定

医院-医生匹配 (Hospital-Resident Problem)：

$M$ 个医院，每个医院 $h$ 有配额 $q_h$ （可接受多个医生）
$N$ 个医生，每个医生只能匹配一个医院
双方都有偏好排序

匹配 $\mu$ ：

$\mu(d)$ ：医生 $d$ 匹配到的医院（或失业）
$\mu(h)$ ：医院 $h$ 匹配到的医生集合， $|\mu(h)| \leq q_h$

阻塞对： $(d, h)$ 是阻塞对，如果：

$d$ 偏好 $h$ over $\mu(d)$
且以下之一成立：
- $|\mu(h)| < q_h$ （医院有空位）
- 存在 $d' \in \mu(h)$ 使得 $h$ 偏好 $d$ over $d'$

3.2 DA算法推广

医生求婚版本：

医生向医院求婚
医院持有最优的 $q_h$ 个医生，拒绝其余
被拒绝的医生向次优医院求婚

性质：

算法终止且产生稳定匹配
对医生最优（对医院悲观）

3.3 实际应用：NRMP

National Resident Matching Program (美国医生匹配)：

历史：

1950年代前：混乱，医院提前抢人，医生毁约
1952年：引入集中匹配
1984年：Roth证明NRMP使用的算法等价于DA算法
1990年代：改革，加入夫妇匹配、优先级等复杂约束

成功原因：

稳定性 → 减少毁约
透明性 → 参与者信任
适应性 → 不断改进

四、学校选择机制 (School Choice)

4.1 问题背景

传统机制（波士顿、纽约等）：

学生提交偏好排序
学校按"接近性"（如家庭住址）或先到先得分配

问题：

策略性：学生不能真实报告偏好
不公平：信息不对称，有经验的家长占优
不稳定：存在阻塞对

4.2 学生最优稳定机制 (Student-Optimal Stable Mechanism, SOSM)

机制：DA算法，学生求婚

优点：

激励相容：真实报告偏好是优势策略（在单方面偏好下）
稳定：无阻塞对
学生最优：所有稳定匹配中学生最满意

改革实例：

波士顿 (2005)：

旧机制：立即接受算法 → 策略性报告
新机制：SOSM
结果：更多学生报告真实第一志愿

纽约 (2003)：

高中匹配系统改革
参与学校从17个增加到500+
学生满意度大幅提升

4.3 优先级设计

关键问题：学校如何排序学生？

常见优先级规则：

兄弟姐妹优先：有兄弟姐妹在该校的学生优先
步行距离：居住地离学校近的优先
抽签：随机决定

权衡：

公平性 vs. 效率
社区稳定 vs. 择校自由

五、器官交换 (Kidney Exchange)

5.1 问题设定

背景：

肾脏移植需求远超供给
很多患者有愿意捐赠的亲友，但血型/组织不兼容

解决方案：配对捐赠 (Paired Donation)

患者A的捐赠者 → 患者B
患者B的捐赠者 → 患者A

挑战：

两对以上的循环交换（3对、4对）
物流复杂性（同时手术）
激励相容（如何防止捐赠者反悔？）

5.2 顶级交易循环算法 (Top Trading Cycles, TTC)

Shapley-Scarf (1974) 房屋交换问题的推广：

算法：

while 存在未匹配的对:
    每对指向其最偏好的未匹配对
    找到所有循环（A → B → C → A）
    执行循环中的交换
    移除已匹配的对

性质：

Pareto有效
激励相容（真实报告偏好是优势策略）
策略简单（指向最优）

5.3 实际系统

New England Program for Kidney Exchange (2005)：

Roth等人设计
整合多个医院
允许3-way交换

全国性网络：

UNOS（美国）
NHS（英国）

成果：

大幅增加移植数量
提高匹配质量（更好的组织兼容性）

六、市场设计的原则 (Market Design Principles)

6.1 市场厚度 (Thickness)

定义：有足够多的参与者同时存在于市场中

问题：

市场太薄 → 难以找到好匹配
市场分散（时间/空间）→ 效率低

解决：

集中化：统一平台（如NRMP）
时间集中：统一时间点（如高考志愿填报）

6.2 避免拥堵 (Congestion)

定义：市场处理速度快，不让参与者等待

问题：

算法太慢 → 参与者绕过机制
信息过载 → 决策质量下降

解决：

限制排名长度（如NRMP限制12个）
高效算法（DA是 $O(N^2)$ ，可接受）

6.3 安全性 (Safety)

定义：参与者愿意真实报告偏好

问题：

策略性报告 → 低效率
复杂策略 → 不公平（有经验者占优）

解决：

激励相容机制（DA、TTC）
简单明了的规则

6.4 Roth的市场设计失败案例

英国肾脏交换（早期）：

设计复杂，难以理解
医院不信任 → 参与率低

加州大学招生：

时间分散 → 提前抢人
缺乏集中机制

教训：理论正确不够，还需考虑实践约束和参与者心理。

七、前沿话题 (Advanced Topics)

7.0 论文精读：从匹配机制到平台治理

市场设计的 fundamental 不是“写一个算法把双方配起来”，而是设计一套规则，使市场足够厚、参与者愿意进入、策略行为不至于毁掉结果，并且匹配结果能被参与者接受。DA、TTC、肾脏交换和学校选择都围绕这几个标准展开。

数字平台把这些标准放进了一个更复杂的环境。平台不仅决定“谁和谁匹配”，还决定谁先被看见、信息披露到什么程度、评价如何影响未来机会、佣金和补贴如何改变参与者激励。用机制设计语言写，可以把平台规则看作：

\text{outcome}=M(\text{preferences},\text{information},\text{ranking rule},\text{prices},\text{reputation}).

这比传统匹配多了几个变量。学校选择中，学生提交偏好列表，机制给出学校；外卖平台中，消费者看到的商家列表本身已经被排序规则加工过，商家的“偏好”也会被佣金、配送费、流量和评分影响。

读平台经济论文时，可以把 fundamental 和前沿问题一一对应：

市场设计基础问题	平台里的对应问题	读论文时要看
厚度	是否有足够买家和卖家同时参与	平台补贴、准入规则和多归属是否影响参与。
拥堵	参与者太多时如何筛选和排序	搜索排序、推荐系统和默认展示是否改变可见性。
激励相容	参与者是否愿意真实报告偏好或质量	评分操纵、刷单、策略性定价和虚假披露。
安全与信任	参与者是否相信机制可执行	申诉、处罚、评价纠错和数据透明度。

Martin (2024, DOI: 10.1111/1756-2171.12485) 关于市场透明度和消费者搜索的研究，可以这样放进本章：传统直觉常以为信息越透明越好，但市场设计会问更细的问题：披露哪些信息、以什么顺序披露、消费者是否真的处理得了这些信息、卖家会不会因为披露规则改变价格。它对应的是本章的“信息结构设计”，不是一句普通的市场背景。

Wessel et al. (2025, DOI: 10.1080/07421222.2025.2487315) 讨论生成式 AI 对数字平台价值创造的影响，也可以用同样方式读。生成式 AI 让平台从“匹配用户和内容/商家”进一步走向“替用户生成、筛选和代理行动”。这会改变偏好表达方式：过去用户显式搜索，现在用户可能让 AI agent 替自己筛选。市场设计问题随之变成：AI 代理代表谁的偏好？平台是否能操纵代理看到的选择集？推荐结果是否仍然可解释、可申诉？

Tang and Xu (2025, DOI: 10.1111/jems.12630) 则连接到市场势力。数字技术如果只是降低交易成本，平台会提高效率；但如果它同时让头部企业积累数据、优化定价、锁定用户，就可能提高进入壁垒和议价能力。把这篇论文放进市场设计章节，关键是理解：机制不只是分配效率问题，也是权力分配问题。

因此，平台治理论文的系统读法不是“用了算法，所以是前沿”。而是：

平台规则如何改变参与者看到的选择集；
平台规则如何改变参与者报告信息和采取行动的激励；
平台规则如何改变市场厚度、拥堵和信任；
平台规则是否把效率提升转化成某一方的市场势力。

这条线把 DA、TTC 这类经典机制和生成式 AI 平台接在一起：二者都在回答同一个问题，只是现代平台把信息、价格、排序、声誉和自动代理全部放进了机制本身。

7.1 匹配与契约 (Matching with Contracts)

推广：匹配不仅是"谁和谁"，还包括合同条款（如工资、工作时间）

应用：

医生匹配中加入薪资谈判
学校选择中加入课程包

7.2 动态匹配 (Dynamic Matching)

问题：参与者随时间到达和离开

应用：

器官移植（器官供给随机到达）
在线约会平台

挑战：

何时匹配vs.等待更好选项
厚度 vs. 及时性的权衡

7.3 匹配与货币 (Matching with Transfers)

放松无货币约束：

允许一方支付另一方
例：肾脏交换中允许"链"（利他捐赠启动）

理论：结合匹配理论和机制设计

7.4 在线平台的匹配

例子：

Airbnb：房东-房客匹配
Uber：司机-乘客匹配
在线约会：Tinder、探探

特点：

实时、大规模
机器学习辅助偏好推断
双边评级系统

近年前沿：平台规则和算法定价

在线平台不只是把买卖双方“放在一起”，它还会决定搜索排序、流量分配、佣金、处罚、推荐和价格展示方式。Chen et al. (2021) 把数字平台治理和设计放在同一个框架里讨论；Bonina et al. (2021) 进一步提醒我们，平台能不能带来发展收益，还取决于制度环境、参与者能力和治理规则。

算法定价让这个问题更复杂。Assad, Clark, Ershov & Xu (2023) 研究德国汽油市场时发现，算法定价会改变竞争过程；Johnson, Rhodes & Wildenbeest (2023) 则说明，当卖家使用定价算法时，平台如何分配需求会影响算法之间是否更容易形成类似合谋的结果。对本章来说，这些研究把“市场设计”从学校选择、医生匹配扩展到了日常数字市场。

平台设计问题	对应的市场设计语言	学生应关注的点
搜索排序和推荐	厚度、拥堵、信息披露	排名规则会改变谁被看见，也会改变参与者策略。
平台导流规则	机制约束、激励相容	规则不只是技术细节，可能抑制或放大算法合谋。
双边评价系统	信任、安全性、声誉机制	评分能降低信息不对称，也可能带来歧视和策略性评价。
平台治理	准入、处罚、申诉和数据权利	一个市场能否长期运行，取决于参与者是否相信规则。

直觉总结 (Intuitive Summary)

匹配理论的核心洞见

稳定性是关键
- 不稳定的匹配会瓦解
- 稳定匹配作为均衡概念
延迟接受的智慧
- 不立即决定 → 收集更多信息
- 女性"待价而沽" → 持有最优
求婚方占优
- DA算法的不对称性
- 设计时选择哪方求婚很重要
激励相容的价值
- 真实报告 → 简化决策、提高参与
- 不是所有机制都激励相容

匹配机制比较

机制	稳定性	激励相容	效率	应用
DA (男求婚)	✓	✓*	男性最优稳定	医生匹配
DA (女求婚)	✓	✓*	女性最优稳定	学校选择
TTC	✗	✓	Pareto有效	器官交换、学校选择
立即接受	✗	✗	低	旧波士顿机制
Serial Dictatorship	✗	✓	独裁者最优	宿舍分配

*在单方面偏好或特定条件下

理论 vs. 实践

理论提供：

稳定性概念
算法保证
性质分析

实践需要：

简单易懂
适应约束（如夫妇匹配）
获得参与者信任

成功案例：理论与实践紧密结合（如Roth的工作）

文献导读 (Literature Guide)

奠基性论文：

Gale, D., & Shapley, L. (1962). "College Admissions and the Stability of Marriage." American Mathematical Monthly.
Shapley, L., & Scarf, H. (1974). "On Cores and Indivisibility." Journal of Mathematical Economics. (TTC)
Roth, A. (1984). "The Evolution of the Labor Market for Medical Interns and Residents." JPE.

应用文献：

Abdulkadiroğlu, A., & Sönmez, T. (2003). "School Choice: A Mechanism Design Approach." AER.
Roth, A., Sönmez, T., & Ünver, M. (2004). "Kidney Exchange." QJE.
Pathak, P., & Sönmez, T. (2008). "Leveling the Playing Field: Sincere and Sophisticated Players in the Boston Mechanism." AER.

综述：

Roth, A. (2008). "Deferred Acceptance Algorithms: History, Theory, Practice, and Open Questions." International Journal of Game Theory.
Sönmez, T., & Ünver, M. (2011). "Matching, Allocation, and Exchange of Discrete Resources." In Handbook of Social Economics.

教科书/通俗读物：

Roth, A. (2015). Who Gets What — and Why: The New Economics of Matchmaking and Market Design. Houghton Mifflin. (畅销书)
Kojima, F., & Pathak, P. (2009). "Incentives and Stability in Large Two-Sided Matching Markets." AER.

前沿：