Stable Roommates ist die Variante des Stable-Matching-Problems ohne Zweiteilung: Eine gerade Anzahl von Personen (zum Beispiel Zimmergenossen) bewertet alle anderen Personen, und gesucht ist eine Paarung ohne Blockierungspaare — kein Paar darf einander gegenüber den zugewiesenen Partnern vorziehen. Anders als beim Stable-Marriage-Problem gibt es hier keine zwei getrennten Gruppen.
Der Unterschied zum Heiratsproblem
Im Heiratsproblem existiert dank Gale und Shapley immer eine stabile Paarung. Beim Stable Roommates ist das nicht der Fall: Schon bei vier Personen mit zyklischen Präferenzen (jede bevorzugt die nächste, diese wieder eine andere) lässt sich keine stabile Aufteilung finden. Das Problem ist damit strukturell schwieriger, obwohl die Aufgabenstellung nur minimal anders klingt.
Der Irving-Algorithmus
Robert Irving beschrieb 1985 einen Algorithmus, der in O(n²) Zeit eine stabile Paarung findet — oder korrekt feststellt, dass keine existiert. Das Verfahren arbeitet in zwei Phasen: Zuerst erzeugt eine Vorschlagsrunde eine reduzierte Präferenzliste (jede Person behält den besten Partner, der sie angenommen hat), danach werden Zyklen in den verbleibenden Listen aufgelöst, um Blockierungspaare zu eliminieren. Existiert eine stabile Paarung, ist das Ergebnis für alle Beteiligten das bestmögliche unter den stabilen Lösungen.
Anwendungen
Stable Roommates löst Zuordnungen innerhalb einer einzigen Gruppe: Zimmervergabe in Wohngemeinschaften und Studentenheimen, Tauschbörsen (Wer möchte was von wem?), Peer-Assignments und die Bildung von Tandems in Lernprogrammen. Modelliert wird die Situation als vollständiger ungerichteter Graph auf einer Knotenmenge, in dem jede Kante eine potenzielle Paarung darstellt — eine bewusste Abgrenzung zum bipartiten Graphen, der das Heiratsproblem beschreibt.