The Boston Public School Match
˙ ˙ ˘ By ATILA ABDULKADIROGLU, PARAG A. PATHAK, ALVIN E. ROTH,
AND

¨ TAYFUN SONMEZ*

After the publication of “School Choice: A Mechanism Design Approach” by Abdulkadiroglu and Sonmez (2003), a Boston Globe re˘ ¨ porter contacted us about the Boston Public Schools (BPS) system for assigning students to schools. The Globe article highlighted the difficulties that Boston’s system may give parents in strategizing about applying to schools. Briefly, Boston tries to give students their firstchoice school. But a student who fails to get her first choice may find her later choices filled by students who chose them first. So there is a risk in ranking a school first if there is a chance of not being admitted; other schools that would have been possible had they been listed first may also be filled. Valerie Edwards, then Strategic Planning Manager at BPS, and her colleague Carleton Jones invited us to a meeting in October 2003. BPS agreed to a study of their assignment system and provided us with micro-level data sets on choices and characteristics of students in the grades at which school choices are made (K, 1, 6, and 9), and school characteristics. Based on the pending results of this study, the Superintendent has asked for our advice on the design of a new assignment mechanism. This paper describes some of the difficulties with the current mechanism and some elements of the design and evaluation of possible replacement mechanisms. School choice in Boston has been partly shaped by desegregation. In 1974, Judge W. Arthur Garrity ordered busing for racial balance. In 1987, the U.S. Court of Appeals freed BPS to adopt a new, choice-based assignment plan. In
* Abdulkadiroglu: Department of Economics, Columbia ˘ University, New York, NY 10027; Pathak and Roth: Harvard Business School and Department of Economics, Harvard University, Cambridge, MA 02138; Sonmez: De¨ partment of Economics, Koc University, Istanbul, Turkey, ¸ and Harvard University. 368

1999 BPS eliminated racial preferences in assignment and adopted the current mechanism.
I. The Current Boston Mechanism

BPS has over 60,000 students from grades K–12 in almost 140 schools in three zones: East, West, and North. During the first registration period in January, students who will be entering a new school in grades K, 1, 6, and 9 are asked to rank at least three schools in order of preference. Although most assignments are made in the first registration period, Boston has other registration periods in February, March, and April. For elementary and middle school, parents are asked to consider schools in their zone plus five schools open to all neighborhoods. High school admissions are city-wide for 18 schools. There are also 13 high schools that require special admissions and three special-education programs that are not part of the centralized allocation process. In 2004, at the end of the first registration period, there were about 4,800 students entering kindergarten, 4,000 entering grade 1, over 4,300 students entering grade 6, and about 4,000 entering grade 9. Boston assigns students if possible to their first-choice school, allocating over-demanded seats by a system of priorities. First, a younger sibling has priority to attend the same school as an older sib. Next in priority for half of each program’s seats are students from the school’s walk zone. Not every residential location in the city has a school for which they obtain walkzone preference. Students who live in these locations are then given priority for assignment to their first- and second-choice schools. Additional priorities are assigned by random numbers generated once for each student. After the first registration period there is no longer a walk-zone priority.

VOL. 95 NO. 2

PRACTICAL MARKET DESIGN

369

Within each priority class, students’ random numbers determine a strict priority order. Each school has a maximum capacity determined by BPS. The Boston mechanism assigns students as follows: Step 1.—For each school, consider the students who have listed it as their first choice and assign seats to these students in priority order until either no seats remain or no student remains who has listed it as first choice. Step k.—For each school with seats still available, consider the students who have listed it as their kth choice and assign seats to these students in priority order until either no seats remain or no student remains who has listed it as kth choice. The procedure terminates when each student is assigned a seat (or all submitted choices are considered). If a student does not get her top choice, she may be added to a school’s waiting list. Students who get their second choice go on the wait-list for their first choice. Students who get neither their first nor second choice are placed on wait-lists for both. Students who do not get any of their choices go on wait-lists for up to three choices. The priority on the wait-list is based on sibling preference, round of application, and random number. When the school year starts, if a student leaves the public-school system, the student may no longer stay on a waitlist. All wait-lists expire in January of the next school year. During the 2002–2003 assignment process, about 11 percent of students were on wait-lists. In 2004, two major changes were introduced: caps to the size of the wait-list and active confirmation of interest in a wait-list. This year, students may go on wait-lists only until the wait-list contains 25 percent of the number of seats at the grade level in the school. Also, students already on the number of wait-lists they are entitled to according to the school choice they received must leave one list before being added to another. At the end of the assignment process, if a student is not given any of his choices, or did not return an application, BPS assigns the student to the school closest to home that has space.

