Der Satz von Gale-Shapley ist ein grundlegendes Ergebnis in der Mathematik und Informatik, das sich mit der Frage beschäftigt, wie stabile Matchings in bipartiten Graphen gefunden werden können. Dieser Satz hat Anwendungen in der Spieltheorie, der Ökonomie und der Informatik. Er wurde erstmals 1962 von den Mathematikern David Gale und Lloyd Shapley bewiesen. Der Satz von Gale-Shapley zeigt, dass es immer möglich ist, ein stabiles Matching zu finden, wenn zwei Gruppen von Elementen (wie z. B. Arbeitgeber und Arbeitssuchende) jeweils eine Präferenzordnung über die Elemente der anderen Gruppe haben.

Kontext Die Unternehmen einer Stadt stellen ein. Jedes sucht genau eine Person. Glücklicherweise sucht eine Gruppe von Personen nach einem Job bei den Unternehmen in ihrer Nachbarschaft (dies kann durch einen bipartiten Graphen modelliert werden). Jedes Unternehmen hat eine klar definierte Rangfolge (totale Ordnung) der verschiedenen Personen, die in ihrer Nachbarschaft nach einem Job suchen. Auf ähnliche Weise hat jede Person eine klar definierte Rangfolge der verschiedenen Unternehmen in ihrer Nachbarschaft.

Formel, sei ein bipartiter Graph. Für alle gibt es eine totale Ordnung an , und für alle gibt es eine totale Ordnung an .

Aussage Der Satz von Gale-Shapley lautet:

Es gibt eine stabile Einstellungskonfiguration (Matching) zwischen den Unternehmen und den Personen, das heißt, dass für jedes nicht gematchte Personen-Unternehmens-Paar entweder die Person von einem Unternehmen eingestellt wird, das sie vorzieht, oder das Unternehmen eine Person eingestellt hat, die es vorzieht.

Formal:

Es existiert ein Matching sodass für alle , entweder ein existiert mit und (d.h., bevorzugt gegenüber ), oder ein existiert mit und (d.h., bevorzugt gegenüber ).

Algorithmus Input Als Eingabe dient die voll beschriebene Situation (i.e. der bipartite Graph und eine totale Ordnung für jeden Knoten an seiner Nachbarschaft).

Output Der Algorithmus liefert ein stabiles Matching zwischen den Unternehmen und den Personen.

Pseudocode 1 Zu Beginn des Verfahrens hat jedes Unternehmen keine bevorzugte Wahl und hat noch niemanden abgelehnt. 2 solange es eine Person gibt, die nicht die bevorzugte Wahl eines Unternehmens ist und die nicht von allen Unternehmen in ihrer Nachbarschaft abgelehnt wurde 3 Sei das Unternehmen, das die Person unter denen, die sie noch nicht abgelehnt haben, am meisten bevorzugt. 4 wenn noch nicht kontaktiert wurde 5 dann wird zu seiner bevorzugten Wahl 6 sonst hat eine bevorzugte Wahl . In diesem Fall: 7 wenn gegenüber bevorzugt 8 dann wird zur bevorzugten Wahl und lehnt endgültig ab 9 sonst hat keinen Grund, seine bevorzugte Wahl zu ändern, und lehnt endgültig ab. 10 Schließlich stellt jedes Unternehmen seine bevorzugte Wahl ein.

Terminierung Der Algorithmus terminiert, da die Ablehnungen endgültig sind. Da jede Person sich höchstens bei allen Unternehmen in ihrer Nachbarschaft bewirbt, terminiert der Algorithmus in weniger als Schritten, wobei die Summe der Anzahl der Unternehmen in der Nachbarschaft jeder Person ist.

Korrektheit Sei eine der Personen, die nach einem Job suchen, und ein Unternehmen. Zu Beginn des Algorithmus hatte keinen Job. Wenn am Ende des Algorithmus immer noch keinen Job hat oder von einem Unternehmen eingestellt wird, das sie weniger mochte als , dann hat sie abgelehnt. Also hat jemanden Besseren als gefunden. Somit liefert der Algorithmus tatsächlich ein stabiles Matching.

Gale-Shapley, Satz von Kategorie:Graphentheorie