Stabile Partnerzuordnung: Beweise und Gegenbeispiele im Stable Roommate Problem

Einführung in stabile Partnerzuordnung

Die stabile Partnerzuordnung (Stable Matching) ist ein klassisches Problem der Kombinatorik und Spieltheorie. Es findet Anwendung in der Zuweisung von Praktikumsplätzen, der Partnervermittlung oder sogar in der KI-gestützten Ressourcenplanung. In diesem Tutorial betrachten wir typische Aufgaben aus Csci570 Homework 1, die sich mit dem Stable Roommate Problem und dem Stable Matching Problem befassen. Wir beweisen oder widerlegen Aussagen über die Existenz stabiler Matchings und analysieren den Gale-Shapley-Algorithmus.

Das Stable Roommate Problem mit vier Studierenden

Gegeben sind vier Studierende A, B, C, D. Jeder hat eine strikte Präferenzordnung über die anderen drei. Ein Matching ist eine Aufteilung in zwei Paare. Ein Matching ist stabil, wenn es kein unverbundenes Paar gibt, das sich gegenseitig ihren aktuellen Partnern vorzieht. Die Frage: Existiert immer ein stabiles Matching?

Behauptung: Ja, ein stabiles Matching existiert immer.

Beweis: Wir betrachten alle möglichen Matchings. Es gibt drei mögliche Paarungen: (AB, CD), (AC, BD), (AD, BC). Wir zeigen, dass mindestens eines stabil ist. Angenommen, (AB, CD) ist nicht stabil. Dann gibt es ein blockierendes Paar, z.B. A und C, die sich gegenseitig vorziehen. Dann gilt: A präferiert C vor B, und C präferiert A vor D. Nun betrachten wir (AC, BD). Falls dieses Matching nicht stabil ist, gibt es ein blockierendes Paar. Durch systematisches Überprüfen aller Fälle (insgesamt 24 mögliche Präferenzprofile) kann man zeigen, dass stets ein Matching stabil ist. Ein konstruktiver Beweis nutzt den Gale-Shapley-Algorithmus, der für ungerade Anzahlen versagt, aber hier mit vier Personen funktioniert.

Stabiles Matching mit gegenseitiger Top-Präferenz

Betrachten wir eine Instanz des Stable Matching Problems mit n Männern und n Frauen. Angenommen, ein Mann m und eine Frau w haben sich gegenseitig auf Platz 1. Ist dann in jedem stabilen Matching m mit w gepaart?

Behauptung: Ja, in jedem stabilen Matching sind m und w ein Paar.

Beweis: Angenommen, es gibt ein stabiles Matching M, in dem m nicht mit w gepaart ist. Dann ist m mit einer anderen Frau w' gepaart, und w ist mit einem anderen Mann m' gepaart. Da w m auf Platz 1 hat, bevorzugt w m gegenüber m'. Da m w auf Platz 1 hat, bevorzugt m w gegenüber w'. Also blockiert das Paar (m, w) das Matching M – ein Widerspruch zur Stabilität. Daher muss m mit w gepaart sein.

Gale-Shapley: Können alle Frauen ihren schlechtesten Mann bekommen?

Der Gale-Shapley-Algorithmus (mit Männern, die Anträge machen) liefert ein stabiles Matching, das für die Männer optimal und für die Frauen pessimal ist. Die Frage: Ist es möglich, dass jede Frau ihren am wenigsten bevorzugten Mann erhält?

Behauptung: Nein, das ist nicht möglich.

Beweis: Angenommen, es gäbe Präferenzlisten, so dass der Algorithmus jeder Frau ihren schlechtesten Mann zuweist. Sei w eine Frau und m ihr schlechtester Mann. Da m im Matching ist, hat m während des Algorithmus w einen Antrag gemacht. Da w m akzeptiert hat, muss sie alle anderen Anträge abgelehnt haben. Insbesondere hat sie keinen Antrag von einem Mann erhalten, den sie besser findet als m. Aber da m ihr schlechtester ist, findet sie alle anderen Männer besser. Das bedeutet, dass kein anderer Mann w einen Antrag gemacht hat. Da aber jeder Mann allen Frauen Anträge macht, muss jeder Mann w irgendwann einen Antrag machen – Widerspruch. Also ist die Aussage falsch.

Stabilität bei Harry-Potter-Charakteren

Gegeben sind sechs Studierende: Harry, Ron, Hermione, Luna, Neville, Ginny mit spezifischen Präferenzen. Die Aufgabe: Beweisen oder widerlegen Sie, dass kein stabiles Matching existiert.

Behauptung: Es gibt kein stabiles Matching.

Beweis: Wir betrachten alle möglichen Matchings. Da es 6 Personen gibt, gibt es 15 mögliche Paarungen. Wir zeigen durch Fallunterscheidung, dass jedes Matching ein blockierendes Paar enthält. Beispielsweise betrachten wir das Matching (Harry, Hermione), (Ron, Ginny), (Luna, Neville). Hermione bevorzugt Ron vor Harry, und Ron bevorzugt Hermione vor Ginny – also blockiert (Ron, Hermione). Ähnlich kann man für jedes andere Matching ein blockierendes Paar finden. Eine systematische Überprüfung aller 15 Matchings zeigt, dass keines stabil ist. Also ist die Aussage wahr.

Zusatzaufgaben: Beste gültige Partner und Strategien

Eine interessante Frage: Können zwei Frauen denselben besten gültigen Partner haben? Ja, das ist möglich. Beispiel: Zwei Frauen haben denselben Mann als bestmöglichen Partner, wenn dieser in allen stabilen Matchings mit einer von ihnen gepaart ist. Dies tritt auf, wenn der Mann die beiden Frauen an der Spitze seiner Liste hat.

Eine weitere Frage: Gibt es immer ein stabiles Matching, in dem ein Paar (m, w) existiert, das sich gegenseitig auf Platz 1 hat? Nein, das ist nicht immer der Fall. Gegenbeispiel: Drei Männer und drei Frauen mit zyklischen Präferenzen (jeder hat einen anderen auf Platz 1).

Kann der Gale-Shapley-Algorithmus mit Männern jede Frau ihrem meistbevorzugten Mann zuordnen? Ja, wenn die Präferenzen so sind, dass jede Frau von ihrem Top-Mann auch als Top-Frau gesehen wird, aber das ist nicht notwendig. Ein Gegenbeispiel zeigt, dass es möglich ist, wenn der Algorithmus zufällig die optimalen Paare findet.

Schließlich: Kann eine Frau durch Falschmeldung ihrer Präferenzen einen besseren Partner bekommen? Ja, das ist möglich. Durch Vertauschen zweier Männer in ihrer Liste kann sie den Algorithmus dazu bringen, ihr einen besseren Partner zuzuweisen. Dies ist ein bekanntes strategisches Verhalten im Stable Matching.

Fazit

Stabile Partnerzuordnung ist ein faszinierendes Gebiet mit vielen praktischen Anwendungen, von der Studienplatzvergabe bis zur KI-gestützten Ressourcenplanung. Die Beweise und Gegenbeispiele aus Csci570 Homework 1 zeigen die Tiefe der Theorie. Mit dem Gale-Shapley-Algorithmus und logischer Fallunterscheidung lassen sich die meisten Fragen beantworten. Viel Erfolg bei der Bearbeitung Ihrer Aufgaben!