Stable Roommates Problem

In der Mathematik, den Wirtschaftswissenschaften und der Informatik, insbesondere in den Bereichen Kombinatorik, Spieltheorie und Algorithmen, ist das Stable Roommate Problem (SRP) das Problem, ein stabiles Matching für eine gerade Menge zu finden. Ein Matching ist eine Trennung der Menge in disjunkte Paare ("Mitbewohner"). Das Matching ist „stabil“, wenn es keine zwei Elemente gibt, die keine Mitbewohner sind und sich unter dem Matching gegenseitig ihrem Mitbewohner vorziehen. Dies unterscheidet sich vom Stable Marriage Problem dadurch, dass das Stable Roommate Problem das Matching von zwei beliebigen Elementen erlaubt, nicht nur zwischen den Klassen „Männer“ und „Frauen“.

Es wird allgemein beschrieben als:

In einem bestimmten Fall des Stable Roommate Problems (SRP) ordnet jeder der 2n Teilnehmer die anderen in eine strikte Präferenzordnung. Ein Matching ist eine Menge von n disjunkten Teilnehmerpaaren. Ein Matching M in einer Instanz von SRP ist stabil, wenn es keine zwei Teilnehmer x und y gibt, von denen jeder den anderen seinem Partner in M vorzieht. Man sagt, ein solches Paar blockiert M oder ist ein blockierendes Paar in Bezug auf M.

Lösung

Im Gegensatz zum Stable Marriage Problem kann es sein, dass für bestimmte Gruppen von Teilnehmern und deren Präferenzen kein stabiles Matching existiert. Für ein minimales Beispiel einer nicht existierenden stabilen Paarung betrachte vier Personen A, B, C und D, deren Rangliste wie folgt lautet:

A:(B,C,D), B:(C,A,D), C:(A,B,D), D:(A,B,C)

In dieser Rangliste ist jeder der Personen A, B und C für irgendjemanden die am meisten bevorzugte Person. In jeder Lösung muss einer aus A, B oder C mit D und die anderen beiden miteinander ein Paar bilden (zum Beispiel AD und BC), aber für jeden, der mit D zusammenkommt, wird ein anderer Teilnehmer ihn am höchsten bewertet haben, und D's Partner wird wiederum diesen anderen Teilnehmer gegenüber D bevorzugen. In diesem Beispiel ist AC eine passendere Paarung als AD. Aber die notwendige verbleibende Paarung von BD wirft das gleiche Problem auf. Dies zeigt das Fehlen eines stabilen Matchings für diese Teilnehmer und ihre Präferenzen auf.

Algorithmus

Ein effizienter Algorithmus wurde 1985 von Irving vorgestellt.

Der Algorithmus wird für jedes Beispiel des Problems bestimmen, ob ein stabiles Matching existiert, und wenn dies der Fall ist, wird er ein solches Matching finden. Der Irving-Algorithmus hat eine O(n²) Komplexität, vorausgesetzt, geeignete Datenstrukturen werden verwendet, um die notwendige Manipulation der Präferenzlisten und die Identifizierung von Rotationen zu implementieren.

Der Algorithmus besteht aus zwei Phasen. In Phase 1 machen die Teilnehmer einander Anträge, auf ähnliche Weise wie beim Gale-Shapley-Algorithmus für das Stable Marriage Problem. Jeder Teilnehmer ordnet die anderen Teilnehmer nach ihren Präferenzen. Dies ergibt eine Präferenzliste – eine geordnete Menge der anderen Teilnehmer. Die Teilnehmer machen dann, der Reihenfolge nach, jeder Person auf ihrer Liste einen Antrag und gehen zur nächsten Person, wenn ihr derzeitiger Antrag abgelehnt wird. Ein Teilnehmer wird einen Antrag ablehnen, wenn er bereits einen Antrag von jemandem hat, den er bevorzugt. Ein Teilnehmer lehnt auch einen zuvor angenommenen Antrag ab, wenn er später einen Antrag erhält, den er bevorzugt. In diesem Fall macht der abgelehnte Teilnehmer der nächsten Person auf seiner Liste einen Antrag, bis ein Antrag erneut angenommen wird. Sollte ein Teilnehmer schließlich von allen anderen Teilnehmern abgelehnt werden, zeigt dies, dass kein stabiles Matching möglich ist. Andernfalls endet Phase 1 damit, dass jede Person einen Antrag von einer der anderen hält.

Betrachte zwei Teilnehmer, q und p. Wenn q einen Antrag von p hält, dann entfernen wir aus q's Liste alle Teilnehmer x, die nach p kommen würden. Symmetrisch entfernen wir für jeden entfernten Teilnehmer x, q aus der Liste von x, sodass q in der Liste von p an erster Stelle steht; und p an der letzten Stelle in q's Liste, da q und jeder x keine Partner in einem stabilen Matching sein können. Die sich daraus ergebende reduzierte Menge von Präferenzlisten wird als Phase-1-Tabelle bezeichnet. Wenn in dieser Tabelle eine reduzierte Liste leer ist, gibt es kein stabiles Matching. Ansonsten ist die Phase-1-Tabelle eine stabile Tabelle. Eine stabile Tabelle ist definitionsgemäß die Menge von Präferenzlisten aus der Originaltabelle, nachdem Mitglieder aus einer oder mehreren Listen entfernt wurden und die folgenden drei Bedingungen erfüllt sind (wobei reduzierte Liste eine Liste in der stabilen Tabelle bedeutet):

