On the Existence of Stable Roommate Matchings

This paper identifies a condition called “no odd rings” that is sufficient for the existence of stable roommate matchings in the weak preferences case. It shows that the process of allowing randomly chosen blocking pairs to match converges to a stable roommate matching with probability one as long as there are no odd rings. This random-paths-to-stability result generalizes that of Roth and Vande Vate (1990, Econometrica58, 1475–1480) and may not hold if there are odd rings. The “no odd rings” condition can also be used to prove a number of other sufficient conditions that are more economically interpretable. Journal of Economic Literature Classification Numbers: C78, D71.