中国高考招生匹配市场中的算法设计及公平激励机制
|
摘要
用匹配博弈的方法,研究中国高考招生市场的算法设计及公平激励机制.基于高考招生程序,构建高考招生匹配算法,证明该算法的可行性.证明一个稳定匹配,可以由一个纳什均衡策略经高考招生算法生成,但反之不一定成立.证明一个稳定匹配一定是公平的,反之不一定成立.构建拒绝-接受算法,证明该算法是一个稳定的、策略防御的匹配机制,因而是一个公平的激励机制.
This paper, using matching game theoretic methods, studies the algorithm design and the fair incentive mechanism in Chinese college admissions market. Based on the admissions procedure, we design the Chinese college admissions algorithm, which we proved is feasible. We prove that every stable allocation can be produced by a Nash equilibrium, but not vice versa. We demonstrate the relationship between fairness and stability, and prove that stability implies fairness but not vice versa. Then we construct a(Gale and Shapley) deferred-acceptance algorithm in our market and show that it is both stable and strategy-proof. Therefore, it is a fair incentive mechanism.
This paper, using matching game theoretic methods, studies the algorithm design and the fair incentive mechanism in Chinese college admissions market. Based on the admissions procedure, we design the Chinese college admissions algorithm, which we proved is feasible. We prove that every stable allocation can be produced by a Nash equilibrium, but not vice versa. We demonstrate the relationship between fairness and stability, and prove that stability implies fairness but not vice versa. Then we construct a(Gale and Shapley) deferred-acceptance algorithm in our market and show that it is both stable and strategy-proof. Therefore, it is a fair incentive mechanism.
引文
[1]搜狐教育.“聚焦2016高考招生录取四大改革:让学生和学校的选择都宽广”[EB/OL].[2016-08-01].http://learning.sohu.com/20160609/n453756084.shtml.
[2] Gale D, Shapley L S. College admissions and the stability of marriage[J]. The American Mathematical Monthly, 1962, 69(1):9-15.
[3] Kojima F. Games of school choice under the Boston mechanism with general priority structures[J]. Social Choice Welfare, 2008, 31(3):357-365.
[4] Kelso A S, Crawford V P. Job matching, coalition formation, and gross substitutes[J]. Econometrica,1982, 50(6):1483-1504.
[5] Alkan A. A class of multipartner matching markets with a strong lattice structure[J]. Economic Theory, 2002, 19(4):737-746.
[6] Roth A, Elliot P. The effects of a change in the NRMP matching algorithm[J]. Journal of the American Medical Association,1997, 278(9):729-732.
[7] Roth A, Elliot P. The redesign of the matching market for American physicians:some engineering aspects of economic design[J]. American Economic Review, 1999, 89(4):748-780.
[8] Abdulkadiroglu P, Roth A E. The New York city high school match[J]. American Economic Review, 2005, 95(2):364-367.
[9] Abdulkadiroglu P, Roth A E, Sonmez T. Changing the Boston school choice mechanism[J].American Economic Review,2005, 95(2):368-371.
[10] Kumano T. Strategy-proofness and stability of the Boston mechanism:An almost impossibility result[J]. Journal of Public Economics, 2013, 105(1):23-29.
[11] Roth A. Stability and polarization of interests in job matching[J]. Econometrica, 1984, 52(1):47-57.
[12] Roth A. The economics of matching:stability and incentives[J]. Mathematics of Operations Research, 1982, 7(4):617-628.
[13] Akahoshi T. A necessary and sufficient condition for stable matching rules to be strategy-proof[J]. Social Choice Welfare, 2014, 43(2):683-702.
[14] Shapley L, Scarf H. On cores and indivisibility[J]. Journal of Mathematical Economics, 1974,1(1):23-37.
这充分体现了考生志愿在录取中的作用,即志愿具有优先级.在上一步骤中被接受的学生,在下一步骤中不会被拒绝,即便有更强大的竞争对手出现.正是这一政策隐含了该算法最终产生的不一定是个稳定匹配.
一所学校c的偏好P_c是相应偏好指:对任意的S′?S和任意的s_1,s_2∈S\S′,S′∪{s_1}P_cS′∪{s_2}?{s_1}P_c{s_2}, S′∪{s_1}P_cS′?{s_1}P_c?.
拒绝-接受算法与高考招生算法的实质不同正体现在这里:志愿优先级在这里被消散了.那些第一志愿是学校c且在步骤1′中被接受的学生,如果在这里的排名在q_c之后,将会在这一步骤被拒绝,因而在下一步骤将向他的第二志愿学校投档.
[2] Gale D, Shapley L S. College admissions and the stability of marriage[J]. The American Mathematical Monthly, 1962, 69(1):9-15.
[3] Kojima F. Games of school choice under the Boston mechanism with general priority structures[J]. Social Choice Welfare, 2008, 31(3):357-365.
[4] Kelso A S, Crawford V P. Job matching, coalition formation, and gross substitutes[J]. Econometrica,1982, 50(6):1483-1504.
[5] Alkan A. A class of multipartner matching markets with a strong lattice structure[J]. Economic Theory, 2002, 19(4):737-746.
[6] Roth A, Elliot P. The effects of a change in the NRMP matching algorithm[J]. Journal of the American Medical Association,1997, 278(9):729-732.
[7] Roth A, Elliot P. The redesign of the matching market for American physicians:some engineering aspects of economic design[J]. American Economic Review, 1999, 89(4):748-780.
[8] Abdulkadiroglu P, Roth A E. The New York city high school match[J]. American Economic Review, 2005, 95(2):364-367.
[9] Abdulkadiroglu P, Roth A E, Sonmez T. Changing the Boston school choice mechanism[J].American Economic Review,2005, 95(2):368-371.
[10] Kumano T. Strategy-proofness and stability of the Boston mechanism:An almost impossibility result[J]. Journal of Public Economics, 2013, 105(1):23-29.
[11] Roth A. Stability and polarization of interests in job matching[J]. Econometrica, 1984, 52(1):47-57.
[12] Roth A. The economics of matching:stability and incentives[J]. Mathematics of Operations Research, 1982, 7(4):617-628.
[13] Akahoshi T. A necessary and sufficient condition for stable matching rules to be strategy-proof[J]. Social Choice Welfare, 2014, 43(2):683-702.
[14] Shapley L, Scarf H. On cores and indivisibility[J]. Journal of Mathematical Economics, 1974,1(1):23-37.
这充分体现了考生志愿在录取中的作用,即志愿具有优先级.在上一步骤中被接受的学生,在下一步骤中不会被拒绝,即便有更强大的竞争对手出现.正是这一政策隐含了该算法最终产生的不一定是个稳定匹配.
一所学校c的偏好P_c是相应偏好指:对任意的S′?S和任意的s_1,s_2∈S\S′,S′∪{s_1}P_cS′∪{s_2}?{s_1}P_c{s_2}, S′∪{s_1}P_cS′?{s_1}P_c?.
拒绝-接受算法与高考招生算法的实质不同正体现在这里:志愿优先级在这里被消散了.那些第一志愿是学校c且在步骤1′中被接受的学生,如果在这里的排名在q_c之后,将会在这一步骤被拒绝,因而在下一步骤将向他的第二志愿学校投档.