针对基于偏好序的双边匹配问题,提出了具有抗操作和抗自亏性的匹配方法.具体地,首先,给出了稳定匹配方案和帕累托有效匹配方案的定义,以及匹配方法的抗操作性和抗自亏性定义.然后,通过借鉴经典G-S算法的思想,设计了确定最优匹配方案的IG-S算法.进一步地,讨论IG-S算法的特点,并证明了IG-S算法的合理性.最后,通过一个算例表明所提方法的可行性和有效性.
Abstract
With respect to the two-sided matching decision-making problem considering preference ordering, the matching method with the characteristics of strategy proof and self-deprecating proof is proposed. Firstly, the definitions of stable matching alternative, pareto efficient matching alternative, strategy proof and self-deprecating proof matching methods are given. Then, by referencing the idea of classical G-S algorithm, the IG-S (improved G-S) algorithm for determining the optimal matching alternatives is designed. Further, the characteristics in the proposed algorithm are discussed, and the rationales of proposed algorithm are proved. Finally, an example is given to illustrate the efficiency and feasibility of proposed method.
关键词
双边匹配 /
偏好序 /
IG-S算法 /
抗操作 /
抗自亏
{{custom_keyword}} /
Key words
two-sided matching /
preference ordering /
IG-S algorithm /
strategy proof /
self-deprecating proof
{{custom_keyword}} /
中图分类号：
N945
C934
{{custom_clc.code}}
({{custom_clc.text}})
{{custom_sec.title}}
{{custom_sec.title}}
{{custom_sec.content}}
参考文献
[1] Gale D, Shapley L. College admissions and the stability of marriage[J]. American Mathematical Monthly, 1962, 69(1):9-15.
[2] 蒋忠中, 樊治平, 汪定伟. 电子中介中具有模糊信息且需求不可分的多属性商品交易匹配问题[J]. 系统工程理论与实践, 2011, 31(12):2355-2366. Jiang Z Z, Fan Z P, Wang D W. Trade matching for multi-attribute exchanges with fuzzy information and indivisible demand in E-brokerage[J]. Systems Engineering-Theory & Practice, 2011, 31(12):2355-2366.
[3] 陈林, 朱卫平. 基于二手市场与理性预期的房地产市场机制研究[J]. 管理科学学报, 2011, 14(2):61-70. Chen L, Zhu W P. Research on real estate market mechanism in the second-hand market and rational expectation[J]. Journal of Management Sciences in China, 2011, 14(2):61-70.
[4] 李铭洋, 樊治平, 乐琦. 考虑稳定匹配条件的一对多双边匹配决策方法[J]. 系统工程学报, 2013, 28(4):454-463. Li M Y, Fan Z P, Yue Q. Decision analysis method for one-to-many two-sided matching considering stable matching condition[J]. Journal of Systems Engineering, 2013, 28(4):454-463.
[5] Biro P, Cechlarova K. Inapproximability of the kidney exchange problem[J]. Information Processing Letters, 2007, 101(5):199-202.
[6] 梁海明, 姜艳萍. 一种考虑弱偏好序信息的双边匹配决策方法[J]. 系统工程学报, 2014, 29(2):153-159. Liang H M, Jiang Y P. Method for two-sided matching decision-making based on the weak preference ordering information[J]. Journal of Systems Engineering, 2014, 29(2):153-159.
[7] Roth A E. Common and conflicting interests in two-sided matching market[J]. European Economic Review, 1985, 27(1):75-96.
[8] Yoshihisa M, Tatsuya H, Yoshiteru I. A network visualization of stable matching in the stable marriage problem[J]. Artificial Life and Robotics, 2011, 16:40-43.
[9] Pais J. Random matching in the college admissions problem[J]. Economic Theory, 2008, 35(1):99-116.
[10] Westkamp A. An analysis of the German university admissions system[J]. Economic Theory, 2013, 53(3):561-589.
[11] 樊治平, 乐琦. 基于完全偏好序信息的严格双边匹配方法[J]. 管理科学学报, 2014, 17(1):21-34. Fan Z P, Yue Q. Strict two-sided matching method based on complete preference ordinal information[J]. Journal of Management Sciences in China, 2014, 17(1):21-34.
[12] Boudreau J W, Knoblauch V. Preferences and the price of stability in matching markets[J]. Theory and Decision, 2013, 74(4):565-589.
[13] Echenique F, Lee S, Shum M, et al. The revealed preference theory of stable and extremal stable matchings[J]. Econometrica, 2013, 81(1):153-171.
[14] Khaled J, Jean-Marc M. An ordinal sorting method for group decision-making[J]. European Journal of Operational Research, 2007, 180:1272-1289.
[15] Balinski M, Sonmez T. A tale of two mechanisms:Student placement[J]. Journal of Economic Theory, 1999, 84(1):73-94.
[16] 魏立佳. 弱偏好序下的最优单边匹配算法设计[J]. 系统工程理论与实践, 2011, 31(9):1687-1695. Wei L J. Optimal mechanism design of weak preference orders one-sided matching[J]. Systems Engineering-Theory & Practice, 2011, 31(9):1687-1695.
[17] Abdulkadiroglu A, Sonmez T. House allocation with existing tenants[J]. Journal of Economic Theory, 1999, 88(2):233-260.
{{custom_fnGroup.title_cn}}
脚注
{{custom_fn.content}}
基金
国家自然科学基金(71271050,71571040);中国博士后科学基金(2015M572479)
{{custom_fund}}
PDF(600 KB)
