Stable Marriage Problem
In der Mathematik, der Volkswirtschaftslehre und der Informatik bezeichnet das Stable Marriage Problem (englisch für: Problem der stabilen Paarung, auch “stable matching problem” oder SMP) das Problem, eine stabile Paarung zwischen zwei gleich großen Mengen von Elementen zu finden, anhand einer gegebenen Präferenzordnung für jedes Element. Eine Paarung (oder ein Matching) ist eine Zuordnung der Elemente der einen Menge zu den Elementen der anderen Menge. Sie ist nicht stabil, wenn
- a.) Ein Element A aus der ersten Menge ein gegebenes Element B aus der zweiten Menge gegenüber dem Element bevorzugt, mit dem A schon gematcht ist, und
- b.) B ebenfalls A gegenüber dem Element präferiert, mit dem B schon gematcht ist.
Mit anderen Worten: Eine Paarung ist stabil, wenn kein Match (A, B) existiert, bei dem sowohl A als auch B individuell bessergestellt wären als mit dem Element, mit dem sie gerade gematcht sind.
Das Stable Marriage Problem nimmt heterosexuelle Paare an und wurde wie folgt formuliert:
„Gegeben n Männer und n Frauen, wobei jede Person alle Angehörigen des anderen Geschlechts in der Reihenfolge ihrer Präferenz angeordnet hat, heiraten die Männer und Frauen einander so, 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.“
Man beachte, dass sich dieses Problem darin vom Stable Roommates Problem unterscheidet, dass es zwei verschiedene Klassen gibt, die miteinander ein Paar bilden müssen (in diesem Beispiel Männer und Frauen).