Abstract(s)
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.