Satz von Gale-Shapley

Dieser Artikel wurde auf der Qualitätssicherungsseite des Portals Mathematik eingetragen. Dies geschieht, um die Qualität der Artikel aus dem Themengebiet Mathematik auf ein akzeptables Niveau zu bringen. Bitte hilf mit, die Mängel dieses Artikels zu beseitigen, und beteilige dich bitte an der Diskussion! (Artikel eintragen)

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 $G=(U\cup P,E)$ ein bipartiter Graph. Für alle $u\in U$ gibt es eine totale Ordnung $<_{u}$ an $N(u)$, und für alle $p\in P$ gibt es eine totale Ordnung $<_{p}$ an $N(p)$.

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 $(p,u)$ entweder die Person $p$ von einem Unternehmen eingestellt wird, das sie $u$ vorzieht, oder das Unternehmen $u$ eine Person eingestellt hat, die es $p$ vorzieht.

Formal:

Es existiert ein Matching $M\subseteq U\times P$ sodass für alle $(u,p)\in E(G)\setminus M$, entweder ein $p'\in P$ existiert mit $(u,p')\in M$ und $p<_{u}p'$ (d.h., $u$ bevorzugt $p'$ gegenüber $p$), oder ein $u'\in U$ existiert mit $(u',p)\in M$ und $u<_{p}u'$(d.h., $p$ bevorzugt $u'$ gegenüber $u$).

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 $p$ gibt, die nicht die bevorzugte Wahl eines Unternehmens ist und die nicht von allen Unternehmen in ihrer Nachbarschaft abgelehnt wurde
3      Sei $u$ das Unternehmen, das die Person $p$ unter denen, die sie noch nicht abgelehnt haben, am meisten bevorzugt.
4      wenn $u$ noch nicht kontaktiert wurde
5          dann wird $p$ zu seiner bevorzugten Wahl
6      sonst hat $u$ eine bevorzugte Wahl $p'$. In diesem Fall:
7          wenn $u$ $p$ gegenüber $p'$ bevorzugt
8              dann wird $p$ zur bevorzugten Wahl und $u$ lehnt $p'$ endgültig ab
9          sonst hat $u$ keinen Grund, seine bevorzugte Wahl zu ändern, und $u$ lehnt $p$ 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 $p$ sich höchstens bei allen Unternehmen in ihrer Nachbarschaft bewirbt, terminiert der Algorithmus in weniger als $N$ Schritten, wobei $N=\sum _{p\in P}|N(p)|$ die Summe der Anzahl der Unternehmen in der Nachbarschaft jeder Person ist.

Korrektheit

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