Two-sided Matching: An Application to High School Choice

“Boston Mechanism” is the name of the student assignment mechanism used in Boston from 1999 to 2005. The history of school choice in Boston began in the 1970s and desegregation was the key factor for its implementation. Indeed, in 1974 Federal Judge W. Arthur Garrity supervised the Boston Public Schools (BPS) busing plans in use and required that the school committee attained to the Massachusetts law on the subject, according to which schools admissions had to be meticulously balanced by race (Pathak, 2011). However, after the U.S. Court of Appeals authorised Boston Public Schools to apply a choice-based assignment system in 1987, the Boston School committee decided to implement an assignment mechanism not based on racial preferences in 1999, and adopted the Boston Mechanism (Abdulkadiroğlu, Pathak, Roth and Sönmez, 2005).
The Boston Mechanism was a priority matching mechanism, once widely used in the United Kingdom medical labor market (Roth 1991) and now extremely common in school choice: apart from the Boston case, variants are in use in many school districts, such as Lee County, Florida, Minneapolis and Seattle (Abdulkadiroğlu and Sönmez, 2003). Main prerogative of priority matching mechanisms is to match the largest number of applicants to their first choice, but this is at the expense of efficiency and strategy-proofness.
Boston mechanism’s flaws were highlighted by Abdulkadiroğlu and Sönmez (2003) and brought to the knowledge of the public opinion by reporter Gareth Cook, with an article on the Boston Globe in September 2003. A month later, Valerie Edwards, then BPS Strategic Planning Manager, and her colleague Carleton Jones contacted the researchers for a meeting and commissioned them a study of the Boston school assignment system, providing all the necessary information. Grounded on the pending results of that study, Superintendent Payzant asked the economists to work on a new school choice system, that would have been operative since a couple of years later, in 2005 (Abdulkadiroğlu, Pathak, Roth, Sönmez, 2005).
In the same years, as we know, New York City was implementing a new student assignment mechanism as well. Although the new high school choice system in New York was perceived as a benchmark, Boston taskforce researchers could not take for granted that the Massachusetts city would benefit from the deferred acceptance algorithm as much as New York City, and considered also top trading cycles as a possible mechanism (Abdulkadiroğlu, Pathak, Roth, Sönmez, 2005). In fact, there were several differences between the situations in Boston and in New York. First of all, school choice system in Boston concerns not only high school admissions, but all grades, comprising also kindergarten, elementary and middle school. Moreover, the Boston Mechanism was already based on a centralized system. Finally, schools in Boston, unlike New York City ones, are completely “passive”, since admissions hinge on priorities set centrally (Abdulkadiroğlu et al., 2006).
Boston Public Schools system is divided into three zones: East, West, and North and takes care of over 60.000 kids from kindergarten to grade twelve.
Elementary and middle schools are mostly zone schools and only a few are citywide schools, to which kids from every neighbourhood can apply. Instead, the majority of high schools is citywide, whereas a few special-education programs are not part of the centralized allocation system (Abdulkadiroğlu, Pathak, Roth, and Sönmez, 2005).

As Abdulkadiroğlu et al. (2006, p.4) clearly explain, most schools allocate half of their seats according to exogenous criteria that constitute five categories. The priority classes are:
1) Guaranteed priority, for students who already attend the school or went to a feeder school;
2) Sibling-walk priority, for students who both have a sibling at the school and live in the walk zone of the school;
3) Sibling priority, for students who have a sibling at the school;
4) Walk –zone priority, for students who live in the walk zone of the school;
5) Other students.
For the other half of the seats only guaranteed and sibling priorities are valid, whereas walk zone priorities are not contemplated. A random tiebreaker, through a random lottery number given to each student, is used to break ties in each indifference class: thereby fixed priorities become similar to school preferences and it is possible to apply a two-sided matching mechanism.
However, these exogenous priorities are adopted only among those students who ranked the school in the same position (e.g. everyone who placed that school as its kth choice in the application form), exactly due to the peculiar procedure of priority matching mechanisms.
As Abdulkadiroğlu, Pathak, Roth and Sönmez (2005) explain, under the Boston Mechanism, parents could enrol their kids, ranking from three to five schools, during several registration periods: January was the most popular, but also February, March and April were possible. Obviously, each school capacity was decided by BPS. As our economists (2005) describe it, the Boston Mechanism considered each school separately, together with the students ranking it first, than second and so on:

Step 1: For each school, students who ranked it as their first choice are considered. Those students are allocated to their first choice school according to the priority order and using the single random tiebreaker, until there are no more seats or students who ranked it first.
Step k: For each school which still has empty seats, students who ranked it as their kth choice are considered. Those students receive a seat from their kth preference according to priority classes and the single random tiebreaker, until there are no more seats or students who rank that school as their kth preference.
The algorithm terminates when every student has been assigned or every submitted choice has been considered. When a student does not receive a seat in any of the schools she listed, BPS assigns her to the school with available seats, closest to her home.

Furthermore, the Boston Mechanism made use of waiting lists and their operation is noteworthy as well. In fact, students who do not get their top choice, may be added to a school’s waiting list. For example, a student who received a seat in the school she listed second, enters her first choice waitlist. Likewise, a student who received a seat in the school she listed third, enters both her first and her second choice waitlists, and so on until students who did not get any of their choices and are placed to up to three waitlists. In 2004, however, waiting lists’ operation changed through the introduction of a limit in size equal to the 25 percent of the number of seats at each grade level in the school and an active confirmation of interest in a waitlist by the side of the students involved (Abdulkadiroğlu, Pathak, Roth and Sönmez, 2005).
[…]