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

许多美国城市（包括纽约市、波士顿、西雅图、剑桥、夏洛特、丹佛、明尼阿波利斯和哥伦布）允许家庭为他们的孩子选择一所他们居住的地区以外的学校。因为任何一所学校都可能没有足够的座位来容纳所有作为第一选择的学生，学区使用优先规则和随机分配的彩票号码来解决不可避免地出现的冲突。例如，在纽约市（NYC）的许多公立学校中，学校预定义地理区域内的孩子比该区域外的所有孩子都有优先权，已经在学校注册的兄弟姐妹的孩子比已经在学校注册的兄弟姐妹的孩子有优先权。还有其他优先事项。同一优先级组的学生之间的任何冲突都根据每个学生随机分配的彩票号码来解决。在纽约，每个学生可以按照自己的喜好顺序在申请表上列出最多12所学校。在所有学生向教育部门提交排名表后，计算机算法将每个学生与学生名单上尽可能高的学校进行匹配，以保持所有学校优先级和随机分配的彩票号码的一致性。事实上，同样的算法也在许多其他城市使用。现在，虽然这个算法确实执行了它指定的任务，但它仍然不能使学生尽可能地富裕。例如，根据Abdulkadiroglu， Pathak和Roth（2009）在2006-2007年在纽约市学区进行的一项研究，如果根据匹配算法将4000多名8年级学生重新分配到与他们匹配的学校不同的学校，而不改变任何其他学生分配的学校，他们的生活就会变得更好。问题不在于算法本身。事实上，该算法完全按照预期执行。问题是，学校的优先考虑有时会无意中优先于学生的福祉。事实上，该算法不允许将这4000名学生与他们喜欢的学校相匹配的原因是，他们喜欢的学校会违反那些匹配不受变化影响的学生的优先级。所以在这种情况下，学校优先级的刚性隐含地优先于这4000名学生的福祉。我们在这里提供了一个更全面的学校优先级视图，限制学生使用它们来反对现状。采用这里提出的匹配方法不会让任何学生的情况比他们在现行制度下的情况更糟，而且通常会让许多学生的情况变得更好——就像上面提到的4000名纽约学生一样。更严格地说，假设（学生与学校的）匹配a阻止了匹配B，如果a使优先级被B违反的学生得到更好的待遇，而没有使优先级被a违反的学生得到更坏的待遇。这种阻止的概念抓住了学生通过寻找优先级被违反的学生来寻求救济的权利，只要它不会被优先级被违反的学生否决。假设匹配的B是优先级中立的，如果它是未阻塞的。我们寻找优先级中立和帕累托有效的匹配：我们称这种匹配为优先级高效匹配。我们将确保优先级高效匹配始终存在，并且对于每个择校问题都是独一无二的。此外，在所有优先级无关的匹配中，所有学生都弱偏好优先级有效的匹配。由于所有稳定匹配都是优先级中立的，这意味着所有学生都弱倾向于优先级有效的匹配而不是稳定匹配。因此，在择校问题的优先级有效匹配与稳定匹配下，没有学生的情况变得更糟，而且许多学生的情况会变得更好。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

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.