(Il)legal Assignments In School Choice

摘要

In public school choice, students with strict preferences are assigned to schools. Schools are endowed with priorities over students. Incorporating constraints from different applications, priorities are often modelled as choice functions over sets of students. It has been argued that the most desirable criterion for an assignment is stability; there should not exist any blocking pair: no student shall prefer some school to her assigned school and have higher priority than some student who got into that school or the school has an empty seat. We propose a blocking notion where in addition it must be possible to assign the student to her preferred school. We then define the following stability criterion for a set of assignments: a set of assignments is legal if and only if any assignment outside the set is blocked with some assignment in the set and no two assignments inside the set block each other. 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 stable assignments: (i) it is a lattice and (ii) it satisfies the rural hospitals theorem. The student-optimal legal assignment is efficient and provides a solution for the conflict between stability and efficiency.