Thursday, June 16, 2011

The daycare assignment problem

Assigning people with heterogeneous preference to medical residency, schools, job candidates or marital partners is a difficult problem, and with the help of the work of Al Roth, we have made much progress in finding optimal systems. More and more situations are uncovered that required a special analysis because some feature requires rethinking the whole process.

John Kennes, Daniel Monte and Norovsambuu Tumennasan study assignments of toddlers in daycares as applied in Denmark. It is special because if the overlapping generation nature of daycares, and the fact that some children get preferential treatment (like previous attendees and siblings). The usual Gale-Shapley algorithm appears to be Pareto-optimal, at least among stable matching algorithms, as in simpler setups, but it is unfortunately not strategy proof and does not Pareto dominate all strongly stable algorithms. For once, another assignment mechanism seems to perform better. But I wonder what would happen when there is rationing in daycares, as is typically the case.

No comments: