匹配理论

匹配理论 (Matching Theory)

匹配理论（Matching Theory）是市场设计（Market Design）的核心理论分支，研究如何在缺乏价格机制的双边或多边市场中，通过算法和制度设计实现资源的稳定、高效配置。其研究对象包括婚姻市场、劳动力市场、学校招生、器官移植配对等——这些市场的共同特征是：交易双方不可简单用货币定价，且交易必须建立在双方互选的基础上。匹配理论为阿尔文·罗思（Alvin Roth）和劳埃德·沙普利（Lloyd Shapley）赢得2012年诺贝尔经济学奖。

稳定匹配问题

匹配理论的起点是盖尔-沙普利（Gale-Shapley，1962）提出的稳定婚姻问题（Stable Marriage Problem）：设有 $n$ 位男性和 $n$ 位女性，每人都有一个严格排序的偏好列表（对异性的排名）。一个匹配（matching）是将男女配对的一一映射。如果一个匹配中存在一对男女，他们彼此对对方的偏好均高于各自当前的匹配对象，则这对男女构成阻塞对（Blocking Pair）。不存在任何阻塞对的匹配称为稳定匹配（Stable Matching）。

稳定性的核心直觉是：如果存在阻塞对，这两人会"私奔"破坏现有的匹配安排，因此不稳定的匹配缺乏自我执行的力量。稳定匹配概念超越了传统价格理论中瓦尔拉斯均衡的分析框架，为无价格市场的均衡分析奠定了微观基础。

盖尔和沙普利证明了一个关键定理：对于任意偏好分布，稳定匹配始终存在。他们通过构造性证明给出了寻找稳定匹配的算法。

延迟接受算法 (Deferred Acceptance Algorithm)

DA算法是匹配理论的核心算法，有两种对称的版本：

男性求婚版本

1. 每位男性向自己偏好列表中尚未拒绝过自己的排名最高的女性求婚。
2. 每位女性暂时接受当前求婚者中自己最偏好的一位，拒绝其余求婚者。若尚未收到任何求婚，则保持单身状态。
3. 被拒绝的男性在下一轮向偏好列表中下一位女性求婚。
4. 重复直至没有新的求婚发生。此时每位女性永久接受其当前持有的求婚者。

算法在至多 $n^2$ 轮内终止，终态匹配一定稳定。在男性求婚版本中，输出结果为男性最优稳定匹配（Men-Optimal Stable Matching）：每个男性获得的配偶在所有稳定匹配中是最好的，而每个女性获得的配偶是所有稳定匹配中最差的。对称地，女性求婚版本给出女性最优稳定匹配。

核心性质

策略防操纵性 (Strategy-Proofness)

在男性最优稳定匹配机制下，男性没有动机谎报自己的真实偏好：说真话是弱占优策略。但对女性而言，该机制不具备策略防操纵性（Dubins \& Freedman, 1981; Roth, 1982）。更一般地，不存在任何同时对所有参与者都策略防操纵且始终输出稳定匹配的机制——这一不可能性结果是匹配理论中与阿罗不可能定理类似的深刻结论。

偏远农村医院定理 (Rural Hospitals Theorem)

在多对一匹配（如医院-医生匹配）中，Roth (1986) 证明：所有稳定匹配中，各机构填补的岗位数完全相同，且未填补满的机构在所有稳定匹配中填补的岗位集合也相同。这意味着算法选择（是医生发起还是医院发起）不影响哪些机构招不满人，只影响谁去哪些机构。

对偶结构与格 (Lattice)

所有稳定匹配的集合在参与者的偏好偏序下形成一个分配格（Distributive Lattice），其中男性最优和女性最优稳定匹配分别构成格的上确界和下确界。这一代数结构意味着稳定匹配集合具有良好的数学性质：任意两个稳定匹配的"上并"和"下交"（相对于男性偏好）也是稳定匹配。

多对一匹配：大学录取模型

将稳定婚姻问题中的性别角色替换为大学录取或医院-医生匹配，即得到多对一匹配模型。每个大学（医院）有固定容量 $q_c$，可同时录取多名学生（医生）。

在多对一模型中，稳定匹配需同时满足：

• 个体理性（Individual Rationality）：没有参与者被匹配到不可接受的对方（即偏好低于单身的对象）。
• 无阻塞（No Blocking）：不存在一个学生-大学对，学生偏好该大学超过当前录取，且大学偏好该学生超过当前录取的某位学生（或大学有空位且该学生可接受）。

DA算法经适当调整后可直接应用于多对一匹配：机构在每轮保留偏好最高的至多 $q_c$ 名申请者，其余拒绝。

实际应用

匹配理论的应用已成为经济学直接改善社会福祉的典范：

1. NRMP（美国国家住院医师匹配计划）：自1950年代起用于匹配医学生与住院医师岗位。Roth在1990年代协助重新设计算法，采用学生-最优DA机制取代此前存在严重策略操纵问题的旧算法。
2. 择校系统（School Choice）：纽约、波士顿、巴黎等全球众多城市采用DA或其变体（如顶级交易循环机制，TTC）分配公立学校学位。这些系统的设计权衡了稳定性、效率与策略防操纵性。
3. 肾脏交换（Kidney Exchange）：在活体肾脏移植中，当捐赠者与受赠者因血型或组织型不兼容时，通过跨配对进行循环交换。匹配理论为构建多医院联网、考虑链条交换和非定向捐赠提供了算法基础。
4. 法庭与法官分配：部分国家将案件匹配给法官时使用基于偏好的匹配机制。

与一般均衡理论的对比

匹配理论与一般均衡理论在"配置效率"这一终极关切上完全一致，但在路径上各有侧重。一般均衡理论依赖于价格调整机制实现市场出清，而匹配理论则处理价格机制失灵（或不存在）的"无价格市场"——在这些市场中，交易的本质是互选而非买卖，配置的稳定性取代了帕累托效率成为核心规范性标准。然而两者之间存在深层联系：影子价格（对偶变量）在匹配问题中对应各参与者的匹配剩余，稳定匹配本质上是以参与者的偏好排序为约束条件的核（Core）分配——这是合作博弈论与匹配理论的交叉地带，也是沙普利在博弈论领域奠基性贡献的自然延伸。