Original PDF Flash format the-boston-public-school-match  


The Boston Public School Match

The Boston Public School Match
By ATI˙LA ABDULKADI˙ROG˘LU, PARAG A. PATHAK, ALVIN E. ROTH, AND TAYFUN SO¨NMEZ*
After the publication of “School Choice: A
1999 BPS eliminated racial preferences in as-
Mechanism Design Approach” by Abdulkadiro-
signment and adopted the current mechanism.
g˘lu and So¨nmez (2003), a Boston Globe re-
porter contacted us about the Boston Public
I. The Current Boston Mechanism
Schools (BPS) system for assigning students to
schools. The Globe article highlighted the dif-
BPS has over 60,000 students from grades
ficulties that Boston’s system may give parents
K–12 in almost 140 schools in three zones:
in strategizing about applying to schools.
East, West, and North. During the first registra-
Briefly, Boston tries to give students their first-
tion period in January, students who will be
choice school. But a student who fails to get her
entering a new school in grades K, 1, 6, and 9
first choice may find her later choices filled by
are asked to rank at least three schools in order
students who chose them first. So there is a risk
of preference. Although most assignments are
in ranking a school first if there is a chance of
made in the first registration period, Boston has
not being admitted; other schools that would
other registration periods in February, March,
have been possible had they been listed first
and April.
may also be filled.
For elementary and middle school, parents
Valerie Edwards, then Strategic Planning
are asked to consider schools in their zone plus
Manager at BPS, and her colleague Carleton
five schools open to all neighborhoods. High
Jones invited us to a meeting in October 2003.
school admissions are city-wide for 18 schools.
BPS agreed to a study of their assignment sys-
There are also 13 high schools that require
tem and provided us with micro-level data sets
special admissions and three special-education
on choices and characteristics of students in the
programs that are not part of the centralized
grades at which school choices are made (K, 1,
allocation process.
6, and 9), and school characteristics. Based on
In 2004, at the end of the first registration
the pending results of this study, the Superin-
period, there were about 4,800 students entering
tendent has asked for our advice on the design
kindergarten, 4,000 entering grade 1, over 4,300
of a new assignment mechanism. This paper
students entering grade 6, and about 4,000 en-
describes some of the difficulties with the cur-
tering grade 9.
rent mechanism and some elements of the de-
Boston assigns students if possible to their
sign and evaluation of possible replacement
first-choice school, allocating over-demanded
mechanisms.
seats by a system of priorities. First, a younger
School choice in Boston has been partly shaped
sibling has priority to attend the same school as
by desegregation. In 1974, Judge W. Arthur
an older sib. Next in priority for half of each
Garrity ordered busing for racial balance. In
program’s seats are students from the school’s
1987, the U.S. Court of Appeals freed BPS to
walk zone. Not every residential location in the
adopt a new, choice-based assignment plan. In
city has a school for which they obtain walk-
zone preference. Students who live in these
locations are then given priority for assignment
* Abdulkadirog˘lu: Department of Economics, Columbia
to their first- and second-choice schools. Addi-
University, New York, NY 10027; Pathak and Roth:
tional priorities are assigned by random num-
Harvard Business School and Department of Economics,
bers generated once for each student. After the
Harvard University, Cambridge, MA 02138; So¨nmez: De-
first registration period there is no longer a
partment of Economics, Koc¸ University, Istanbul, Turkey,
and Harvard University.
walk-zone priority.
368
VOL. 95 NO. 2
PRACTICAL MARKET DESIGN
369
Within each priority class, students’ random
The Boston mechanism is a priority matching
numbers determine a strict priority order. Each
mechanism (Roth, 1991). Priority mechanisms
school has a maximum capacity determined by
have been used to match medical graduates to
BPS. The Boston mechanism assigns students
internships in several regions of the United
as follows:
Kingdom, starting in the 1960s. Each of these
mechanisms was abandoned after being gamed
Step 1.—For each school, consider the students
by the participants. Yan Chen and So¨nmez
who have listed it as their first choice and
(2005) experimentally examine preference ma-
assign seats to these students in priority order
nipulation under the Boston mechanism and
until either no seats remain or no student
observe the associated welfare loss.
remains who has listed it as first choice.
Priority mechanisms are common in school
Step k.—For each school with seats still avail-
choice. The largest district we know of with a
able, consider the students who have listed it
priority mechanism is Hillsborough County
as their kth choice and assign seats to these
School District in Tampa-St. Petersburg, the
students in priority order until either no seats
11th largest school district in the United States,
remain or no student remains who has listed
with about 170,000 students.1 Cambridge, Den-
it as kth choice.
ver, Minneapolis, and Seattle also have priority
mechanisms.
The procedure terminates when each student is
The idea that students and parents should be
assigned a seat (or all submitted choices are
cautious in choosing their first choice is in-
considered).
cluded in the reference material provided to
If a student does not get her top choice, she
students and parents. BPS states “for a better
may be added to a school’s waiting list. Stu-
chance of getting your ‘first choice’ school
dents who get their second choice go on the
... consider choosing less popular schools” (In-
wait-list for their first choice. Students who get
troducing Boston Public Schools, 2004, p. 3
neither their first nor second choice are placed
[quotation marks in original]). In Seattle and
on wait-lists for both. Students who do not get
Tampa-St. Petersburg, the incentives for such
any of their choices go on wait-lists for up to
preference manipulation are advocated in the
three choices. The priority on the wait-list is
local press (see Haluk Ergin and So¨nmez,
based on sibling preference, round of applica-
2005). Note that when students rank less com-
tion, and random number. When the school year
petitive programs first, many get their stated
starts, if a student leaves the public-school sys-
first choice. Approximately 80 percent of stu-
tem, the student may no longer stay on a wait-
dents who submit preferences in the first regis-
list. All wait-lists expire in January of the next
tration period get their stated first choice in
school year.
Boston. Of course, this is not necessarily their
During the 2002–2003 assignment process,
most preferred school.
about 11 percent of students were on wait-lists.
In 2004, two major changes were introduced:
II. Two Alternative Matching Mechanisms
caps to the size of the wait-list and active con-
firmation of interest in a wait-list. This year,
It is costly in the Boston mechanism to list a
students may go on wait-lists only until the
first-choice that you do not succeed in getting
wait-list contains 25 percent of the number of
because, once other students are assigned their
seats at the grade level in the school. Also,
first-choice places, they cannot be displaced
students already on the number of wait-lists
even by a student with higher priority. A class
they are entitled to according to the school
of mechanisms that avoid this are deferred-
choice they received must leave one list before
acceptance algorithms (David Gale and Lloyd
being added to another.
Shapley, 1962) of the kind adopted by New
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 stu-
dent to the school closest to home that has
1 Often, the precise allocation rules are not publicly
space.
specified by the school districts.
370
AEA PAPERS AND PROCEEDINGS
MAY 2005
York City high schools (Abdulkadirog˘lu et al.,
cycle is an ordered list of distinct schools and
2005) and elsewhere (Roth, 2002):
students (student 1 - school 1 - student 2 - ... -
student k - school k) with student 1 pointing
Step 1.—Each student “proposes” to her first
to school 1, school 1 to student 2, ... , student
choice. Each school tentatively assigns its
k to school k, and school k pointing to student
seats to its proposers one at a time in their
1.) Each student is part of at most one cycle.
priority order. Any remaining proposers are
Every student in a cycle is assigned a seat at
rejected.
the school she points to and is removed. The
Step k.—Each student who was rejected in the
counter of each school is reduced by 1, and if
previous step proposes to her next choice if
it reaches zero, the school is removed.
one remains. Each school considers the stu-
Step k.—Each remaining student points to her
dents it has been holding together with its
favorite school among the remaining schools,
new proposers and tentatively assigns its
and each remaining school points to the stu-
seats to these students one at a time in priority
dent with highest priority among the remain-
order. Any remaining proposers are rejected.
ing students. There is at least one cycle.
Every student in a cycle is assigned a seat at
The algorithm terminates when no student pro-
the school she points to and is removed. The
posal is rejected, and each student is assigned
counter of each school in a cycle is reduced
her final tentative assignment.
by 1, and if it reaches zero, the school is
In contrast with the Boston algorithm, the
removed.
deferred-acceptance algorithm assigns seats
only tentatively at each step, so students with
The procedure terminates when each student is
higher priorities may be considered in subse-
assigned a seat (or all submitted choices are
quent steps. Consequently it is stable in the
considered).
sense that there is no student who loses a seat to
This version of the TTC mechanism was in-
a lower-priority student and receives a less-
troduced
by
Abdulkadirog˘lu
and
So¨nmez
preferred assignment. Moreover all students
(2003) and is an extension of Gale’s “top trad-
prefer their outcome to any other stable match-
ing cycles mechanism” described in Shapley
ing (Gale and Shapley, 1962), and the induced
and Herbert Scarf (1974). Many properties of
student-optimal stable mechanism is dominant-
TTC carry over to school choice, including Pa-
strategy incentive-compatible (Roth, 1982a).
reto efficiency (Shapley and Scarf, 1974) and
(Unlike in New York City, the schools are not
dominant-strategy incentive compatibility (Roth,
strategic players in Boston, as the priorities are
1982b). Variations of this procedure can also be
set centrally.) If the intention of the school
considered which may reduce instability (e.g.,
board is that priorities be “strictly enforced,”
Onur Kesten, 2005). See also the recent design
this mechanism is a leading candidate.
of a kidney exchange clearinghouse (Roth et al.,
However, if welfare considerations apply
2004, 2005).
only to students, there is tension between sta-
bility and Pareto optimality (Roth, 1982a). If
III. Design Considerations
priorities are merely a device for allocating
scarce spaces, it might be possible to assign
Unlike in New York (Abdulkadirog˘lu et al.,
students to schools they prefer by allowing them
2005), students’ priorities at schools are not set
to trade their priority at one school with a stu-
by schools, but by the central administration.
dent who has priority at a school they prefer.
There does not seem to be any issue of individ-
The following top trading cycles (TTC) mech-
ual schools gaming the system in Boston.
anism creates a virtual exchange for priorities:
Therefore, it is natural to ask whether the ben-
efits that “stable” matching produces in New
Step 1.—Assign counters for each school to
York have parallel benefits in the different sit-
track how many seats remain available. Each
uation in Boston, and if not, whether the welfare
student points to her favorite school, and each
improvements that might be available from a
school points to the student with the highest
TTC-like mechanism should be considered.
priority. There must be at least one cycle. (A
At a public meeting of the Boston School
VOL. 95 NO. 2
PRACTICAL MARKET DESIGN
371
Committee in October 2004 we were asked for
School Match.” American Economic Review,
advice about how to think about this. We re-
2005 (Papers and Proceedings), 95(2), pp.
plied with the question “Would anyone mind if
364 – 67.
two students who each preferred the school in
Abdulkadirog˘lu, Atila and So¨nmez, Tayfun.
the other student’s walk zone were to trade their
“School Choice: A Mechanism Design Ap-
priorities and enroll in those schools?” If this is
proach.” American Economic Review, 2003,
not desirable (e.g., because of transportation
93(3), pp. 729 – 47.
costs, or because walk-zone priorities reflect a
Chen, Yan and So¨nmez, Tayfun. “School Choice:
public good that results when parents walk chil-
An Experimental Study.” Journal of Eco-
dren to school, or because lawsuits might follow
nomic Theory, 2005 (forthcoming).
if a child is excluded from a school while an-
Ergin, Haluk and So¨nmez, Tayfun. “Games of
other with lower priority is admitted), then sta-
School Choice under the Boston Mecha-
ble
matchings
would
efficiently
combine
nism.” Journal of Public Economics, 2005
student preferences with priorities. But if help-
(forthcoming).
ing the students this way is worth whatever
Gale, David and Shapley, Lloyd. “College Ad-
transportation and other costs might be in-
missions and the Stability of Marriage.”
curred, then only the students’ preferences need
American
Mathematical
Monthly,
1962,
to be taken into account and a TTC-like mech-
69(1), pp. 9 –15.
anism might be more appropriate.
Kesten, Onur. “Student Placement to Public
Schools in the US: Two New Solutions.”
IV. Recent Developments
Mimeo, University of Rochester, 2005.
Roth, Alvin E. “The Economics of Matching:
In December 2003, the Boston School Com-
Stability and Incentives.” Mathematics of
mittee initiated an evaluation of all aspects of
Operations Research, 1982, 7(4), pp. 617–
student assignment. The final task-force report
28.
recommends changing the student assignment
Roth, Alvin E. “Incentive Compatibility in a
algorithm. The task force observed that, even
Market with Indivisible Goods.” Economics
though students can select three schools, many
Letters, 1982b, 9(2), pp. 127–32.
children do not get any of their picks because, if
Roth, Alvin E. “A Natural Experiment in the
a parent and student choose three popular
Organization of Entry-Level Labor Markets:
schools and do not get their first choice, they
Regional Markets for New Physicians and
may also miss their second and third choice.
Surgeons in the United Kingdom.” American
A memorandum from Superintendent Payzant
Economic Review, 1991, 81(3), pp. 414 – 40.
in December 2004 states that BPS plans to
Roth, Alvin E. “The Economist as Engineer:
change the computerized process used to assign
Game Theory, Experimental Economics and
students to schools. Although the task-force re-
Computation as Tools of Design Econom-
port recommended that BPS adopt the TTC
ics.” Econometrica, 2002, 70(4), pp. 1341–
assignment algorithm, the School Committee is
78.
interested in simulations of both mechanisms
Roth, Alvin E.; So¨nmez, Tayfun and U
¨ nver, M.
and in understanding the extent of preference
Utku. “Kidney Exchange.” Quarterly Journal
manipulation under the Boston mechanism.
of Economics, 2004, 119(2), pp. 457– 88.
They are also thinking through their philosoph-
Roth, Alvin E.; So¨nmez, Tayfun and U
¨ nver, M.
ical position on the trade-off between stability
Utku. “A Kidney Exchange Clearinghouse in
and efficiency.
New England.” American Economic Review,
2005 (Papers and Proceedings), 95(2), pp.
REFERENCES
376 – 80.
Shapley, Lloyd and Scarf, Herbert. “On Cores
Abdulkadirog˘lu, Atila; Pathak, Parag A. and
and Indivisibility.” Journal of Mathematical
Roth, Alvin E. “The New York City High
Economics, 1974, 1(1), pp. 23–28.

Document Outline