David Gale & Lloyd Shapley

Script zum Heiratsproblem

Das sogenannte Heiratsproblem stellt den Ausgangspunkt für Zuordnungsprobleme dar. So geht es zum Beispiel darum, Arbeitssuchenden eine freie Stelle nach ihrer Qualikation oder Studenten ihre Universität nach Fähigkeiten zuzuordnen. Im Prinzip wird nach fertiger Zuordnung ein Netz aufgespannt, in dem jeder eine optimale Vergabe findet. Bekannt ist dieses auch bei der Suche von Heiratswilligen nach einem potenziellen Partner. Jeder Heiratswillige hat dabei seine ganz private Rankingliste, auf der draufsteht, in welcher Reihenfolge, je nach Sympatie, man bereit ist, dem späteren Partner ein Angebot zu machen.

Im Folgenden wird das Vorgehen an einem einfachen Beispiel mit vier Partnern angedeutet. Trotzdem jeder einzelne Partner eine Präferenzliste besitzt, ist die Zuordnung in diesem Beispiel weitgehend unproblematisch. Lediglich der erste Mann hat im Beispiel ein echtes Problem, da ein Bewerber für seine Verlobte in deren Ranking weiter vorne rangiert. Mann 1 reagiert etwas rüde, er löst die Verlobung und streicht die Dame komplett aus seiner Präferenzliste raus. Der neue Partner von D wird Mann 2. Im Beispiel handelt es sich um ein perfektes Matching, auch der Mann mit der Nummer 1 bekommt am Ende seine Partnerin C. Am Hochzeitstag sind alle miteinander liiert. Der Anfang des Algorithmus ist an folgenden Bildern nachzuvollziehen.