无转移支付的匹配问题机制设计研究：理论建模与实验分析

This project studies many-to-one two-sided matching markets without transfers as our starting point. One side is endowed with cardinal preferences and the other side with ordinal ones, while preferences of both sides need not be strict. Using the idea of a competitive equilibrium from equal incomes (CEEI, Hylland and Zeckhauser (1979)), we propose a new mechanism, the Generalized CEEI (G-CEEI), in which students face different prices depending on how schools prefer them. We will try to investigate the properties of matchings that the new mechanism delivers. Desirably, we will try to prove that it always produces fair (justified-envy-free) and ex-ante efficient random assignments and stable deterministic ones with respect to stated preferences. More importantly, the incentive compatibility problem of participants is considered. An ideal prediction is that each student’s incentive to misreport vanishes when the market becomes large, given all others are truthful. Because it explicitly elicit cardinal preferences, our mechanism is particularly relevant in settings where one side of agents have similar ordinal preferences and the other side with weak preferences. It may significantly improve matching efficiency. We will also discuss its potentially broad applications in all kinds of economic and management problems, like school choice, marriage matching, organ donation matching, housing allocation, etc. Algorithms of realizing the solution(s) of G-CEEI in all kinds of situations will also be constructed and developed in lab. Meanwhile, the algorithms to evaluate the influence of sophisticated agents as well as the additional mechanisms to protect naive agents and to elicit cardinal preferences from unaware agents will also be investigated. Finally, a theory of G-CEEI with many-to-many two-sided matching with cardinal preferences on both sides will also be under construction.

本项目研究“无转移支付的匹配问题”，从一对一单边匹配中“均等收入竞争均衡”（CEEI）的虚拟市场机制出发，提出一个新的机制——广义CEEI（G-CEEI），使虚拟市场中的价格结构同时反映标的对购买者的偏好。我们将全面论证新机制的福利与行为性质。可预期的是，我们将证明它总是产生公平、稳定、事前Pareto有效的随机双边匹配。更重要地，我们研究参与者的激励相容问题，当市场规模越来越大时，汇报真实的偏好将是一个渐进的Nash均衡。G-CEEI在最近文献中说的“当匹配一方具有相同序数偏好而异质基数偏好、另一方具有弱偏好，则传统机制发挥不好”时尤为有用，它可以显著提高匹配效率。此外，我们探讨它在经济管理其他诸方面的潜在应用，以学生-学校择校录取匹配为一个典型例子展开，以及如保障房配置、器官捐赠匹配等等重要的国计民生资源配置管理问题。最后，我们还将用数值模拟计算实验的方法来研发G-CEEI的程序算法。

依据本项目的研究设计，项目组完成了重要的匹配机制市场设计工作（由一系列中英文已发表论文（含正式接受待刊（Forthcoming）、已投稿论文、工作论文组成），沿着诺贝尔奖获得者（2012）Alvin Roth的思路在没有自发市场的资源配置环境中进行市场设计研究其资源配置的效率。项目组在研究中指出，一个好的“虚拟市场”匹配机制所应具有的理想性质主要可以分为两类：机制的福利性质和机制的行为性质。福利性质主要包括“有效性”和“公平性”，行为性质也称可行性，主要包括“稳定性”和“抗操作性”（strategy-proofness）。匹配机制在国际学术界不仅理论研究受到重视，更重要的是对理论上推出机制在现实问题中的应用更是广泛存在。在公共管理领域和一些实务界，都可以应用各种理论机制所编制的匹配程序实际运作，实现有效的配置。项目组在研究中提出了一种新的G-CEEI（Generalized Competitive Equilibrium from Equal Incomes）机制（含优先权的配置问题研究：一个虚拟市场方法），不仅完成了G-CEEI机制之设立及其性质（福利与行为）的全部理论证明，并与世界上现行的、广受理论家推崇的匹配机制Deferred Acceptance Algorithm和Boston Mechanism所能得到的匹配结果（及其福利与行为性质）进行了充分的理论比较。在理论上，G-CEEI是一个更广义的机制，即当某些条件满足时，Deferred Acceptance Algorithm（又称Gale-Shapley Mechanism）和Boston Mechanism分别成为G-CEEI的特例；同时，由于G-CEEI是一种虚拟市场（Pseudo Market）机制，其能够实现市场均衡的价格组也能够比Deferred Acceptance Algorithm实现更多的配置。.除了理论设计、与传统机制的理论比较，其实际应用和测评也在开展、设计和进行中。实验阶段分为模拟实验和真人（subjects）参与的实验室实验。主攻模拟实验算法的项目组核心成员在项目研究中形成的重要管理类算法工作论文在国际SSCI顶级期刊Operations Research 接受匿名评审。与南京大学工程管理学院、社会科学计算实验中心的合作（程序算法手册、科普和网站建设）将在结项后继续展开。