350 ( ) 9,,,,,,,,,,, :,,,,,,, ( Ergin and Sgnmez, 2006) Gale and Shapley (1962), Gale2Shapley,, Gale2Shapley ( (2007) ) Dubins and Freedman (1981) Gal

Size: px

Start display at page:

Download "350 ( ) 9,,,,,,,,,,, :,,,,,,, ( Ergin and Sgnmez, 2006) Gale and Shapley (1962), Gale2Shapley,, Gale2Shapley ( (2007) ) Dubins and Freedman (1981) Gal"

翁灯常
7 years ago
Views:

1 ( ) China Eco nomic Quarterly Vol19, No11 October, ,,,,,,,,, 2008,, 3, 4, 3 :, ; : (0592) ; E2mail com,,

2 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)

3 1 : 351 ( Galeπs Top trading cycles) 20 90,,, Abdulkadiroglu and Sgnmez (2003),, Abdulkadiroglu , 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,, ;,,,

4 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

5 1 : 353 Gale2Shapley, n m, qc i,,,,,, n, ( ), m,,, A,, ( ) 3, (2007),,,,,,,,,,,,,,, ( 105 %),,,, n i = 1 3,,,

6 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,

7 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,,,,,, ( )

8 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,,,,,,,,,,, ( ),,,

9 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 : ( ) ( )

10 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,

11 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

12 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)

13 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), [ 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, [ 3 ] Abdulkadiroglu, A., P. Pat hak, A. Rot h, and T. Sgnmez, The Boston Public School Match, A2 merican Economic Review, 2005, 95 (2), [ 4 ] Abdulkadiroglu, A., P. Pat hak, A. Rot h, and T. Sgnmez, Changing t he Boston School Choice Mechanism, NBER Working Paper No , [ 5 ] Abdulkadiroglu, A., and T. Sgnmez, School Choice : A Mechanism Design Approach, A merican Economic Review, 2003, 93 (3), [ 6 ] Balinski, M., and T. Sgnmez, A Tale of Two Mechanisms : Student Placement, J ournal of Eco2 nomic Theory, 1999, 84 (1), [ 7 ] Chen, Y., and T. Sgnmez, School Choice : An Experimental Study, J ournal of Economic Theo2 ry, 2006, 127 (1), [ 8 ] Dubins, L., and D. Freedman, Machiavelli and t he Gale2Shapley Algorit hm, A merican M athe2 matical Monthl y, 1981, 88 (7), [ 9 ] Ergin, H., and T. Sgnmez, Games of School Choice under t he Boston Mechanism, J ournal of Public Economics, 2006, 90 (1 2), [ 10 ] Gale, D., and L. Shapley, College Admissions and t he Stability of Marriage, A merican M athe2 matical Monthl y, 1962, 69 (1), [ 11 ],, ( ), , [ 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), [ 13 ] Rot h, A., The Economics of Matching : Stability and Incentives, M athematics of Operations Re2 search, 1982a, 7 (4), [ 14 ] Rot h, A., Incentive Compatibility in a Market wit h Indivisible Goods, Economics L etters, 1982b, 9 (2), [ 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), [ 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), [ 17 ] Shapley, L., and H. Scarf, On Cores and Indivisible Goods, J ournal of M athematical Econom2 ics, 1974, 1 (1), [ 18 ] Zhou, L., On a Conject ure by Gale about One2sided Matching Problem, J ournal of Economic T heory, 1990, 52 (1),

14 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

572 ( ) 9 (1997),,,,,, (, 1997),, (, 1998), (, 2006),,,,,,,, (, 1997),, ( Naughton, 1994) (Lipton and Sachs, 1990 ;, 2004 ; ),,, (, 1997) (1998),,,,,,

572 ( ) 9 (1997),,,,,, (, 1997),, (, 1998), (, 2006),,,,,,,, (, 1997),, ( Naughton, 1994) (Lipton and Sachs, 1990 ;, 2004 ; ),,, (, 1997) (1998),,,,,, 9 2 2010 1 ( ) China Econo mic Quarterly Vol19, No12 J anuary, 2010 3,,, 2 451,,,,,,,, ( ),, (, 2005), 1 (, 1996a), (, 2004), : W + q, W, ( ), q,, : ( ),,, 3 :,, 510632 ; E2mail :zqx831118 @163. com, (08J