The Boston mechanism is a priority matching mechanism (Roth, 1991). Priority mechanisms have been used to match medical graduates to internships in several regions of the United Kingdom, starting in the 1960s. Each of these mechanisms was abandoned after being gamed by the participants. Yan Chen and Sonmez ¨ (2005) experimentally examine preference manipulation under the Boston mechanism and observe the associated welfare loss. Priority mechanisms are common in school choice. The largest district we know of with a priority mechanism is Hillsborough County School District in Tampa-St. Petersburg, the 11th largest school district in the United States, with about 170,000 students.1 Cambridge, Denver, Minneapolis, and Seattle also have priority mechanisms. The idea that students and parents should be cautious in choosing their first choice is included in the reference material provided to students and parents. BPS states “for a better chance of getting your ‘first choice’ school ... consider choosing less popular schools” (Introducing Boston Public Schools, 2004, p. 3 [quotation marks in original]). In Seattle and Tampa-St. Petersburg, the incentives for such preference manipulation are advocated in the ¨ local press (see Haluk Ergin and Sonmez, 2005). Note that when students rank less competitive programs first, many get their stated first choice. Approximately 80 percent of students who submit preferences in the first registration period get their stated first choice in Boston. Of course, this is not necessarily their most preferred school.
II. Two Alternative Matching Mechanisms

It is costly in the Boston mechanism to list a first-choice that you do not succeed in getting because, once other students are assigned their first-choice places, they cannot be displaced even by a student with higher priority. A class of mechanisms that avoid this are deferredacceptance algorithms (David Gale and Lloyd Shapley, 1962) of the kind adopted by New

Often, the precise allocation rules are not publicly specified by the school districts.

1

370

AEA PAPERS AND PROCEEDINGS

MAY 2005

York City high schools (Abdulkadiroglu et al., ˘ 2005) and elsewhere (Roth, 2002): Step 1.—Each student “proposes” to her first choice. Each school tentatively assigns its seats to its proposers one at a time in their priority order. Any remaining proposers are rejected. Step k.—Each student who was rejected in the previous step proposes to her next choice if one remains. Each school considers the students it has been holding together with its new proposers and tentatively assigns its seats to these students one at a time in priority order. Any remaining proposers are rejected. The algorithm terminates when no student proposal is rejected, and each student is assigned her final tentative assignment. In contrast with the Boston algorithm, the deferred-acceptance algorithm assigns seats only tentatively at each step, so students with higher priorities may be considered in subsequent steps. Consequently it is stable in the sense that there is no student who loses a seat to a lower-priority student and receives a lesspreferred assignment. Moreover all students prefer their outcome to any other stable matching (Gale and Shapley, 1962), and the induced student-optimal stable mechanism is dominantstrategy incentive-compatible (Roth, 1982a). (Unlike in New York City, the schools are not strategic players in Boston, as the priorities are set centrally.) If the intention of the school board is that priorities be “strictly enforced,” this mechanism is a leading candidate. However, if welfare considerations apply only to students, there is tension between stability and Pareto optimality (Roth, 1982a). If priorities are merely a device for allocating scarce spaces, it might be possible to assign students to schools they prefer by allowing them to trade their priority at one school with a student who has priority at a school they prefer. The following top trading cycles (TTC) mechanism creates a virtual exchange for priorities: Step 1.—Assign counters for each school to track how many seats remain available. Each student points to her favorite school, and each school points to the student with the highest priority. There must be at least one cycle. (A

cycle is an ordered list of distinct schools and students (student 1 - school 1 - student 2 - ... student k - school k) with student 1 pointing to school 1, school 1 to student 2, ... , student k to school k, and school k pointing to student 1.) Each student is part of at most one cycle. Every student in a cycle is assigned a seat at the school she points to and is removed. The counter of each school is reduced by 1, and if it reaches zero, the school is removed. Step k.—Each remaining student points to her favorite school among the remaining schools, and each remaining school points to the student with highest priority among the remaining students. There is at least one cycle. Every student in a cycle is assigned a seat at the school she points to and is removed. The counter of each school in a cycle is reduced by 1, and if it reaches zero, the school is removed. The procedure terminates when each student is assigned a seat (or all submitted choices are considered). This version of the TTC mechanism was introduced by Abdulkadiroglu and Sonmez ˘ ¨ (2003) and is an extension of Gale’s “top trading cycles mechanism” described in Shapley and Herbert Scarf (1974). Many properties of TTC carry over to school choice, including Pareto efficiency (Shapley and Scarf, 1974) and dominant-strategy incentive compatibility (Roth, 1982b). Variations of this procedure can also be considered which may reduce instability (e.g., Onur Kesten, 2005). See also the recent design of a kidney exchange clearinghouse (Roth et al., 2004, 2005).
III. Design Considerations

