A Characterization of the Top Trading Cycles Mechanism for the School Choice Problem

Dur, Umut (2012): A Characterization of the Top Trading Cycles Mechanism for the School Choice Problem.

Abstract

Abstract This paper characterizes the top trading cycles mechanism for the school choice problem. Schools may have multiple available seats to be assigned to students. For each school a strict priority ordering of students is determined by the school district. Each student has strict preference over the schools. We first define weaker forms of fairness, consistency and resource monotonicity. We show that the top trading cycles mechanism is the unique Pareto efficient and strategy-proof mechanism that satisfies the weaker forms of fairness, consistency and resource monotonicity. To our knowledge this is the first axiomatic approach to the top trading cycles mechanism in the school choice problem where schools have a capacity greater than one.

• Item Type: MPRA Paper
• Language: English
• Keywords: Top Trading Cycles Mechanism, School Choice Problem
• Subjects: C - Mathematical and Quantitative Methods > C7 - Game Theory and Bargaining Theory > C78 - Bargaining Theory ; Matching Theory; I - Health, Education, and Welfare > I2 - Education and Research Institutions > I20 - General; D - Microeconomics > D7 - Analysis of Collective Decision-Making > D78 - Positive Analysis of Policy Formulation and Implementation; D - Microeconomics > D6 - Welfare Economics > D61 - Allocative Efficiency ; Cost-Benefit Analysis

References

Atila Abdulkadiroglu. Generalized matching for school choice. Working paper, 2011.

Atila Abdulkadiroglu and Yeon-Koo Che. The role of priorities in assigning indivisible objects: A characterization of top trading cycles. Working paper, 2010.

Atila Abdulkadiroglu and Tayfun Sönmez. House allocation with existing tenants. Journal of Eco- nomic Theory, 88:233260, 1999.

Atila Abdulkadiroglu and Tayfun Sönmez. School choice: A mechanism design approach. American Economic Review, 93:729747, 2003.

Atila Abdulkadiroglu, Parag A. Pathak, and Alvin E. Roth. Strategy-proofness versus eciency in matching with indierences: Redesigning the nyc high school match. American Economic Review, 99:19541978, 2009.

Jose Alcalde and Salvador Barbera. Top dominance and the possibility of strategy-proof stable solutions to matching problems. Economic Theory, 4:417435, 1994.

Michel Balinski and Tayfun Sönmez. A tale of two mechanisms: Student placement. Journal of Economic Theory, 84:7394, 1999.

Youngsub Chun and William Thomson. Monotonicity properties of bargaining solutions when applied to economics. Mathematical Social Sciences, 15:1127, 1988.

Lars Ehlers and Bettina Klaus. Resource-monotonicity for house allocation problems. International Journal of Game Theory, 32:545560, 2003.

Haluk Ergin. Consistency in house allocation problems. Journal of Mathematical Economics, 34: 7797, 2000.

Onur Kesten. On two competing mechanisms for priority-based allocation problems. Journal of Economic Theory, 127:155171, 2006.

Onur Kesten. Coalitional strategy-proofness and resource monotonicity for house allocation problems. International Journal of Game Theory, 38:1721, 2009.

Fuhito Kojima and M. Utku Ünver. The 'boston' school choice mechanism. Stanford University and Boston College, unpublished mimeo, 2010.

Thayer Morrill. An alternative characterization of top trading cycles. forthcoming in Economic Theory, 2012.

Parag A. Pathak. The mechanism design approach to student assignment. Annual Review of Eco- nomics, 3:513536, 2011.

Marek Pycia and M. Utku Ünver. Incentive compatible allocation and exchange of discrete resources. UCLA and Boston College, unpublished mimeo, 2011a.

Marek Pycia and M. Utku Ünver. Trading cycles for school choice. UCLA and Boston College, unpublished mimeo, 2011b.

Lloyd Shapley and Herbert Scarf. On cores and indivisibility. Journal of Mathematical Economics, 1:2337, 1974.

Tayfun Sönmez and M. Utku Ünver. House allocation with existing tenants: A characterization. Games and Economic Behavior, 69:425445, 2010.

William Thomson. The theory of fair allocation. book manuscript, 2000.

William L. Thomson. The consistency principle. In Tatsuro Ichiishi, Abraham Neyman, and Yair Tauman, editors, Game Theory and Applications, pages 187215. Academic Press, 1990.