权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

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

高效匹配、持续投票、关键信息不可承包

基本信息

批准号：
2049810
负责人：
Philip Reny
金额：
$ 15万
依托单位：
University of Chicago
依托单位国家：
美国
项目类别：
Standard Grant
财政年份：
2021
资助国家：
美国
起止时间：
2021-08-01 至 2024-07-31
项目状态：
已结题

来源：
https://www.nsf.gov/awardsearch/showAward?AWD_ID=2049810&HistoricalAwards=false
关键词：
Efficient Matching Continuous Voting Non

项目摘要

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.

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