Using school choice as a motivating example, we introduce a stylized model of a many-to-one matching market where the clearinghouse seeks to implement contingent priorities—i.e., priorities that depend on the current assignment—to improve the likelihood that students with siblings are assigned together. We provide a series of guidelines and introduce two natural approaches to implement them: (i) absolute, whereby a prioritized student can displace any student without siblings assigned to the school, and (ii) partial, whereby prioritized students can only displace students that have a less favorable lottery than their priority provider. We study several properties of the corresponding mechanisms, including the existence of a stable assignment under contingent priorities, the complexity of finding one if it exists, and its incentive properties. Furthermore, we introduce a soft version of these priorities to guarantee existence, and we provide mathematical programming formulations to find such stable matching or certify that one does not exist. Finally, using data from the Chilean school choice system, we show that our framework can significantly increase the number of students assigned to their top preference and the number of siblings assigned together relative to current practice. A full version of this paper can be found at https://arxiv.org/abs/2409.04914

Centralized mechanisms are becoming the standard approach to solve several assignment problems. Examples include the allocation of students to schools (school choice), high-school graduates to colleges, residents to hospitals and refugees to cities. In most of these markets, a desirable property of the assignment is stability, which guarantees that no pair of agents has incentive to circumvent the matching. Using school choice as our matching market application, we introduce the problem of jointly allocating a school capacity expansion and finding the best stable matching for the students in the expanded market. We analyze theoretically the problem, focusing on the trade-off behind the multiplicity of student-optimal assignments, and the problem complexity. Since the theoretical intractability of the problem precludes the adaptation of classical approaches to solve it efficiently, we generalize existent mathematical programming formulations of stability constraints to our setting. These generalizations result in integer quadratically-constrained programs, which are computationally hard to solve. In addition, we propose a novel mixed-integer linear programming formulation that is exponentially-large on the problem size. We show that the stability constraints can be separated in linear time, leading to an effective cutting-plane method. We evaluate the performance of our approaches in a detailed computational study, and we find that our cutting-plane method outperforms mixed-integer programming solvers applied to existent formulations extended to our problem setting. We also propose two heuristics that are effective for large instances of the problem. Finally, we use the Chilean school choice system data to demonstrate the impact of capacity planning under stability conditions. Our results show that each additional school seat can benefit multiple students. On the one hand, we can focus on access by prioritizing extra seats that benefit previously unassigned students; on the other hand, we can focus on merit by allocating extra seats that benefit several students via chains of improvement. These insights empower the decision-maker in tuning the matching algorithm to provide a fair application-oriented solution.

Motivated by our collaboration with a major US online dating company, we study how a platform should dynamically select the set of potential partners to show to each user in each period to maximize the expected number of matches in a time horizon, considering that a match is formed only after two users like each other, possibly in different periods. Increasing match rates is a prevalent objective among online platforms. We provide insights on how to leverage users? preferences and behavior towards this end. Our proposed algorithm was piloted by our collaborator in major cities in the US. We introduce a model of a dynamic matching market mediated by a platform. The platform hosts a set of users and must decide, in each period, what subset of profiles to show to each user to maximize the overall expected number of matches. Each period, users log in with some time-dependent probability and, conditional on logging in, observe a set of profiles-an assortment-that satisfies the constraints imposed by the platform. Then, users decide whether to like or not like each profile in their assortment based on their preferences. If two users mutually like each other, possibly in different periods, a match is generated. Our goal is to find an algorithm to maximize the total expected number of matches generated by the platform over an entire time horizon. We show that the platform's problem is computationally hard.