Itai Ashlagi and Peng Shi have a paper motivated by some of the recent discussions of school choice in Boston:
Improving Community Cohesion in School Choice via Correlated-Lottery Implementation
Itai Ashlagi and Peng Shi
Draft Date: August 6, 2013
Abstract:
In school choice, children submit a preference ranking over schools to a centralized assignment algorithm, which takes into account schools’ priorities over children and uses randomization to break ties. One criticism of current school choice mechanisms is that they tend to disperse communities so children do not go to school with others from their neighborhood.
We suggest to improve community cohesion by implementing a correlated lottery in a given school choice mechanism: we find a convex combination of deterministic assignments that maintains the original assignment probabilities, thus maintaining choice, but yields increased cohesion.
To analyze the gain in cohesion for a wide class of mechanisms, we first prove the following characterization which maybe of independent interest: any mechanism which, in the large market limit, is non-atomic, Bayesian incentive compatible, symmetric and efficient within each priority class, is a “lottery-plus-cutoff” mechanism. This means that the large market limit can be described as follows: given the distribution of preferences, every student receives an identically distributed lottery number, every school sets a lottery cutoff for each priority class, and a student is assigned her most preferred school for which she meets the cutoff. This generalizes Liu and Pycia (2012) to allow arbitrary priorities. Using this, we derive analytic expressions for maximum cohesion under a large market approximation. We show that the benefit of lottery-correlation is greater when students’ preferences are more correlated.
In practice, although the correlated-lottery implementation problem is NP-hard, we present a heuristic that does well. We apply this to real data from Boston elementary school choice 2012 and find that we can increase cohesion by 79% for K1 and 37% for K2 new families. Greater cohesion gain is possible (tripling cohesion for K1 and doubling for K2) if we apply lottery-correlation on top of reducing the choice menu (to what was eventually adopted by Boston after the 2012-2013 school choice reform). This has minimal impact on racial or socio-economic diversity.
Improving Community Cohesion in School Choice via Correlated-Lottery Implementation
Itai Ashlagi and Peng Shi
Draft Date: August 6, 2013
Abstract:
In school choice, children submit a preference ranking over schools to a centralized assignment algorithm, which takes into account schools’ priorities over children and uses randomization to break ties. One criticism of current school choice mechanisms is that they tend to disperse communities so children do not go to school with others from their neighborhood.
We suggest to improve community cohesion by implementing a correlated lottery in a given school choice mechanism: we find a convex combination of deterministic assignments that maintains the original assignment probabilities, thus maintaining choice, but yields increased cohesion.
To analyze the gain in cohesion for a wide class of mechanisms, we first prove the following characterization which maybe of independent interest: any mechanism which, in the large market limit, is non-atomic, Bayesian incentive compatible, symmetric and efficient within each priority class, is a “lottery-plus-cutoff” mechanism. This means that the large market limit can be described as follows: given the distribution of preferences, every student receives an identically distributed lottery number, every school sets a lottery cutoff for each priority class, and a student is assigned her most preferred school for which she meets the cutoff. This generalizes Liu and Pycia (2012) to allow arbitrary priorities. Using this, we derive analytic expressions for maximum cohesion under a large market approximation. We show that the benefit of lottery-correlation is greater when students’ preferences are more correlated.
In practice, although the correlated-lottery implementation problem is NP-hard, we present a heuristic that does well. We apply this to real data from Boston elementary school choice 2012 and find that we can increase cohesion by 79% for K1 and 37% for K2 new families. Greater cohesion gain is possible (tripling cohesion for K1 and doubling for K2) if we apply lottery-correlation on top of reducing the choice menu (to what was eventually adopted by Boston after the 2012-2013 school choice reform). This has minimal impact on racial or socio-economic diversity.