Two-sided Matching: An Application to High School Choice

"What is important about Columbus’s discovery of America is not that it was the first, but that it was the last. After Columbus, America was never lost again; no subsequent explorers can claim its discovery. But to make a somewhat different point, just as the importance of what Columbus discovered is in large measure due to what was subsequently learned about and accomplished in the Americas, so it is with scientific theories and discoveries, whose importance derives from what they allow us to understand and predict."
In these terms, Harvard Professor of Economics and Business Administration Alvin Roth (Roth and Sotomayor, 1990, p. 170) refers to the work of Gale and Shapley, whose renowned paper “College Admissions and the Stability of Marriage”, published in 1962, laid the foundation stone of a new branch of economic theory. From that moment on, an entire theoretical literature arose, concerning two-sided matching problems.
The metaphor of Columbus’s discovery of America alludes to the fact that the NIMP (National Intern Matching Program) algorithm, first used in 1951 to match graduating medical students and hospitals, is a stable matching mechanism; nevertheless, the existence of the property of stability was first demonstrated only years later by Gale and Shapley (1962) through the deferred acceptance procedure, heart of their contribution and now even used to describe the NIMP procedure. As Roth himself underlines (Roth and Sotomayor, 1990, p. 170), this is a perfect case of art imitating life imitating art. In fact, two-sided matching is a field of mathematics where theory and applications proceed at the same pace, not being able to prescind one from the other.
Moreover, the NIMP algorithm epitomises one of the main fields of application of two-sided matching: medical labour market, as it emerges from “What have we learned from market design?”, a review on the subject advance by Roth himself (2008). On the other hand, the same article outlines other fields where two-sided matching theories have been successfully implemented, such as school choice. This thesis addresses exactly the student assignment mechanism implemented during the last years in two of the main cities of the United States of America: New York and Boston.