Leximin Allocations in the Real World
November 4, 2015

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. Previous work showed that in a much simpler domain, the leximin mechanism is proportional, envy-free, efficient, and group strategyproof. We extend this result to a broad domain that not only subsumes our classroom allocation setting, but also a number of other settings studied in the literature. Consequently, our work generalizes various results from resource allocation, cake-cutting, and kidney exchange. We provide worst-case guarantees regarding the performance of the leximin mechanism with respect to two natural quantitative objectives. Our experiments, which are based on real data, show that the performance in practice is significantly better than the worst-case guarantees. Our nontrivial implementation of the leximin mechanism scales gracefully in terms of running time (even though the problem is intractable in theory). At the end of the talk, I will discuss issues related to the deployment of our approach.

This is joint work with David Kurokawa and Ariel D. Procaccia.