(Il)legal Assignments in School Choice

Abstract

In public school choice, students with strict preferences are assigned to schools. Schools are endowed with priorities over students. Incorporating different constraints from applications, priorities are often modeled as choice functions over sets of students. It has been argued that the most desirable criterion for an assignment is fairness; there should not be a student having justified envy in the following way: he prefers some school to his assigned school and has higher priority than some student who got into that school. Justified envy could cause court cases. We propose the following fairness notion for a set of assignments: a set of assignments is legal if and only if any assignment outside the set has justified envy with some assignment in the set and no two assignments inside the set block each other via justified envy. We show that under very basic conditions on priorities, there always exists a unique legal set of assignments, and that this set has a structure common to the set of fair assignments: (i) it is a lattice and (ii) it satisfies the rural-hospitals theorem. This is the first contribution providing a "set-wise" solution for many-to-one matching problems where priorities are not necessarily responsive and schools are not active agents.