Stable Matching with Dynamic Priorities

We study the problem of finding a stable matching under adaptive priorities, whereby the clearinghouse prioritizes some agents based on the allocation of others, and we use school choice as a motivating example. To accomplish this, we introduce a stylized model of a two-sided matching market with siblings’ priorities. We argue that the standard notion of stability does not apply in the presence of adaptive priorities. To address this, and motivated by practice, we define several assumptions on families’ preferences and siblings’ priorities, introduce different notions of stability under adaptive priorities, and show that a stable matching under these settings may not exist. On the positive side, we show that such matchings exist if families strictly prefer their members to remain together in two important settings: (i) when families are of size at most two, and (ii) when there is a single grade level. In addition, we devise a mechanism to find such stable assignments in polynomial time. Finally, we show that the problem of finding the stable matching under adaptive priorities of maximum cardinality is NP-Hard.