The dynamics of stable matchings and half-matchings for the stable marriage and roommates problems (Q2482674)

This paper studies the dynamics of stable marriage and stable roommates markets. The main tool of this paper is the algorithm of Roth and Vande Vate and its generalization by Tan and Hsueh. Beyond proposing alternative proofs for known results, some of them are generalized to the nonbipartite case. In particular, it is shown that the lastcomer gets his best stable partner in both algorithms. Consequently, it is better to arrive later than earlier to a stable rommates market. This paper also proves that when the equilibrium is restored after the arrival of a new agent, some agents will be better off under any stable solution for the new market than at any stable solution for the original market. A procedure to find these agents is proposed.