Leximin Allocations in the Real World
Leximin Allocations in the Real World
复制标题
DOI：
10.1145/2764468.2764490
复制
发表时间：
2015-06
期刊：
影响因子：
--
通讯作者：
David Kurokawa;Ariel D. Procaccia;Nisarg Shah
中科院分区：
文献类型：
--
作者：
David Kurokawa;Ariel D. Procaccia;Nisarg Shah
作为与加利福尼亚主要学区合作的一部分，我们研究了将公立学校中未使用的教室分配给特许学校的问题。我们的方法围绕着随机溶血机制。我们将先前的工作扩展到课堂分配设置，表明词汇机制是比例，无嫉妒，高效和群体策略性的。我们还证明，Leximin机制为可能分配的最大教室数量提供了（最坏的）4-附属方式。我们的实验基于实际数据，表明leximin机制的非平凡实现在运行时间方面优雅地扩展了（即使问题在理论上很棘手），并且在许多效率目标方面表现出色。我们竭尽全力建立我们的方法的实用性，并讨论与其部署有关的问题。
As part of a collaboration with a major California school district, we study the problem of fairly allocating unused classrooms in public schools to charter schools. Our approach revolves around the randomized leximin mechanism. We extend previous work to the classroom allocation setting, showing that the leximin mechanism is proportional, envy-free, efficient, and group strategyproof. We also prove that the leximin mechanism provides a (worst-case) 4-approximation to the maximum number of classrooms that can possibly be allocated. Our experiments, which are based on real data, show that a nontrivial implementation of the leximin mechanism scales gracefully in terms of running time (even though the problem is intractable in theory), and performs extremely well with respect to a number of efficiency objectives. We take great pains to establish the practicability of our approach, and discuss issues related to its deployment.