(i) p steht an erster Stelle auf q's reduzierter Liste, dann und nur dann, wenn q an letzter Stelle auf p's Liste ist.
(ii) p ist nicht auf der reduzierten Liste von q genau dann, wenn q nicht auf p's ist, genau dann, wenn q die letzte Person auf seiner Liste gegenüber p vorzieht; oder p die letzte Person auf seiner Liste gegenüber q bevorzugt.
(iii) Keine reduzierte Liste ist leer.

Stabile Tabellen haben mehrere wichtige Eigenschaften, die zur Rechtfertigung des weiteren Verfahrens verwendet werden:

1. Jede stabile Tabelle muss eine Untertabelle der Phase-1-Tabelle sein, wobei die Untertabelle eine Tabelle ist, in der die Präferenzlisten der Untertabelle diejenigen der Übertabelle sind, wobei einige Individuen aus den Listen der jeweils anderen entfernt wurden.

2. Wenn in jeder stabilen Tabelle jede reduzierte Liste genau eine Person enthält, dann ergibt die Paarung jeder Person mit der einzelnen Person auf ihrer Liste ein stabiles Matching.

3. Wenn die das Stable Roommates Problembeispiel ein stabiles Matching aufweist, gibt es ein stabiles Matching, das in einer der stabilen Tabellen enthalten ist.

4. Jede stabile Untertabelle einer stabilen Tabelle und insbesondere jede stabile Untertabelle, die ein stabiles Matching wie in 2 angibt, kann durch eine Sequenz von Rotationseliminierungen in der stabilen Tabelle erhalten werden.

Diese Rotationseliminierungen umfassen Phase 2 des Irving-Algorithmus.

Gemäß 2 gibt es einen Match, wenn jede reduzierte Liste der Phase-1-Tabelle genau ein Individuum enthält.

