弱偏好序下的最优单边匹配算法设计

被引：12

作者：

魏立佳

机构：

[1] 厦门大学王亚南经济研究院

来源：

系统工程理论与实践 | 2011年 / 31卷 / 09期

关键词：

弱优先序; 单边匹配; 算法设计; 高考录取;

D O I：

暂无

中图分类号：

O224 [最优化的数学理论];

学科分类号：

摘要：

传统的匹配算法假定学生偏好序是严格的,但在现实中匹配的学生一方很可能会具有弱偏好序,这时任意一种算法的双边匹配都不能满足稳定、抗操作和帕累托最优.在中国,高等学校录取的"平行志愿"录取方式是一个典型的单边匹配.因此论文将弱偏好序的匹配算法研究拓展到单边匹配领域,设计了"挤出"匹配算法,并证明该算法满足稳定、抗操作和帕累托最优的算法,且匹配后学生总效用最高.通过计算机算法模拟的方式,全志愿模拟录取证实"挤出"算法确实能显著改进匹配效率,且主要改善优先序排名较后的学生的效用;在两批次高考志愿录取模拟中,"挤出"算法使学生总效用最高,能同时保证"高分低就"率和"高分落榜"率最低.

引用

页码：1687 / 1695

页数：9

共 5 条

[1] 中国高考录取与博士生录取的机制设计
魏立佳
[J]. 经济学(季刊), 2010, 9 (01) : 349 - 362
[2] 高考录取机制的博弈分析
聂海峰
[J]. 经济学(季刊), 2007, (03) : 899 - 916
[3] Deferred acceptance algorithms: history, theory, practice, and open questions[J] . Alvin E. Roth.International Journal of Game Theory . 2008 (3)
[4] The Boston Public School match
Abdulkadiroglu, A
Pathak, PA
Roth, AE
Sönmez, T
[J]. AMERICAN ECONOMIC REVIEW, 2005, 95 (02) : 368 - 371
[5] A Tale of Two Mechanisms: Student Placement[J] . Journal of Economic Theory . 1999 (1)

← 1 →