When groups of schools within a single district run their admission processes independently of one another, the resulting match is often inefficient: many children are left unmatched and seats are left unfilled.
We study the problem of re-matching students to take advantage of these empty seats in a context where there are priorities to respect. We propose an iterative way in which each group may independently match and re-match students to its schools.
The advantages of this process are that every iteration leads to a Pareto improvement and a reduction in waste while maintaining respect of the priorities. Furthermore, it reaches a non-wasteful match within a finite number of iterations.
While iterating may be costly, as it involves asking for inputs from the children, there are significant gains from the first few iterations. We show this analytically for certain stylized problems and computationally for a few others.
Vikram Manjunath