Seminar: Daniel Monte, Simon Fraser University.

Title: The Daycare Assignment Problem.

In this paper we introduce and study the daycare assignment problem. We take the mechanism design approach to the problem of assigning children of different ages to daycares, motivated by the mechanism currently in place in Denmark. The dynamic features of the daycare assignment problem distinguishes it from the school choice problem. For example, the children's preference relations must include the possibility of waiting and also the different combinations of daycares in diff erent points in time. Moreover, schools' priorities are history-dependent: a school gives priority to children currently enrolled in it, as is the case with the Danish system.

First, we study the concept of stability, and to account for the dynamic nature of the problem, we propose a novel solution concept, which we call strong stability. With a suitable restriction on the priority orderings of schools, we show that strong stability and the weaker concept of static stability will coincide. We then extend the well known Gale-Shapley deferred acceptance algorithm for dynamic problems and we prove that it yields a matching that satisfi es strong stability. We show that it is not Pareto dominated by any other matching, and that, if there is an efficient stable matching, it must be the Gale-Shapley one. However, contrary to static problems, the Gale-Shapley algorithm does not necessarily Pareto dominate all other strongly stable mechanisms. Most importantly, the Gale-Shapley algorithm is not strategy-proof. In fact, one of our main results is a much stronger impossibility result: for the class of dynamic matching problems that we study, there are no algorithms that satisfy strategy-proofness and strong stability.

Second, we show that the also well known top trading cycles algorithm is Pareto efficient, as was the case with static problems. However, again, strategy-proofness fails. We conclude by showing that a variation of the serial dictatorship is strategy-proof and efficient.