带约束条件的匹配理论以及与高考录取制度改革有关的几个问题

In the past two decades, matching theory and market design have made significant progress and have been successfully applied in many real markets, including the reform for public school admission mechanisms in big cities of US like Boston and New York. Matching with constraints is a current hot topic in matching theory, in which the constraints are imposed on the quotas of schools for different types of students. There are subtle difference between the students proposing deferred acceptance mechanisms for matching with constraints and classical matching in terms of stability, Pareto efficiency, and strategy-proofness. The Gaokao admission problem of China is actually a school choice problem with constraints, since in the so-called “special admission plans”, some fixed proportion of quota in some universities are used to admit certain type of students. Taking into account the ongoing reform of the Gaokao admission mechanism (merging the admission batch, and gradually increasing the number of parallel Zhiyuan etc), this project aims to study Gaokao admission problem with constraints from the perspective of the matching theory and market design. We also plan to study some related theoretical problems in matching with constraints.

近二十年来，匹配理论以及市场设计理论取得了重要进展并且已经在包括美国多个大城市的公立学校录取机制改革等诸多真实市场中得到了成功的应用。具有约束条件的匹配理论是最近的一个研究热点。择校问题中约束条件是指学校在招生计划中对各个类型的学生名额加有上限或者下限。在带约束条件的匹配理论中，经典采用的学生一方提交申请的延迟接受机制在稳定性，帕累托效率，以及抗操纵性上存在诸多问题。我国的高考录取中由于存在一定比例的“专项招生计划”，这类招生计划只能用来招收部分满足条件的考生，因此我国的高考问题其实是带约束条件的择校问题。考虑到我国目前正在推进的高考录取制度改革 (合并录取批次，逐步增加平行志愿数目等)，本项目计划从匹配理论和市场设计的角度研究带约束条件的高考问题如何受到高考录取制度改革的影响，还计划对带约束条件的匹配问题中的其他几个理论问题开展深入研究。

在开展本项目研究期间，项目申请人和合作者一道，对市场设计（Market Design）理论中一类重要的问题，基于优先权结构的物品分配问题（Priority-Based Allocation Problems）进行了深入研究，并取得了若干原创性进展。一般的基于优先权物品分配问题模型如下：需要将有限个不可分物品分配给有限个人，每个人需要至多一个物品，且一个物品至多分配给至多一个人；分配过程中不允许有转移支付（Monetary Transfer）；所有人在每个物品上有一个优先权排序（严格或者不严格排序），每个人对所有物品上的偏好都是严格的。本项目取得研究成果包括五篇研究论文，其中发表论文两篇（一篇发表于经济学理论顶尖期刊Journal of Economic Theory，一篇发表于经济学理论知名期刊Economic Theory），还有两篇工作论文正在投稿中，一篇即将完稿。..在择校问题中，所有学校对所有学生的排序也都是严格的。在这类理论问题乃至在整个市场设计理论中，Gale 和Shapley的延迟接受（Deferred Acceptance，DA）算法是最重要的匹配机制。在本项目成果的三篇文章中，包括两篇已发表的论文以及一篇工作论文中，我们在择校问题理论中提出了一些新的概念，例如顶端公平集合（Top Fair Set）、弱稳定（Weakly Stable）匹配、以及核（Core）等，这些新的概念对我们理解择校问题中具有良好性质的匹配集合的结构，以及对理解Pareto有效的DA机制，以及其衍生的EADA(Efficiency-Adjusted DA)机制都具有重要的理论意义。..在轮岗问题中，我们有两篇工作论文。在一篇工作论文中，我们提出了两个具有稳定的、条件Pareto最优的（Constrained Efficient）的算法。这两个算法在一类特殊的轮岗问题中是等价的，并且也等价于Yu-Zhang（2002）中的BTTC算法。我们的第二篇工作论文证明了在具有三个人的TAU（Task Allocation with Unqualified agents）优先权结构中，存在一个稳定的、条件Pareto最优的、防策略操控的机制。