Stability, efficiency and monotonicity in two-sided matching

Salem, Sherif Gamal (2012): Stability, efficiency and monotonicity in two-sided matching.

Abstract

we propose a fairness property called P-monotonicity that we would like a matching mechanism to satisfy. We show that it is impossible to have a mechanism which is both stable and P- monotonic. Moreover, we show that it is impossible to have a mechanism which is both efficient and P-monotonic.

• Item Type: MPRA Paper
• Language: English
• Keywords: Stability, Efficiency, Monotonicity, Two-Sided Matching
• Subjects: C - Mathematical and Quantitative Methods > C7 - Game Theory and Bargaining Theory > C78 - Bargaining Theory ; Matching Theory

References

[1] Abdulkadiroglu, A. and T. Sönmez (2003), School Choice: A Mechanism Design Approach, American Economic Review, Vol. 93, 729-747.

[2] Abdulkadiroglu, A., P. Pathak and A. Roth (2005), The New York City High School Match, American Economic Review Papers and Proceedings, Vol. 95, 364- 367.

[3] Alcalde, J. and S. Barberà (1994), Top Dominance and the Possibility of Strategy-Proof Stable Solutions to Matching Problems, Economic Theory, Vol. 4, 417-435.

[4] Balinski, B. and T. Sönmez (1999), A Tale of Two Mechanisms: Student Placement, Journal of Economic Theory, Vol. 84, 73-94.

[5] Biró, P. (2008), Student Admissions in Hungary as Gale and Shapley Envisaged, TR-2008-291, Department of Computing Science , University of Glasgow.

[6] Gale, D. and L. S. Shapley (1962), College Admissions and the Stability of Marriage, The American Mathematical Monthly, Vol. 69, 9-15.

[7] Kojima, F. (2010), Impossibility of Stable and Nonbossy Matching Mechanism, Economic Letters, Vol. 107, 6970.

[8] Matsubae. T. (2010), Impossibility of Stable and Non-damaging Bossy Matching Mechanism, Economics Bulletin, Vol. 30, 2092-2096.

[9] Roth, A. (1982), The Economics of Matching: Stability and Incentives, Mathematics of Operations Research, Vol. 7, 617-628.

[10] Roth, A. (2002), The Economist as Engineer: Game Theory, Experimentation, and Computation as Tools for Design Economics, Econometrica, Vol. 70, 1341- 1378.

[11] Roth, A. (2008), Deferred Acceptance Algorithms: History, Theory, Practice, and Open Questions, International Journal of Game Theory, Vol. 36, 537-569.

[12] Selim, T. H. and S. G. Salem (2010), Education Matching in Egypt and the Gale-Shapley Algorithm: A Theoretical Perspective, African Journal of Business and Economic Research, Vol. 5, 9 - 22.

[13] Sönmez, T. (1994), Strategy-Proofness in Many-To-One Matching Problems, Review of Economic Design, Vol. 1, 365-380.