Efficient Matching, Continuous Voting, and Non-Contractable Critical Information

Many U.S. cities (including New York City, Boston, Seattle, Cambridge, Charlotte, Denver, Minneapolis, and Columbus) allow families to choose a school for their children that is outside the district in which they live. Because there may not be enough seats at any given school to accommodate all students for whom that school is their first choice, school districts use priority rules together with randomly assigned lottery numbers to resolve the conflicts that inevitably arise.

For example, in many New York City (NYC) public schools, children in a school's predefined geographic zone have priority over all children outside that zone, and children with a sibling already enrolled at the school have priority over children who are outside the school’s zone and who do not have a sibling enrolled at the school. There are other priorities as well.

Any conflicts between students in the same priority group are resolved according to each student’s randomly assigned lottery number. In NYC, each student can list up to 12 schools on their application in the order of their preference. After all students have submitted their ranked lists to the department of education, a computer algorithm matches each student to the school that is as high as possible on the student’s list subject to maintaining consistency with all school priorities and the randomly assigned lottery numbers.

This same algorithm is in fact used in many other cities as well. Now, while this algorithm does perform its designated task, it can nevertheless fail to make students as well off as possible. For example, according to a study conducted by Abdulkadiroglu, Pathak, and Roth (2009), in a New York City school district in 2006-2007, over 4,000 grade 8 students could have been made better off by reassigning them to a school different than their match according to the matching algorithm, without changing any other student’s assigned school.

The problem is not with the algorithm itself. Indeed, the algorithm performs precisely as intended. The problem is that school priorities sometimes unintentionally take precedence over student well-being.

Indeed, the reason that the algorithm was not allowed to match those 4000 students to their preferred schools is that their preferred placements would have violated the priorities of students whose matches would have been unaffected by the changes. So in this case, the rigidity of school priorities implicitly took precedence over the well-being of those 4000 students.

We offer here a more holistic view of school priorities that places limits on their use by students to object against a status quo. Adopting the resulting matching method proposed here never makes any student worse off than they would have been under the current system and will typically make many students better off---like the 4000 NYC students above.

More technically, say that a matching (of students to schools) A blocks a matching B if ne makes better off a student whose priority is violated by B without making worse off any student whose priority is violated by A. This notion of blocking captures a student’s right to seek relief from a priority violation by finding a preferred matching, so long as it would not be vetoed by a student whose priority it violates.

Say that a matching B is priority-neutral if it is unblocked. We seek matchings that are both priority-neutral and Pareto efficient: we call such matchings priority-efficient. We will establish that priority-efficient matching always exist and are unique for every school-choice problem.

Moreover, among all priority-neutral matchings the priority-efficient matching is weakly preferred by all students. Since all stable matching are priority-neutral, this implies that all students weakly prefer the priority-efficient matching to the stable matching. Thus no student is ever made worse off, and many will be made better off, under the priority-efficient matching versus the stable matching for any school-choice problem.

This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.