Leximin Allocations in the Real World
Leximin Allocations in the Real World
复制标题
DOI：
10.1145/3274641
复制
发表时间：
2018-11-01
影响因子：
1.2
通讯作者：
Shah, Nisarg
中科院分区：
文献类型：
--
作者：
Kurokawa, David;Procaccia, Ariel D.;Shah, Nisarg
作为与加州一个主要学区合作的一部分，我们研究了将公立学校闲置的教室公平分配给特许学校的问题。我们的方法围绕随机leximin机制。我们扩展以前的工作表明，leximin机制是成比例的，无嫉妒，帕累托最优，组strategyproof，不仅在我们的教室分配设置，但在一个一般的框架，包括一些设置以前在文献中研究。我们还证明了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 show that the leximin mechanism is proportional, envy-free, Pareto optimal, and group strategyproof, not only in our classroom allocation setting, but in a general framework that subsumes a number of settings previously studied in the literature. 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 non-trivial 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 establish the practicability of our approach, and discuss issues related to its deployment.