Fragile Stable Matchings
We show how fragile stable matchings are 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. Our results hold for a broad class of dynamics.
Code (0)
등록된 구현이 없습니다.
Tasks
BlockingSimilar Papers 제목 키워드 기반
Matching markets with farsighted couples
We adopt the notion of the farsighted stable set to determine which matchings are stable when agents are farsighted in matching markets with couples. We show that a singleton matching is a farsighted stable set if and on…
Priority-Neutral Matching Lattices Are Not Distributive
Stable matchings are a cornerstone of market design, with numerous practical deployments backed by a rich, theoretically-tractable structure. However, in school-choice problems, stable matchings are not Pareto optimal fo…
On the many-to-one strongly stable fractional matching set
For a many-to-one matching market where firms have strict and $\boldsymbol{q}$-responsive preferences, we give a characterization of the set of strongly stable fractional matchings as the union of the convex hull of all …
AllFinding all stable matchings with assignment constraints
In this paper we consider stable matchings subject to assignment constraints. These are matchings that require certain assigned pairs to be included, insist that some other assigned pairs are not, and, importantly, are s…
AllThe lattice of worker-quasi-stable matchings
In a many-to-one matching model in which firms' preferences satisfy substitutability, we study the set of worker-quasi-stable matchings. Worker-quasi-stability is a relaxation of stability that allows blocking pairs invo…
Blocking