可调整个体优先级的双边匹配算法

Two-sided matching algorithm with adjustable individual priority

针对传统双边匹配算法单边占优、缺乏最低保障以及无法精细调控个体优先级等问题,提出了可通用于一对一、一对多、多对多双边匹配的WYS算法。WYS算法通过外生给定优先级,使得每个参与主体都有机会遍历自身偏好序中全部对象,从而显著提高匹配结果中最差群体的效用以及全体总效用,并能够对个体效用进行精确调控。随后按照诺奖得主Roth提出的"经济工程学"范式设计实验对WYS算法的性质进行了深入探讨,大量随机实验表明WYS算法匹配结果稳定,能够给予参与主体某种程度的最低保障,且不存在单边占优问题。WYS算法对于维持市场厚度、兼顾效率与公平有重要意义,拓宽了匹配理论的应用范围。

In view of the unilateral dominance problem, the lack of minimum guarantee and inability to adjust individual priority of traditional two-sided matching algorithms, this research proposes WYS algorithm which can be used in one-toone, one-to-many and many-to-many two-sided matching problems. WYS algorithm allows each participant to traverse all the objects in its preference list by exogenously giving priority, thusly the total utility and the utility of the worst group can both be improved. It also makes the individual regulation possible. Then in accordance with the Nobel Prize winner Roth＇s＂economic engineering＂, experiments are designed to explore the properties of WYS algorithm. The stability feature, non-unilateral dominance feature and participants＇ minimum guarantee of WYS algorithm are proven by numerous random experiments. WYS algorithm is of great significance in maintaining the thickness of market and balancing between efficiency and fairness, and also enriches the application scenario of matching theory.