Andernfalls tritt der Algorithmus in Phase 2 ein. Eine Rotation in einer stabilen Tabelle T ist definiert als eine Folge (x₀, y₀), (x₁, y₁), …, (x_k-1, y_k-1) mit paarweise verschiedenen x_i und der Bedingung, dass y_i an erster Stelle auf der reduzierten Liste von x_i steht (oder x_i ist an letzter Stelle auf y_i's reduzierter Liste) und y_i+1 an zweiter Stelle auf x_i's reduzierter Liste steht für i = 0, …, k-1, wobei die Indizes modulo k genommen werden. Daraus folgt, dass in einer stabilen Tabelle mit einer reduzierten Liste, die mindestens zwei Individuen enthält, eine solche Rotation immer existiert. Um sie zu finden, beginne bei einem p₀, mit mindestens zwei Individuen in ihrer reduzierten Liste und definiere rekursiv q_i+1 als die Person an zweiter Stelle auf der Liste von p_i und p_i+1 als die Person an letzter Stelle auf der Liste von q_i+1, bis diese Sequenz irgendein p_j wiederholt, womit eine Rotation gefunden ist: es ist die Folge von Paaren, die bei dem ersten Vorkommen von (p_j, q_j) beginnt und bei dem Paar vor dem letzten Vorkommen endet. Die Sequenz von p_i bis zu p_j wird als das Ende der Rotation bezeichnet. Die Tatsache, dass diese Suche in einer stabilen Tabelle stattfindet, garantiert, dass jeder p_i mindestens zwei Personen auf seiner Liste hat.

Um die Rotation zu eliminieren, weist y_i x_i zurück, sodass x_i y_i+1 einen Antrag macht; das gilt für jedes i. Um die stabilen Tabelleneigenschaften (i) und (ii) wiederherzustellen, werden für jedes i alle Nachfolger von x_i-1 aus der Liste von y_i entfernt, und y_i wird aus ihren Listen entfernt. Wenn eine reduzierte Liste während dieser Entfernung leer wird, gibt es kein stabiles Matching. Andernfalls ist die neue Tabelle wieder eine stabile Tabelle und gibt entweder bereits ein Matching an, da jede Liste genau eine Person enthält, oder es kann eine weitere Rotation gefunden und eliminiert werden, sodass dieser Schritt wiederholt wird.

Phase 2 des Algorithmus kann nun wie folgt zusammengefasst werden:

T = Phase 1 Tabelle;
while (true) {
    identifiziere eine Rotation r in T;
    eliminiere r aus T;
    if eine Liste in T leer wird,
        return null; (kein stabiles Matching kann existieren)
    else if (jede reduzierte Liste in T hat die Größe 1)
        return das Matching M = {{x, y} | x und y sind auf des anderen Liste in T}; (das  ist ein stabiles Matching)
}

Um eine O(n²)-Laufzeit zu erreichen, eine Rangordnungsmatrix, deren Eintrag in Zeile i und Spalte j die Position des j-ten Individuums in der i-ten Liste ist; das dauert O(n²) lang. Mit der Rangordnungsmatrix kann in konstanten Zeitabständen überprüft werden, ob eine Person eine andere bevorzugt, indem sie ihre Ränge in der Matrix vergleichen. Außerdem, anstatt Elemente aus den Präferenzlisten explizit zu entfernen, werden die Indizes des ersten, zweiten und letzten auf der reduzierten Liste jeder Person beibehalten. Die erste Person, die nicht gematcht ist, d. h. mindestens zwei in ihrer reduzierten Liste hat, wird ebenfalls beibehalten. Dann wird in Phase 2 die Sequenz von p_i "durchlaufen", um herauszufinden, dass eine Rotation in einer Liste gespeichert ist und es wird ein Array verwendet, um Individuen als besucht zu markieren, wie in einer standardmäßigen Tiefensuche Graph-Traversierung. Nach der Eliminierung einer Rotation speichern wir weiterhin nur ihr Ende, falls vorhanden, in der Liste und wie im Array besucht. Und beginnen dann die Suche nach der nächsten Rotation bei der letzten Person am Ende und ansonsten bei der nächsten nicht gemachten Person, wenn es kein Ende gibt. Dies reduziert das wiederholte Überqueren des Endes, da es durch die Entfernung der Rotation weitgehend unbeeinflusst bleibt.

Beispiel

Im Folgenden sind die Präferenzlisten für ein Beispiel des Stable Roommate Problems mit 6 Teilnehmern aufgeführt: 1, 2, 3, 4, 5, 6.

1 :   3   4   2   6   5
2 :   6   5   4   1   3
3 :   2   4   5   1   6
4 :   5   2   3   6   1
5 :   3   1   2   4   6
6 :   5   1   3   4   2

Eine mögliche Ausführung von Phase 1 besteht aus der folgenden Abfolge von Anträgen und Ablehnungen, wobei → macht Antrag repräsentiert und × lehnt ab darstellt.

1 → 3
2 → 6
3 → 2
4 → 5
5 → 3;   3 × 1
1 → 4
6 → 5;   5 × 6
6 → 1

So endet Phase 1 mit den folgenden reduzierten Präferenzlisten:

1 :   3   4   2   6   5
2 :   6   5   4   1   3
3 :   2   4   5   1   6
4 :   5   2   3   6   1
5 :   3   1   2   4   6
6 :   5   1   3   4   2

In Phase 2 wird zuerst die Rotation r₁ = (1,4), (3,2) identifiziert. Dies liegt daran, dass 2 der zweite Favorit von 1 ist und 4 der zweite Favorit von 3 ist. Das Eliminieren von r₁ ergibt:

1 :   3   4   2   6   5
2 :   6   5   4   1   3
3 :   2   4   5   1   6
4 :   5   2   3   6   1
5 :   3   1   2   4   6
6 :   5   1   3   4   2

Als nächstes wird die Rotation r₂ = (1,2), (2,6), (4,5) identifiziert, und ihre Eliminierung ergibt:

1 :   3   4   2   6   5
2 :   6   5   4   1   3
3 :   2   4   5   1   6
4 :   5   2   3   6   1
5 :   3   1   2   4   6
6 :   5   1   3   4   2

Daher sind 1 und 6 gematcht. Schließlich wird die Rotation r₃ = (2,5), (3,4) identifiziert, und ihre Eliminierung ergibt:

1 :   3   4   2   6   5
2 :   6   5   4   1   3
3 :   2   4   5   1   6
4 :   5   2   3   6   1
5 :   3   1   2   4   6
6 :   5   1   3   4   2

Daher ist das Matching {{1, 6}, {2,4}, {3, 5}} stabil.

Implementierung in Softwarepaketen

• Java: Ein Constraint-Programmiermodell, um alle stabilen Matchings im Stable Roommates Problem mit unvollständigen Listen zu finden, ist unter der CRAPL-Lizenz verfügbar.
• R: Das Constraint-Programmiermodell ist auch als Teil des R Pakets matchingMarkets verfügbar.
• API: Die MatchingTools API stellt den Algorithmus über eine freie Programmierschnittstelle zur Verfügung.

Literatur

• Tamás Fleiner, Robert W. Irving, David F. Manlove: An efficient algorithm for the "stable roommates" problem. In: Theoretical Computer Science. 381, Nr. 1-3, 2007, S. 162–176. doi:10.1016/j.tcs.2007.04.029.
• Daniel M. Gusfield, Robert W. Irving: The Stable Marriage Problem: Structure and Algorithms. In: MIT Press. 1989.
• Robert W. Irving, David F. Manlove: The Stable Roommates Problem with Ties. (PDF) In: Journal of Algorithms. 43, Nr. 1, 2002, S. 85–105. doi:10.1006/jagm.2002.1219.