Unlike in New York (Abdulkadiroglu et al., ˘ 2005), students’ priorities at schools are not set by schools, but by the central administration. There does not seem to be any issue of individual schools gaming the system in Boston. Therefore, it is natural to ask whether the benefits that “stable” matching produces in New York have parallel benefits in the different situation in Boston, and if not, whether the welfare improvements that might be available from a TTC-like mechanism should be considered. At a public meeting of the Boston School

VOL. 95 NO. 2

PRACTICAL MARKET DESIGN

371

Committee in October 2004 we were asked for advice about how to think about this. We replied with the question “Would anyone mind if two students who each preferred the school in the other student’s walk zone were to trade their priorities and enroll in those schools?” If this is not desirable (e.g., because of transportation costs, or because walk-zone priorities reflect a public good that results when parents walk children to school, or because lawsuits might follow if a child is excluded from a school while another with lower priority is admitted), then stable matchings would efficiently combine student preferences with priorities. But if helping the students this way is worth whatever transportation and other costs might be incurred, then only the students’ preferences need to be taken into account and a TTC-like mechanism might be more appropriate.
IV. Recent Developments

School Match.” American Economic Review, 2005 (Papers and Proceedings), 95(2), pp. 364 – 67.
Abdulkadiroglu, Atila and Sonmez, Tayfun. ˘ ¨

In December 2003, the Boston School Committee initiated an evaluation of all aspects of student assignment. The final task-force report recommends changing the student assignment algorithm. The task force observed that, even though students can select three schools, many children do not get any of their picks because, if a parent and student choose three popular schools and do not get their first choice, they may also miss their second and third choice. A memorandum from Superintendent Payzant in December 2004 states that BPS plans to change the computerized process used to assign students to schools. Although the task-force report recommended that BPS adopt the TTC assignment algorithm, the School Committee is interested in simulations of both mechanisms and in understanding the extent of preference manipulation under the Boston mechanism. They are also thinking through their philosophical position on the trade-off between stability and efficiency. REFERENCES
Abdulkadiroglu, Atila; Pathak, Parag A. and ˘ Roth, Alvin E. “The New York City High

“School Choice: A Mechanism Design Approach.” American Economic Review, 2003, 93(3), pp. 729 – 47. Chen, Yan and Sonmez, Tayfun. “School Choice: ¨ An Experimental Study.” Journal of Economic Theory, 2005 (forthcoming). Ergin, Haluk and Sonmez, Tayfun. “Games of ¨ School Choice under the Boston Mechanism.” Journal of Public Economics, 2005 (forthcoming). Gale, David and Shapley, Lloyd. “College Admissions and the Stability of Marriage.” American Mathematical Monthly, 1962, 69(1), pp. 9 –15. Kesten, Onur. “Student Placement to Public Schools in the US: Two New Solutions.” Mimeo, University of Rochester, 2005. Roth, Alvin E. “The Economics of Matching: Stability and Incentives.” Mathematics of Operations Research, 1982, 7(4), pp. 617– 28. Roth, Alvin E. “Incentive Compatibility in a Market with Indivisible Goods.” Economics Letters, 1982b, 9(2), pp. 127–32. Roth, Alvin E. “A Natural Experiment in the Organization of Entry-Level Labor Markets: Regional Markets for New Physicians and Surgeons in the United Kingdom.” American Economic Review, 1991, 81(3), pp. 414 – 40. Roth, Alvin E. “The Economist as Engineer: Game Theory, Experimental Economics and Computation as Tools of Design Economics.” Econometrica, 2002, 70(4), pp. 1341– 78.
¨ Roth, Alvin E.; Sonmez, Tayfun and Unver, M. ¨ Utku. “Kidney Exchange.” Quarterly Journal

of Economics, 2004, 119(2), pp. 457– 88.
¨ Roth, Alvin E.; Sonmez, Tayfun and Unver, M. ¨ Utku. “A Kidney Exchange Clearinghouse in

New England.” American Economic Review, 2005 (Papers and Proceedings), 95(2), pp. 376 – 80. Shapley, Lloyd and Scarf, Herbert. “On Cores and Indivisibility.” Journal of Mathematical Economics, 1974, 1(1), pp. 23–28.