市场机制设计理论及其在择校问题中的应用研究

In the markets of indivisible goods or markets without monetary transfers. such as the school choice market and the market for human organs, the decentralized mechanisms currently used in practice often have serious flaws such as lack of stability or efficiency. Market design is a field of research that designs central allocation mechanisms to replace the decentralized mechanisms and fix their flaws. This project focuses on the two fundamental mechanisms in market design, namely, the Deferred acceptance algorithm and the Top trading cycles mechanism, and.studies their application in school choice. To be specific, we study: (1) How to improve students' efficiency with minimal violation of stability? and (2) How to improve the stability of the top trading cycles mechanism.

在不可分物品的交易市场或者不能使用货币交易的市场中（例如学生与学校的匹配市场以及人体器官交换的市场），现实中的分散化市场机制往往存在着分配结果不稳定以及缺乏分配效率等缺陷。市场机制设计的意义在于使用集中化的分配机制来取代分散化的市场机制，以克服其缺陷。本项目的研究主要关注市场机制设计中的两大支柱算法，延迟接受算法（Deferred acceptance algorithm）和首位交换环算法（Top trading cycles mechanism），以研究它们在择校问题中的应用。我们具体研究：（1）在择校问题中，如何在提升学生录取的帕累托效率的同时减少稳定性的损失；（2）如何在不损害学生帕累托效率的前提下提升首位交换环算法的稳定性。

市场机制设计的核心在于使用集中化的分配机制来取代分散化的市场机制，以克服其缺陷。我们主要以择校问题为典型作为开展研究的基本框架。择校问题研究如何将各级学校的名额或座位分配给学生，以实现效率与公平等各方面的社会目标。..给定学生的偏好和学校对学生的优先权排序，我们希望好的录取机制给出的匹配结果满足：（1）稳定性。在机制给出的匹配结果中，不能出现有学生喜欢另外一个学校多过目前匹配到的学校，而同时该学校又将这个学生排在优先于目前录取的某个学生。如果这样的情况存在，那么这对学生-学校就可以互相匹配到一起从而使得机制给出的匹配结果无法实现；（2）帕累托效率。在机制的匹配结果中不应出现有学生可以通过互相交换自己所录取到的学校的名额而互相变得更好。如果这样的交换机会存在，那么该机制就不是帕累托有效的，从而可以进行帕累托改进。同时，录取机制还应该满足策略防范性，亦即在任何情况下学生都不能通过采取谎报志愿的策略行为使得自己录取到更好的学校。..然而，录取机制的稳定性和帕累托有效性是不兼容的。我们的第一项主要工作是提出一种合理的与帕累托有效性兼容的弱稳定性的概念。首先，如果一对学生和学校在某个匹配方案下互相喜欢从而想要重新匹配到一起，那么我们将它们称为一个潜在重配对。具体地，我们说一个匹配方案是弱稳定的，如果将该匹配下任何一个潜在重配对重新匹配到一起都必然产生该匹配方案所没有的新的潜在重配对。我们的研究通过刻画这一概念的完整性质，揭示了双边匹配问题中的深层结构。..我们的第二项主要工作是为帕累托有效且稳定的录取机制，即基于非循环优先权结构的延迟接受算法，提供了理论上的剖析。具体地，我们提出一种新的概念，称为首位公平集，并证明在非循环优先权结构下，迭代地将首位公平集中的学生录取到他们最喜欢的学校的机制等价于延迟接受算法。该工作完美地揭示出了帕累托有效的延迟接受算法背后所隐藏的迭代结构，从而使得我们可以直接地将这些机制与经典的基于首位交换环的帕累托有效机制进行直接的对比。