Fragile Stable Matchings
This paper shows the fragility of stable matchings in a decentralized one-to-one matching setting. The classical work of Roth and Vande Vate (1990) suggests simple decentralized dynamics in which randomly-chosen blocking pairs match successively. Such decentralized interactions guarantee convergence to a stable matching. Our first theorem shows that, under mild conditions, any unstable matching—including a small perturbation of a stable matching—can culminate in any stable matching through these dynamics. Our second theorem highlights another aspect of fragility: stabilization may take a long time. Even in markets with a unique stable matching, where the dynamics always converge to the same matching, decentralized interactions can require an exponentially long duration to converge. A small perturbation of a stable matching may lead the market away from stability and involve a sizable proportion of mismatched participants for extended periods.
Kirill Rudov is a final-year Ph.D. candidate in the Department of Economics at Princeton University. His research is in microeconomic theory, with a focus on market design and robustness.