School assignment as viewed by families over time, when sibs are given priority

As I've noted before, demand for pre-kindergarten increases when pre-k kids are guaranteed spots at kindergarten, since it gives families a way to increase their chances in the school choice game. That is, families can change their priority at the kindergarten they want if they succeed in enrolling their child in that school's pre-k.

Two recent papers model some of the timing issues facing families thinking about school (or daycare) placement, when there are preferences for incumbent students, and the siblings of incumbent students. Needless to say, mechanisms that are strategy proof for static choice problems are no longer strategy proof when the strategy sets are expanded to take account of the dynamic problem. Both papers will be presented at the July 11 - 15, 2011: International Conference on Game Theory at Stony Brook.

The papers are:

The Daycare Assignment Problem, by John Kennes, Daniel Monte and, Norovsambuu Tumennasan
(HT: EL)

Abstract

"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 different points in time. Moreover, schools' priorities are history-dependent: a school gives priority to children currently enrolled to 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 satisfies 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, due to the overlapping generations structure of the problem, the also well known Top Trading Cycles algorithm is neither Pareto efficient nor strategy-proof. We conclude by showing that a variation of the serial dictatorship is strategy-proof and efficient.

and

Dynamic School Choice by Umut Dur, a student at UT Austin, who I heard in Montreal...
Abstract:
"Both families and public school systems desire siblings to be assigned to the same school. Although students with siblings at the school have a higher priority than students who do not, public school systems do not guarantee sibling assignments. Hence, families with more than one child may need to misstate their preferences if they want their children to attend to the same school. In this paper, we study the school choice problem in a dynamic environment where some families have two children and their preferences and priority orders for the younger child depend on the assignment of the elder one. In this dynamic environment, we introduce a new mechanism which assign siblings to the best possible school together if parents desire them to attend the same school. We also introduce a new dynamic fairness notion which respects priorities in a dynamic sense. Finally, we show that it is possible to attain welfare gains when school choice problem is considered in a dynamic environment."


Jacob Leshno, who will be at the Stony Brook conference, writes to me about these papers as follows.


"The incentive problems in the daycare problem are akin to the incentive problems of the Boston mechanism. In the Boston mechanism changing your report changes your priority (the Boston mechanism is equivalent to DA where priorities are changed so students who ranked a school as their k-th choice get higher priority than student who rank the school > k). In the daycare problem your report changes your priority since priorities are history dependent (for example, kids are guaranteed to be allowed to stay where they first got admitted). Misreporting preferences to get a more advantageous priority can be a profitable manipulation, and these manipulations will probably still persist even when the market becomes large."