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 $M_1$ 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 $M_2$. As it is undesirable to change
assignments, the goal is to minimize the number of divorces/modifications
between the two stable matchings $M_1$ and $M_2$. Then, how should we choose
$M_1$ and $M_2$? 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 $M_1$ 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.

实现一个可实现在线算法，并通过该算法最小化两种稳定匹配之间的更改和离婚数量，该算法适用于大学招生和稳定匹配优化问题。