9 1 2009 10 ( ) China Eco nomic Quarterly Vol19, No11 October, 2009 3,,,,,,,,, 2008,, 3, 4, 3 :, 361005 ; : (0592) 2573015 ; E2mail :wendyeye @gmail. com,,
350 ( ) 9,,,,,,,,,,, :,,,,,,, ( Ergin and Sgnmez, 2006) Gale and Shapley (1962), Gale2Shapley,, Gale2Shapley ( (2007) ) Dubins and Freedman (1981) Gale2Shapley, Rot h ( 1982a, 1982b) Balinski and Sgnmez (1999) Abdulkadiroglu and Sgnmez (2003) Gale2Shapley Rot h (1984) Gale2Shap2 ley,,,,, Gale2Shapley Gale2Shapley, Sha2 pley and Scarf (1974) Roth and Postlewaite (1977)
1 : 351 ( Galeπs Top trading cycles) 20 90,,, Abdulkadiroglu and Sgnmez (2003),, Abdulkadiroglu 2005 1, Abdulkad2 iroglu ( Abdulkadiroglu, Pat hak, Rot h and Sgnmez, 2006) (Abdulkadiroglu, Pat hak and Rot h, 2008) Chen and Sgnmez (2006) Gale2Shap2 ley,, Gale2Shapley Zhou (1990) (2007),, ( ) : S = = { S1, S2, S3,, S m } ; C = = { C1, C2, C3,, Cn} ; Q = = { qc 1, qc 2, qc 3,, qc n } ; TC i = Ci S = { T C i ( S1 ), TC i ( S2 ), TC i ( S3 ),, TC i ( S m) } ; P = = { PS 1, PS 2, PS 3,, PS m }, PS k S k C { C0 }, C0 1 : S C { C0 }, ΠCi, - 1 ( Ci) qc i 1 Abdulkadiroglu Sgnmez, ( school choice problem) Ab2 dulkadiroglu Sgnmez,, ;,,,
352 ( ) 9 2 M : P 3 ( fair ) 2 : ΠS1, S2, Ci = ( S1 ), ( S1 ) PS 2 ( S2 ) ] TC i ( S1 ) > TC i ( S2 ) : S1 S2, S2 S1 Ci, Ci S 1 S2 4 (non2wasteful) : ΠS k, ΠCi, Ci PS k ( S k ) ] - 1 ( Ci) = qc i : S k Ci, S k Ci, Ci q C i 5 (individually rational) : ΠS k, ( S k ) RS k C0 ; A RS k B Ζ A PS k B A = B : S k, 6 M ( strategy2proof ) : Π PS k, ΠS k, Π P S k, M ( P) RS k M ( P S k, P - S k ), M ( P, P - S k ) S k :, 7 ( Pareto efficient) : ΠS k, ( S k) RS k ( S k), ϖ S l, ( S l) PS l ( S l ) :, ( school admission problem) : M,? ( ), Gale2Shapley : Gale2Shapley,,, S k 2 (2007),, 3 4
1 : 353 Gale2Shapley, n m, qc i,,,,,, n, ( ), m,,, A,, ( ) 3, (2007),,,,,,,,,,,,,,, ( 105 %),,,, n i = 1 3,,,
354 ( ) 9,,,, 1 A A E A C, B B E B C, A E P S B E P S B C P S A E, A, A,,,, F ( ), f ( ) i, N ( N 1), <( i ) ( < ( ) > 0, i i + 1 ), [ a, b],, <( i ) a b,, a, : U = E<( i ) = <( a) [ F( 1 ) - F( a) ] + <( 1 ) [ F( 2 ) - F( 1 ) ] + + <( N - 1 ) [ F( b) - F( N ) ]. 1, N, A N N, N + 1 B N + 1, B N + 1 A N N + 1 B N + 1 N + 1, A N,, 2 N, [ a, b] N, U,,,,, :,,, Gale2Shapley,
1 : 355,,,,,,,,,,,,,,, Gale2Shapley,,, Gale2Shapley,, 1 1 Gale2Shapley,, ( ) ( ) Gale2Shapley, ( 4 ) :, : (, ) g ( S k ) : S k CS k = { Ci, Cj,, Ck } 5, 4, ( ) ( Rot h,1985) 5,,,,,, ( )
356 ( ) 9 ( S k) CS k ΠS k, ΠCi, TC i ( S k ) TC i ( S q Ci ), C CS k, S q Ci Ci q C i : OC = = { O 1 C i, O 2 C j,, O n C k }, O l C Ci i l, O k C j < O l C i (1 k < l n) Cj Ci, (,, ), C0 ( ), :, O 1 C i q C i,,, O 2 C j q C j, ; Cj O 2 C j,, qc j, n, O n C k q C k, ; Ck O n C k,, qc k, n, 3 M, ϖ S k S l, Ci Cj CS k, OC j < OC i, Ci P S k C j, Cj P S l ( S l), M 4 M,,,,,,,,,,, ( ),,,
1 : 357,,, 6 7, : P = { PS 1, PS 2, PS 3,, PS m }, P - S 1 = P - S 2 = = P - S m, P - S C0, C i i :, C 1 qc 1,,, C 2 qc 2, ; C 2,, qc 2, n, C n q C n, n ; C n,, qc n, 5 M 6 M, :,,,,,,, 6, 7 : ( ) ( )
358 ( ) 9?,,, : ;, ;, : :,,,,,,, ( ) A (1) Gale2Shapley : :, C T c qc, :, C, Tc qc k : k, C k, Tc qc k,, (2) : :,, ( S1 C1 S2 C2 S1 ), 1,
1 : 359 k :, 1,, (3) : :,, k : k,, k (4) : :,,, ;,, n k : k,,, ;,, n B 1 (1) 2, 1, 2 1 : U 2 = <( a) [ F( 1 ) - F( a) ] + <( 1 ) [ F( b) - F( 1 ) ] ; U 1 = <( a) [ F( b) - F( a) ]. : U 2 (2) - U 1 = <( a) [ F( 1 ) - F( a) ] + <( 1 ) [ F( b) - F( 1 ) ] - <( a) [ F( b) - F( a) ] = [ F( b) - F( 1 ) ][ <( 1 ) - <( a) ] > 0. N, N - 1 U N = <( a) [ F( 1 ) - F( a) ] + <( 1 ) [ F( 2 ) - F( 1 ) ] + + <( N - 1 ) [ F( b) - F( N - 1 ) ]. N i i + 1, : U N - U N - 1 = [ F( i+1 ) - F( i ) ][ <( i ) - <( i- 1 ) ] > 0. (3) N ( N 1) 2 9U = <( i- 1 ) f ( i ) + < ( i ) [ F( i+1 ) - F( i ) ] - <( i ) f ( i ) = 0 9 i
360 ( ) 9 ] [ <( i ) - <( i- 1 ) ] f ( i ) = < ( i ) [ F( i+1 ) - F( i ) ]. i = i - 1 i = i + 1, U U : U = U = <( a) [ F( 1 ) - F( a) ] + + <( i- 1 ) [ F( i+1 ) - F( i- 1 ) ] + + <( N - 1 ) [ F( b) - F( N ) ]. 1 U > U = U, U ( ), i, 9U = 0, 9 i 9 2 U 9 2 < 0 i N - 1 [ <( i ) - <( i - 1 ) ] f ( i ) = < ( i ) [ F( i + 1 ) - F( i ) ] ( i = 1,2,, N - 1), N - 1 U, a, 3, Oj g ( S k) = Cj, g - 1 ( Cj ) = qc j OC i, g ( S k) = Ci, g ( S k) Cj, - 1 ( Cj ) qc j - 1, M S l, M 4 ΠS k, S k, S k, ( S j ) = Ci, ] Ci P S k ( S k) ] Ci CS k, TC i ( S j ) > TC i ( S q Ci ) > TC i ( S k ) ( S j ) PS i ( S i), Tc ( S j ) > Tc ( S i), M ΠS j, C0 Ci = ( S j ) S j, ( S j ) RS g ( S j ) RS C0, M ΠS j,, S j, Ci R S j C0 ; S j C0,, M 5 j g ( S k ) = C j, g - 1 ( C j ) = qc j i ( j < i), C j P S C i ] g ( S k) C i, - 1 ( C j ) = qc j M 4,, M, M 8 6 M, C i C i S k ϖ C j = ( S k) ( j < i), TC j ( S k ) > TC j ( S0 ) ( S0 C j ), C j S 0 C i C j, 8 (2007)
1 : 361 [ 1 ] Abdulkadiroglu, A., P. Pat hak, and A. Rot h, The New York City High School Match, A meri2 can Economic Review, 2005, 95 (2), 364 367. [ 2 ] Abdulkadiroglu, A., P. Pat hak, and A. Rot h, Strategy2proofness versus Efficiency in Matching wit h Indifferences : Redesigning t he N YC High School Match, Working Paper, Duke University, and Harvard University, 2008. [ 3 ] Abdulkadiroglu, A., P. Pat hak, A. Rot h, and T. Sgnmez, The Boston Public School Match, A2 merican Economic Review, 2005, 95 (2), 368 371. [ 4 ] Abdulkadiroglu, A., P. Pat hak, A. Rot h, and T. Sgnmez, Changing t he Boston School Choice Mechanism, NBER Working Paper No. 11965, 2006. [ 5 ] Abdulkadiroglu, A., and T. Sgnmez, School Choice : A Mechanism Design Approach, A merican Economic Review, 2003, 93 (3), 729 747. [ 6 ] Balinski, M., and T. Sgnmez, A Tale of Two Mechanisms : Student Placement, J ournal of Eco2 nomic Theory, 1999, 84 (1), 73 94. [ 7 ] Chen, Y., and T. Sgnmez, School Choice : An Experimental Study, J ournal of Economic Theo2 ry, 2006, 127 (1), 202 231. [ 8 ] Dubins, L., and D. Freedman, Machiavelli and t he Gale2Shapley Algorit hm, A merican M athe2 matical Monthl y, 1981, 88 (7), 485 494. [ 9 ] Ergin, H., and T. Sgnmez, Games of School Choice under t he Boston Mechanism, J ournal of Public Economics, 2006, 90 (1 2), 215 237. [ 10 ] Gale, D., and L. Shapley, College Admissions and t he Stability of Marriage, A merican M athe2 matical Monthl y, 1962, 69 (1), 9 15. [ 11 ],, ( ), 2007 6 3, 899 916 [ 12 ] Rot h, A., and A. Postlewaite, Weak versus Strong Domination in a Market wit h Indivisible Goods, J ournal of M at hematical Economics, 1977, 4 (2), 131 137. [ 13 ] Rot h, A., The Economics of Matching : Stability and Incentives, M athematics of Operations Re2 search, 1982a, 7 (4), 617 628. [ 14 ] Rot h, A., Incentive Compatibility in a Market wit h Indivisible Goods, Economics L etters, 1982b, 9 (2), 127 132. [ 15 ] Rot h, A., The Evolution of t he Labor Market for Medical Interns and Resident s : A Case Study in Game Theory, J ournal of Political Econom y, 1984, 92 (6), 991 1016. [ 16 ] Rot h, A., The College Admissions Problems is not Equivalent to t he Marriage Problem, J our2 nal of Economic Theory, 1985, 36 (2), 277 288. [ 17 ] Shapley, L., and H. Scarf, On Cores and Indivisible Goods, J ournal of M athematical Econom2 ics, 1974, 1 (1), 23 37. [ 18 ] Zhou, L., On a Conject ure by Gale about One2sided Matching Problem, J ournal of Economic T heory, 1990, 52 (1), 123 135.
362 ( ) 9 A Design for College and Graduate School Admission L IJ IA WEI ( X i amen Uni versit y) Abstract The college admission problem is one of the widely discussed issues in the edu2 cation literature. This paper analyzes the advantages and disadvantages of the parallel applica2 tion policy, and proposes that studentsπ utility can be improved by reducing the rate of tenta2 tive admissions, allowing for applications for different majors and increasing the number of colleges to be applied for. The admission of graduate schools, however, is of another type that has a decentralized admission system. This paper designs a preference ordering mecha2 nism for this type of admission, which satisfies the properties of being fair, non2wastef ul, in2 dividually rational, strategy2proof, and Pareto efficient, and then discusses how to apply the mechanism in reality. JEL Classif ication C78, D61, D78, I20