Description:
<jats:p>
As part of a collaboration with a major California school district, we study the problem of
<jats:italic>fairly</jats:italic>
allocating unused classrooms in public schools to charter schools. Our approach revolves around the randomized
<jats:italic>leximin mechanism</jats:italic>
. 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.
</jats:p>