Patients needing kidney transplants may have donors who cannot donate to them because of blood or tissue incompatibility. Incompatible patient-donor pairs can exchange donor kidneys with other pairs only when there is a "double coincidence of wants." Developing infrastructure to perform three-way as well as two-way exchanges will have a substantial effect on the number of transplants that can be arranged. Larger than three-way exchanges have less impact on efficiency. In a general model of type-compatible exchanges, the size of the largest exchanges required to achieve efficiency equals the number of types.

In 2003 there were 8,665 transplants of deceased donor kidneys for the approximately 60,000 patients waiting for such transplants in the United States. While waiting, 3,436 patients died. There were also 6,464 kidney transplants from living donors (Scientific Registry of Transplant Recipients web site). Live donation is an option for kidneys, since healthy people have two and can remain healthy with one. While it is illegal to buy or sell organs, there have started to be kidney exchanges involving two donor–patient pairs such that each (living) donor cannot give a kidney to the intended recipient because of blood type or immunological incompatibility, but each patient can receive a kidney from the other donor. So far these have been rare: as of December 2004, only five exchanges had been performed in the 14 transplant centers in New England. One reason there have been so few kidney exchanges is that there have not been databases of incompatible patient–donor pairs. Incompatible donors were simply sent home. (Databases are now being assembled not only in New England, but also in Ohio and Baltimore.) Lainie Friedman Ross et al. (1997) discussed the possibility of exchange between incompatible patient–donor pairs. Not only have a few such two-way exchanges been performed, but two three-way exchanges (in which the donor kidney from one pair is transplanted into the patient in a second pair, whose donor kidney goes to a third pair, whose donor kidney goes to the first pair) have been performed at Johns Hopkins. There have also been a number of “list exchanges” in which an incompatible patient– donor pair makes a donation to someone on the waiting list for a cadaver kidney, in return for the patient in the pair receiving high priority for a cadaver kidney when one becomes available.

mechanism to match over 90,000 entering students to public high schools each year. This paper makes a very preliminary report on the design process and the first year of operation, in academic year 2003-04, for students entering high school in Fall 2004. In the first year, only about 3,000 students had to be assigned to a school for which they had not indicated a preference, which is only 10 % of the number of such assignments the previous year. New York City has the largest public school system in the country, with over a million students. In 1969 the system was decentralized into over thirty community school districts. In the 1990s, the city began to take more centralized control, and in 2002, a newly reorganized NYCDOE began to reform many aspects of the school system. In May 2003, Dr. Jeremy Lack, then the NYCDOE Director of Strategic Planning, contacted one of us for advice on designing a new high school matching process. The NYCDOE was aware of the matching process for American physicians, the National Resident Matching Program (Roth 1984; Roth and Peranson 1999). They wanted to know if it could be appropriately adapted to the city’s schools. The three authors of the present paper (and, at several crucial junctures, also Tayfun Sönmez) advised (and often convinced) Dr.

After the publication of “School Choice: A Mechanism Design Approach” by Abdulkadiroglu and Sonmez (2003), a Boston Globe reporter 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 1999 BPS eliminated racial preferences in assignment and adopted the current mechanism.