# Online 2-stage Stable Matching

arXiv: https://arxiv.org/abs/2207.02057 · HTML: https://mlsanity.com/paper/2207.02057/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 7 of its 29 references that are in the map.
- First posted on arXiv 5 Jul 2022.

## Builds on (most cited first, 7 of 7)

- [Adapting Stable Matchings to Evolving Preferences](https://mlsanity.com/paper/1907.01375/) (2019)
- [Changing Bases: Multistage Optimization for Matroids and Matchings](https://mlsanity.com/paper/1404.3768/) (2014)
- [Finding Robust Solutions to Stable Marriage](https://mlsanity.com/paper/1705.09218/) (2017)
- [Online Multistage Subset Maximization Problems](https://mlsanity.com/paper/1905.04162/) (2019)
- [Stable Matching with Evolving Preferences](https://mlsanity.com/paper/1509.01988/) (2015)
- [The Dynamics of Rank-Maximal and Popular Matchings](https://mlsanity.com/paper/1703.10594/) (2017)
- [A Natural Generalization of Stable Matching Solved via New Insights into Ideal Cuts](https://mlsanity.com/paper/1802.06621/) (2018)

## Built on by (most cited first, 1 of 1)

- [Online Housing Market](https://mlsanity.com/paper/2501.15916/) (2025)

## Abstract (arXiv)

We focus on an online 2-stage problem, motivated by the following situation: consider a system where students shall be assigned to universities. There is a first round where some students apply, and a first (stable) matching M1 has to be computed. However, some students may decide to leave the system (change their plan, go to a foreign university, or to some institution not in the system). Then, in a second round (after these deletions), we shall compute a second (final) stable matching M2. As it is undesirable to change assignments, the goal is to minimize the number of divorces/modifications between the two stable matchings M1 and M2. Then, how should we choose M1 and M2? We show that there is an it optimal online algorithm to solve this problem. In particular, thanks to a dominance property, we show that we can optimally compute M1 without knowing the students that will leave the system. We generalize the result to some other possible modifications in the input (students, open positions). We also tackle the case of more stages, showing that no competitive (online) algorithm can be achieved for the considered problem as soon as there are 3 stages.