Stable Matching (deutsch: stabiles Matching) bezeichnet in der Spieltheorie eine Paarung zwischen zwei Gruppen, gegen die kein Blockierungspaar existiert: Es gibt kein Paar aus je einer Seite, das sich gegenseitig gegenüber den aktuellen Partnern vorziehen würde. Stabilität ist damit eine kombinatorische Bedingung an die Präferenzen, nicht an Gewichte.
Das Grundmodell
Gegeben sind zwei gleich große Gruppen (bipartiter Graph mit Knoten als Personen und Kanten als möglichen Paarungen); jede Person hat eine Präferenzliste. Gesucht ist ein stabiles perfektes Matching: Jede Person ist gepaart und kein ungepaartes Paar würde sich verbessern. David Gale und Lloyd Shapley bewiesen 1962, dass eine solche Paarung immer existiert — ihr Algorithmus konstruiert sie in O(n²) Schritten.
Eigenschaften und Verallgemeinerungen
Der klassische Fall mit zwei Geschlechtern heißt Stable Marriage (Stabile Heirat). Wichtige Varianten: Hospitals/Residents (eine Seite hat Kapazitäten), Stable Roommates (eine einzige Gruppe — hier existiert nicht immer eine stabile Paarung) und Varianten mit unvollständigen oder gleichwertigen Präferenzen (dort ist das Auffinden eines maximalen stabilen Matchings NP-schwer). Nicht jedes perfekte Matching ist stabil, und auch ein gewichtetes Matching mit optimaler Gewichtssumme kann Blockierungspaare enthalten — Stabilität ist eine eigene Anforderung.
Anwendungen
Stable-Matching-Verfahren steuern die Vergabe von Studien- und Krankenhausplätzen (etwa das National Resident Matching Program in den USA), Schulplatzvergabe und Tauschringe bei Organspenden. Alvin Roth und Lloyd Shapley erhielten dafür 2012 den Nobelpreis für Wirtschaftswissenschaften. Spieltheoretisch gilt: Wer selbst vorschlägt, sollte seine wahre Präferenz angeben — die vorschlagende Seite erhält immer ihr bestmögliches stabiles Ergebnis.