可调整个体优先级的双边匹配算法
|
摘要
针对传统双边匹配算法单边占优、缺乏最低保障以及无法精细调控个体优先级等问题,提出了可通用于一对一、一对多、多对多双边匹配的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.
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.
引文
[1]魏立佳.从微观理论到社会实践--市场设计的最新进展综述[J].世界经济文汇,2013,56(3):89-104.
[2]Che Y K,Gale I L.Market versus non-market assignment of ownership,1328984[R].Rochester,NY:Social Science Research Network,2009.
[3]Roth A E.The economist as engineer:Game theory,experimentation,and computation as tools for design economics[J].Econometrica,2002,70(4):1341-1378.
[4]Roth A E,Peranson E.The redesign of the matching market for American physicians:Some engineering aspects of economic design[J].American Economic Review,1999,89(4):748-780.
[5]Milgrom P.Critical issues in the practice of market design[J].Economic Inquiry,2011,49(2):311-320.
[6]S?nmez T,ünver M U.Matching,allocation,and exchange of discrete resources[M]//Jess B,Jackson M O,Alberto B.Handbook of Social Economics.North Holland:Elsevier,2011:781-852.
[7]Budish E.Matching“versus”mechanism design[J].SIGecom Exchanges,2012,11(2):4-15.
[8]Gale D,Shapley L S.College admissions and the stability of marriage[J].The American Mathematical Monthly,1962,69(1):9-15.
[9]Roth A E.The economics of matching:Stability and incentives[J].Mathematics of Operations Research,1982,7(4):617-628.
[10]Klumpp T.Two-sided matching with spatially differentiated agents[J].Journal of Mathematical Economics,2009,45(5):376-390.
[11]Erdil A,Ergin H.Two-sided matching with indifferences[J].Journal of Economic Theory,2017,171(6):268-292.
[12]Castillo M,Dianat A.Truncation strategies in two-sided matching markets:Theory and experiment[J].Games and Economic Behavior,2016,98(4):180-196.
[13]Gharote M,Patil R,Lodha S,et al.Assignment of trainees to software project requirements:A stable matching based approach[J].Computers&Industrial Engineering,2015,87(9):228-237.
[14]Byun J,Jang S.Effective destination advertising:Matching effect between advertising language and destination type[J].Tourism Management,2015,50(5):31-40.
[15]Xu X,Wang C,Zeng Y,et al.Matching service providers and customers in two-sided dynamic markets[J].IFAC-Papers On Line,2015,48(3):2208-2213.
[16]Chen J,Song K.Two-sided matching in the loan market[J].International Journal of Industrial Organization,2013,31(2):145-152.
[17]Silveira R,Wright R.Venture capital:A model of search and bargaining[J].Review of Economic Dynamics,2016,19(1):232-246.
[18]Roth A E.Deferred acceptance algorithms:History,theory,practice,and open questions[J].International Journal of Game Theory,2008,36(3):537-569.
[19]Roth A E.The evolution of the labor market for medical interns and residents:A case study in game theory[J].Journal of Political Economy,1984,92(6):991-1016.
[20]Roth A E.What have we learned from market design?[J].The Economic Journal,2008,118(527):285-310.
[21]Itai A,Yash K,Jacob D L.Unbalanced random matching markets:The stark effect of competition[J].Journal of Political Economy,2016,125(1):69-98.
[22]李铭洋,樊治平,乐琦.考虑稳定匹配条件的一对多双边匹配决策方法[J].系统工程学报,2013,29(4):454-463.
[23]Kojima F,Pathak P A,Roth A E.Matching with couples:Stability and incentives in large markets[J].The Quarterly Journal of Economics,2013,128(4):1585-1632.
[2]Che Y K,Gale I L.Market versus non-market assignment of ownership,1328984[R].Rochester,NY:Social Science Research Network,2009.
[3]Roth A E.The economist as engineer:Game theory,experimentation,and computation as tools for design economics[J].Econometrica,2002,70(4):1341-1378.
[4]Roth A E,Peranson E.The redesign of the matching market for American physicians:Some engineering aspects of economic design[J].American Economic Review,1999,89(4):748-780.
[5]Milgrom P.Critical issues in the practice of market design[J].Economic Inquiry,2011,49(2):311-320.
[6]S?nmez T,ünver M U.Matching,allocation,and exchange of discrete resources[M]//Jess B,Jackson M O,Alberto B.Handbook of Social Economics.North Holland:Elsevier,2011:781-852.
[7]Budish E.Matching“versus”mechanism design[J].SIGecom Exchanges,2012,11(2):4-15.
[8]Gale D,Shapley L S.College admissions and the stability of marriage[J].The American Mathematical Monthly,1962,69(1):9-15.
[9]Roth A E.The economics of matching:Stability and incentives[J].Mathematics of Operations Research,1982,7(4):617-628.
[10]Klumpp T.Two-sided matching with spatially differentiated agents[J].Journal of Mathematical Economics,2009,45(5):376-390.
[11]Erdil A,Ergin H.Two-sided matching with indifferences[J].Journal of Economic Theory,2017,171(6):268-292.
[12]Castillo M,Dianat A.Truncation strategies in two-sided matching markets:Theory and experiment[J].Games and Economic Behavior,2016,98(4):180-196.
[13]Gharote M,Patil R,Lodha S,et al.Assignment of trainees to software project requirements:A stable matching based approach[J].Computers&Industrial Engineering,2015,87(9):228-237.
[14]Byun J,Jang S.Effective destination advertising:Matching effect between advertising language and destination type[J].Tourism Management,2015,50(5):31-40.
[15]Xu X,Wang C,Zeng Y,et al.Matching service providers and customers in two-sided dynamic markets[J].IFAC-Papers On Line,2015,48(3):2208-2213.
[16]Chen J,Song K.Two-sided matching in the loan market[J].International Journal of Industrial Organization,2013,31(2):145-152.
[17]Silveira R,Wright R.Venture capital:A model of search and bargaining[J].Review of Economic Dynamics,2016,19(1):232-246.
[18]Roth A E.Deferred acceptance algorithms:History,theory,practice,and open questions[J].International Journal of Game Theory,2008,36(3):537-569.
[19]Roth A E.The evolution of the labor market for medical interns and residents:A case study in game theory[J].Journal of Political Economy,1984,92(6):991-1016.
[20]Roth A E.What have we learned from market design?[J].The Economic Journal,2008,118(527):285-310.
[21]Itai A,Yash K,Jacob D L.Unbalanced random matching markets:The stark effect of competition[J].Journal of Political Economy,2016,125(1):69-98.
[22]李铭洋,樊治平,乐琦.考虑稳定匹配条件的一对多双边匹配决策方法[J].系统工程学报,2013,29(4):454-463.
[23]Kojima F,Pathak P A,Roth A E.Matching with couples:Stability and incentives in large markets[J].The Quarterly Journal of Economics,2013,128(4):1585-1632.