Algorithmus - Gale-Shapley Algorithmus

• Involvierte Definitionen:
• Veranstaltung: AlMa
• Referenz: @herzogWiSe22

⠀

Algorithmus: Gale-Shapley Algorithmus

Sei eine Menge von Männern.
Sei eine Menge von Frauen.

• Jeder Mann habe eine Präferenzliste, die durch die Totalordnung auf gegeben sei.
• Jede Frau habe eine Präferenzliste, die durch die Totalordnung auf gegeben sei.

Der Gale-Shapley Algorithmus funktioniert wie folgt:

1. Jeder unverlobte Mann macht der Frau , die er gemäß seiner Präferenzliste bevorzugt, einen Antrag

2. nimmt den Antrag an, falls

   • sie nicht verlobt ist oder

   • sie gemäß ihrer Präferenzliste gegenüber ihrem derzeitigen Verlobten bevorzugt.

     In diesem Fall streicht die Frau von seiner Präferenzliste .

3. Andernfalls lehnt den Antrag ab und streicht von seiner Präferenzliste .

   Weiter mit 1.

Anmerkung

Männeroptimale stabile Hochzeit

Der Algorithmus ergibt eine männeroptimale stabile Hochzeit.

Vertauschen wir in dem Algorithmus Frauen und Männer, so erhalten wir eine frauenoptimale stabile Hochzeit.