Stable Marriage Problem
In der Mathematik, der Volkswirtschaftslehre und der Informatik bezeichnet das Stable Marriage Problem (auch Stable Matching Problem, englisch für: Problem der stabilen Paarung, abgekürzt „SMP“) das Problem, eine stabile Paarung zwischen den Elementen zweier gleich großer Mengen zu finden. Dabei haben alle Elemente beider Mengen eine eindeutige Reihenfolge der Präferenz für jedes Element der anderen Menge.
Eine Paarung (oder ein Matching) ist eine Zuordnung der Elemente der einen Menge zu den Elementen der anderen Menge. Sie ist nicht stabil, wenn
- ein Element A aus der ersten Menge ein Element B aus der zweiten Menge gegenüber dem Element der zweiten Menge bevorzugt, mit dem A aktuell gematcht ist, und
- B ebenfalls A gegenüber dem Element aus der ersten Menge präferiert, mit dem B aktuell gematcht ist.
Mit anderen Worten: Eine Paarung ist stabil, wenn kein Match (A, B) existiert, den sowohl A als auch B im Vergleich zu ihrem jeweiligen aktuellen Match präferieren würden.
Das Stable Marriage Problem nimmt heterosexuelle Paare an und wurde wie folgt formuliert:
„n Männer und n Frauen, von denen jede Person alle Angehörigen des anderen Geschlechts in der Reihenfolge ihrer Präferenz angeordnet hat, sollen so verheiratet werden, dass es keine zwei Menschen unterschiedlichen Geschlechts gibt, die beide lieber einander geheiratet hätten als ihre gegenwärtigen Partner. Wenn es keine solchen Paare gibt, gilt die Menge der Ehen als stabil.“
Vom Stable Roommates Problem unterscheidet sich das Stable Marriage Problem, weil es hier zwei verschiedene Mengen gibt (in diesem Beispiel Männer und Frauen), deren Elemente paarweise kombiniert werden müssen.