Klassischer Gale-Shapley-Algorithmus

David Gale und Lloyd S. Shapley entwickelten 1962 den Deferred Acceptance Algorithm, der später als der Gale-Shapley-Algorithmus bekannt wurde.

Der klassische GS findet eine Lösung für das Stable Marriage-Problem. Als Stable Marriage-Problem bezeichnet man die Suche nach einem stabilen Matching zwischen zwei gleich großen zueinander disjunkten Mengen. Dabei darf jedem Knoten maximal ein Matchingpartner zugeordnet werden: es handelt sich also nicht um ein b-Matching. Außerdem sind die Präferenzlisten vollständig und dürfen keine Indifferenzen beinhalten.

Der erweiterte GS kann für die Lösung des School-Choice-Problems verwendet werden. Ein Vorteil dieses Algorithmus ist, dass er garantiert, dass das resultierende Matching stabil ist. Aus diesem Grund wird er für seine Fairness geschätzt. Allerdings erfüllt er dafür in der Regel weniger Erstwünsche als rangmaximale Algorithmen (z.B. Boston-Algorithmus).

Gale und Shapley haben sich mit dem Stable Marriage-Problem ursprünglich im Kontext von Partnerzuteilungen zwischen Frauen und Männern beschäftigt. Aus diesem Grund verwenden wir im Folgenden die entsprechenden Bezeichnungen.

Eingabe:

Ein vollständiger bipartiter Graph $G = (U ~\dot{\cup}~ W, E)$ , wobei $U$ die Menge der Männer und $W$ die Menge der Frauen darstellt und $E = U \times W$ gilt
Für jeden Knoten $m$ in $U$ gibt es eine vollständige und strikte Präferenzliste $\succ_{m}$ über $W$
Für jeden Knoten $w$ in $W$ gibt es eine vollständige und strikte Präferenzliste $\succ_{w}$ über $U$

Ausgabe:

Ein stabiles Matching $M$ in $G$

Der Gale-Shapley-Algorithmus löst das Stable Marriage-Problem und wird im folgenden Abschnitt analysiert. Zuerst wird der Algorithmus als Pseudocode beschrieben und darauffolgend einige Eigenschaften bewiesen.

Pseudocode

$M \leftarrow \emptyset $
$\mathbf{while}$ $\exists \: m$ für den gilt $M(m) = \emptyset$ $\mathbf{do}$
$\quad$ $m$ macht seiner favorisierten Frau $w$ einen Antrag.
$\quad\quad$ $\mathbf{if}$ $\nexists \: \tilde{m}\in U$, sodass $M(\tilde{m}) = w$ $\mathbf{then}$
$\quad\quad\quad$ $M \leftarrow$ $M \cup \{ \{m,w \}\}$
$\quad\quad$ $\mathbf{else}$
$\quad\quad\quad$ $\mathbf{if}$ $m \succ_{w} \tilde{m}$ $\mathbf{then}$
$\quad\quad\quad\quad$ $M \leftarrow$ $M \setminus \{ \{\tilde{m},w \} \} $
$\quad\quad\quad\quad$ Streiche $w$ aus $\succ_{\tilde{m}}$.
$\quad\quad\quad\quad$ $M \leftarrow$ $M \cup \{ \{ m,w \} \} $
$\quad\quad\quad$ $\mathbf{else}$
$\quad\quad\quad\quad$ Streiche $w$ aus $\succ_{m}$.
$\mathbf{return}$ $M$

Der Ausdruck $M(v)$ gibt für einen Knoten $v \in U ~\dot{\cup}~ W$ den zugeordneten Partner an.

Zeile $1$ : Das Matching $M$ wird mit der leeren Menge initialisiert.
Zeile $2$ : Solange es einen nicht verlobten Mann $m \in U$ gibt führe Folgendes aus.
Zeile $3$ : Ein solcher beliebiger Mann $m$ (Reihenfolge nicht vorgegeben) macht seiner favorisierten Frau $w\in W$ (höchste Position auf $\succ_{m}$ ) einen Antrag.
Zeile $4-6$ : Seine favorisierte Frau $w$ nimmt den Antrag an, falls sie noch nicht mit einem Mann $\tilde{m} \in U$ verlobt ist.
Zeile $7-10$ : Falls $w$ mit $\tilde{m}$ verlobt ist, vergleicht sie diesen mit dem Antragsteller. Die Frau $w$ hebt ihre Verlobung auf, um sich mit dem Antragsteller $m$ zu verloben, sofern sie $m$ gemäß ihren Präferenzen $\succ_{\tilde{w}}$ vorzieht. Falls $w$ die Verlobung mit $\tilde{m}$ auflöst, streicht der Sitzengelassene $\tilde{m}$ seine ehemalig Verlobte $w$ von seiner Präferenzliste.
Zeile $11-12$ : Falls sich eine Frau $w$ durch eine Auflösung nicht verbessern würde, wird der Antrag von m abgelehnt und dieser streicht die Antragsempfängerin $w$ von seiner Präferenzliste.
Zeile $13$ : Gib das Matching $M$ aus, wenn jeder Mann verlobt ist.

Beispiel

Unten erkennt man eine Instanz des Stable Marriage-Problems. Die Männer werden über die Knotenmenge $U$ = $\{Amir,$ $Paul,$ $Noah,$ $Dimitri,$ $Felix \}$ und die Frauen über die Knotenmenge $W$ = $\{Marianne,$ $Leonie,$ $Annette,$ $Emilia,$ $Mia\}$ dargestellt. Die zur Person dazugehörige Präferenzliste ist links bzw. rechts von dem dazugehörigen Knoten zu finden. In den Präferenzlisten werden die Personen über die ersten beiden Anfangsbuchstaben codiert. Die Präferenzliste von Amir sagt z.B. aus, dass er Leonie gegenüber Marianne, Marianne gegenüber Mia, Mia gegenüber Annette und Annette gegenüber Emilia bevorzugt. Initial ist kein Mann mit einer Frau verlobt.

Während der Durchführung des Algorithmus stellen schwarze Kanten vorläufige Paare zwischen Männern und Frauen dar. Die schwarz und rot gestrichelten Kanten werden bei Konkurrenzsituationen zwischen zwei Männern genutzt. Der antragsstellende Mann ist in einer solchen Situation inzident zu der rot gestrichelten Kante.

Eigenschaften des Algorithmus

Stabilität

Satz

Der Gale-Shapley-Algorithmus findet ein stabiles Matching.

Beweis

Beweis:^meg2020 Zu jedem Zeitpunkt ist jeder Mann mit höchstens einer Frau und jede Frau mit höchstens einem Mann verlobt. Eine Frau verlobt sich mit einem Mann nur, wenn sie entweder noch nicht verlobt ist oder sich durch eine Auflösung ihrer bestehenden Verlobung verbessern kann. Ein Mann stellt seiner favorisierten Frau nur einen Antrag, wenn dieser nicht verlobt ist. Daher bilden die gefundenen Paare immer ein Matching.

Sei $b$ eine blockierende Kante $\{m,w\} \in E \setminus M$ , wobei $M$ ein vom Gale-Shapley-Algorithmus gefundenes Matching ist und $E$ die Menge aller möglichen Paare. Daraus folgt, dass Mann $m$ und Frau $w$ bei Terminierung nicht miteinander verlobt sind und $(i)\: w \succ_{m} M(m)$ und $(ii)\: m \succ_{w} M(w)$ gelten.

Wegen $(i)$ gab es eine Iteration, in der Mann $m$ der Frau $w$ einen Antrag gemacht hat. Die Frau $w$ hat den Antrag von Mann $m$ entweder sofort abgelehnt oder den Mann $m$ später abgewiesen, da sie von jemand Besseren, und zwar ihren Verlobten ( $M(w)$ ) einen Antrag erhalten hat. Damit muss gelten $M(w) \succ_{w} m$ , was ein Widerspruch zu $(ii)$ ist. $\Box$

Mann-Optimalität

Definition

Ein Paar $\{m,w\}$ heißt zulässig, wenn es ein stabiles Matching $M$ mit $\{m,w\} \in M$ gibt.

Ein Mann oder eine Frau in einem zulässigen Paar heißt zulässiger Mann oder zulässige Frau.

Satz

Der Gale-Shapley-Algorithmus liefert ein mann-optimales Matching.

Beweis

Beweis:^meg2020 Sei $M$ ein vom Gale-Shapley-Algorithmus gefundenes, nicht mann-optimales Matching. Dann muss es einen frühesten Zeitpunkt $t$ geben, zu dem ein Mann $m$ von seiner favorisierten zulässigen Frau $w$ abgewiesen wird.

Eine Abweisung durch $w$ zum Zeitpunkt $t$ erfolgt nur, wenn sie von einem für sie besseren Mann $m'$ einen Antrag erhält, d.h. es gilt $m' \succ_{w} m$ .

Da es eine für $m$ zulässige Frau gibt, existiert laut Definition ein stabiles Matching $M$ mit $\{m, w\} \in M$ .

Des Weiteren sei $\{m',w'\} \in M$ . Es gilt $w \succ_{m'} w'$ , da $m'$ zum Zeitpunkt $t$ mit $w$ zusammen ist und zuvor von keiner zulässigen Frau, insbesondere nicht von $w'$ , abgewiesen worden sein kann. Somit bilden $m'$ und $w$ ein blockierendes Paar bezüglich $M$ , was ein Widerspruch ist. $\Box$

Satz

Der Gale-Shapley-Algorithmus weist jeder Frau den für sie schlechtesten zulässigen Partner zu.

Beweis

Beweis:^meg2020 Angenommen $\{ m',w \}$ sei eine Kante in einem vom Gale-Shapley-Algorithmus gefundenen Matching $M$ und zudem sei $m:m \neq m'$ der schlechteste zulässige Partner für $w$ .

Sei $M'$ ein stabiles Matching, bei dem $w$ mit $m$ zusammen ist. Per Annahme gilt $m' \succ_{w} m$ . Zudem sei $\{m', w'\}$ in $M'$ . Betrachte nun das Matching $M$ . Da $M$ mann-optimal ist, findet Mann $m'$ seine Partnerin $w$ besser als $w'$ . Das Matching $M'$ kann nicht stabil sein, da $\{m', w \}$ eine blockierende Kante ist, was einen Widerspruch ergibt. $\Box$

Kardinalitätsmaximalität

Satz

Der Gale-Shapley-Algorithmus findet bei strikten und vollständigen Präferenzlisten ein kardinalitätsmaximales Matching.

Beweis

Sei $M$ nicht kardinalitätsmaximal und ein vom Gale-Shapley-Algorithmus gefundenes Matching. Da $M$ nicht kardinalitätsmaximal ist, muss es eine blockierende Kante $b = \{m,w\} \in E \setminus M$ geben.

Diese Kante $b$ ist eine blockierende Kante, da sowohl $w$ als auch $m$ vollständige Präferenzlisten haben und sich gegenseitig vor der Partnerlosigkeit präferieren. Dies gilt für jeden Mann bzw. jede Frau, da jede Person eine vollständige Präferenzliste hat.

Da $b$ eine blockierende Kante ist, ist $M$ nicht stabil, was ein Widerspruch zu der Annahme ist. $\Box$

Pareto-Effizienz

Satz

Der Gale-Shapley-Algorithmus findet im Allgemeinen kein männerseitig pareto-effizientes Matching.

Beweis

Beweis:^klo2017 Betrachte das im obigen Beispiel vom Gale-Shapley-Algorithmus gefundene Matching $M$ , welches auf Folie $1$ der folgenden Slideshow dargestellt wird. Das auf Folie $2$ dargestellte Matching pareto-dominiert männerseitig $M$ , d.h. Noah und Dimitri können sich durch einen Tausch ihrer Partnerinnen verbessern, ohne dabei einen anderen Mann schlechter zu stellen. Daraus folgt, dass der Gale-Shapley-Algorithmus im Allgemeinen kein männerseitig pareto-effizientes Matching findet. $\Box$

Rangmaximalität

Satz

Der Gale-Shapley-Algorithmus findet im Allgemeinen kein männerseitig rangmaximales Matching.

Beweis

Betrachte das vom Gale-Shapley-Algorithmus gefundene Matching $M$ , welches auf Folie $1$ dargestellt wird. Das Matching $M$ erfüllt zwei Zweitwünsche und drei Drittwünsche der Männer, obwohl durch einen Tausch der Partner von Noah und Dimitri vier Zweitwünsche und ein Drittwunsch erfüllt werden könnten, was auf Folie $2$ dargestellt wird. Deshalb findet der Gale-Shapley-Algorithmus im Allgemeinen kein männerseitig rangmaximales Matching. $\Box$

Strategiesicherheit

Satz

Der Gale-Shapley-Algorithmus ist im Allgemeinen nicht strategiesicher.

Beweis

Beweis:^meg2020 Unter der Annahme, dass die Teilnehmer wissen, dass die Zuteilung nach dem Gale-Shapley-Algorithmus vorgenommen wird und die Präferenzen der Teilnehmer transparent sind, können die Frauen durch falsche Präferenzen das Matching manipulieren. Die Männer hingegen nicht, weil bereits das Matching mann-optimal ist.

Betrachte die untenstehenden Stable Marriage-Instanzen, wobei Folie $1$ die wahren und Folie $2$ die falschen Präferenzen beinhaltet. Wenn Annette vorgibt, Felix gegenüber Noah zu präferieren, wird sie statt mit Noah mit ihrer Erstwahl Dimitri verlobt. Dadurch ist gezeigt, dass der Gale-Shapley-Algorithmus nicht strategiesicher ist. $\Box$

Verständnisfrage

Erweiterter Gale-Shapley-Algorithmus

Wir behandelten in den vorherigen Probleminstanzen Situationen, in denen sowohl Männer als auch Frauen immer strikte und vollständige Präferenzlisten besaßen. Jedoch trifft man in der Realität häufig auf Situationen, in denen Männer und/oder Frauen die gegenüberliegende Seite nicht komplett einschätzen möchten oder können, was an ethischen Gründen oder Gründen, die den verursachenden Informationsaufwand betreffen, liegen könnte. Beispielsweise erzeugt das Erstellen von strikten Präferenzlisten über alle möglichen Partner einen hohen Aufwand, da man sich über alle möglichen Partner informieren muss. Hier wäre es möglicherweise einfacher, Partner in bestimmte Kategorien einzustufen und und diese Kategorien in eine Reihenfolge zu bringen. In solchen Kategorien fasst man Partner zusammen, für die man indifferent ist.

Wenn man solche Indifferenzen in dem Stable Marriage-Problem zulässt, dann erhält man das Stable Marriage Problem with Ties. Falls man die Annahmen noch weiter lockert und verkürzte Präferenzlisten zulässt, erhält man das Stable Marriage Problem with Ties and Incomplete Preferences.

Irving veröffentlichte 1994 eine Abhandlung, in der das Stable Marriage Problem with Ties thematisiert wurde.^irv1994 In dieser Abhandlung teilte er das Konzept der Stabilität, in drei unterschiedlich starke Kategorien der Stabilität auf: Schwach-, Stark- und Super-Stabilität.

Irving stellt unter Anderem einen Algorithmus vor, welcher ein schwach-stabiles Matching findet, falls eines existiert. Im Folgenden wird dieser beschrieben.

Eingabe:

Ein bipartiter Graph $G = (U \dot{\cup} W, E)$ , wobei $U$ die Menge der Männer und $W$ die Menge der Frauen darstellt und $E \subseteq U \times W$ gilt
Für jeden Knoten $m$ in $U$ gibt es eine Präferenzliste mit Indifferenzen $\succ_{m}$ über $W$
Für jeden Knoten $w$ in $W$ gibt es eine Präferenzliste mit Indifferenzen $\succ_{w}$ über $U$

Ausgabe:

Ein schwach-stabiles Matching in $G$

Pseudocode

$M \leftarrow \emptyset $
$\mathbf{while}$ $\exists \: m$ für den gilt $M(m) = \emptyset$ und $\succ_{m}$ ist nicht leer $\mathbf{do}$
$\quad$ Mann $m$ macht seiner favorisierten Frau $w$ einen Antrag.
$\quad$ $M \leftarrow$ $M \cup \{ \{ m,w \} \}$
$\quad$ $\mathbf{if}$ $\exists \: \tilde{m}\in U : M(\tilde{m}) = w$ $\mathbf{then}$
$\quad\quad$ $M \leftarrow$ $M \setminus \{ \{ \tilde{m},w \} \} $
$\quad$ $\mathbf{for\text{ }each}$ $\hat{m} \in U$, für den gilt $m \succ_{w} \hat{m} $ $\mathbf{do}$
$\quad\quad$ Entferne $w$ aus $\succ_{\hat{m}}$.
$\mathbf{return}$ $M$

Zeile $1$ : Das Matching $M$ wird mit $\emptyset$ initialisiert.
Zeile $2$ : Folgendes wird solange wiederholt bis jeder Mann mit einer nicht leeren Präferenzliste verlobt ist.
Zeile $3$ : Ein beliebiger Mann $m$ , der noch nicht verlobt ist und eine nicht leere Präferenzliste hat, macht seiner favorisierten Frau $w$ einen Antrag.
Zeile $4-6$ : Die Frau $w$ nimmt in jedem Fall den Antrag an und löst, falls vorhanden, eine bestehende Verlobung mit einem anderen Mann $\tilde{m}$ auf.
Zeile $7-8$ : Danach streichen alle Nachfolger von $m$ gemäß der Präferenzliste von $w$ die Frau $w$ von ihren Präferenzlisten.
Zeile $9$ : Falls jeder Mann mit einer nicht leeren Präferenzliste verlobt ist, gib das Matching $M$ aus.

Im Unterschied zum Gale-Shapley-Algorithmus wird unter Umständen nicht jeder Mann seiner favorisierten Frau einen Antrag machen, da diese von seiner Präferenzliste wegen der Zeilen $7-8$ gelöscht werden kann. Außerdem wird statt einem stabilen Matching nur ein schwach-stabiles Matching gefunden.

Erweiterter Gale-Shapley School-Choice Algorithmus (EGS-SC)

Im folgenden Abschnitt beschäftigen wir uns mit einer auf das School-Choice-Problem angepassten Version des Gale-Shapley-Algorithmus.^kla2020 Mit diesem erweiterten Gale-Shapley School-Choice Algorithmus ( $EGS-SC$ ) findet man in der Eingabe ein schwach-stabiles Matching.

Wie beim Gale-Shapley-Algorithmus machen die Schüler ihren favorisierten Schulen einen Antrag. Jedoch kann eine Schule mehrere Anträge annehmen, weshalb erst ein Vergleich von allen aufgenommenen Schülern mit dem antragsstellenden Schüler gemacht wird, falls die Kapazität an Schulplätzen erschöpft ist.

Der Mechanismus der verzögerten Akzeptanz wird wie folgt realisiert. Eine Schule $s$ ersetzt einen aufgenommenen Schüler $p$ mit einem antragsstellenden Schüler $p'$ , wenn die Schule den Schüler $p'$ gegenüber $p$ strikt präferiert. Es folgt eine Analyse des $EGS-SC$ .

Eingabe:

Eine Menge an Schülern $P$
Eine Menge an Schulen $S$
Eine Menge an Kapazitäten $C$ mit einer Kapazität $c_s \in C$ für jede Schule $s \in S$
Eine Menge an strikten Präferenzlisten $\succ_{p}$ über eine Teilmenge $S$ für jeden Schüler $p \in P$
Eine Menge an Präferenzlisten mit Indifferenzen $\succ_{s}$ über eine Teilmenge $P$ für jede Schule $s \in S$

Ausgabe:

Ein schwach-stabiles Matching $M$ zwischen Schulen und Schülern

Pseudocode

$M \leftarrow \emptyset $
$\mathbf{while}$ $\exists \: p$ für den gilt $M(p)= \emptyset$ und $\succ_{p}$ ist nicht leer $\mathbf{do}$
$\quad$ Schüler $p$ macht seiner favorisierten Schule $s$ einen Antrag.
$\quad$ $\mathbf{if}$ $c_{s} \not= 0$ $\mathbf{then}$
$\quad\quad$ $M \leftarrow M \cup \{ \{p,s\}\}$
$\quad\quad$ $c_{s} = c_{s} - 1$
$\quad$ $\mathbf{else}$
$\quad\quad$ $\mathbf{if}$ $\nexists$ Schüler $\tilde{p}$, der Schule $s$ zugeordnet ist und $p$ $\succ_s$ $\tilde{p}$ gilt $\quad\quad$ $\mathbf{then}$
$\quad\quad\quad$ Streiche $s$ von $\succ_{p}$.
$\quad\quad$ $\mathbf{else}$
$\quad\quad\quad$ $M \leftarrow M \setminus \{ \{ \tilde{p}, s \}\}$
$\quad\quad\quad$ Streiche $s$ von $\succ_{\tilde{p}}$.
$\quad\quad\quad$ $M \leftarrow M \cup \{ \{p,s \}\}$
$\mathbf{return}$ $M$

Zeile $1$ : Das Matching $M$ wird mit $\emptyset$ initialisiert.
Zeile $2$ : Setze die Kapazität jeder Schule $s \in S$ auf ihre Anfangskapazität.
Zeile $3-4$ : Solange es einen nicht zugeordneten Schüler $p$ gibt dessen Präferenzliste nicht leer ist, macht Schüler $p$ seiner favorisierten Schule $s$ einen Antrag.
Zeile $5-7$ : Sofern die Kapazität seiner favorisierten Schule noch nicht ausgeschöpft ist, wird $p$ an $s$ aufgenommen.
Zeile $8-9$ : Falls die Kapazität der Schule ausgeschöpft ist, überprüft $s$ , ob es einen ihr zugeordneten Schüler $\tilde{p}$ gibt, den sie strikt weniger bevorzugt als $p$ , also $p \succ_s \tilde{p}$ .
Zeile $10$ : Falls es keinen solchen Schüler gibt, wird Schüler $p$ von Schule $s$ abgewiesen und streicht $s$ von seiner Präferenzliste.
Zeile $11-14$ : Falls es so einen Schüler $\tilde{p}$ gibt, verliert $\tilde{p}$ seinen Platz an $p$ . Der Schüler $\tilde{p}$ streicht $s$ von seiner Präferenzliste.
Zeile $15$ : Wenn es keinen Schüler $p$ gibt, der keiner Schule zugeordnet ist und dessen Präferenzliste nicht leer ist, gib Matching $M$ aus.

Verständnisfrage

Eigenschaften des Algorithmus

Mann-optimal

Satz

Der $EGS-SC$ liefert im Allgemeinen kein mann-optimales Matching.

Beweis

Beweis:^klo2017 Gegeben sind zwei Schüler $p_1, p_2$ und zwei Schulen $s_1, s_2$ , deren Kapazität $1$ beträgt. Die Präferenzen sind der Abbildung zu entnehmen.

Der $EGS-SC$ wird, abhängig von der Reihenfolge der gemachten Anträge entweder mit dem ersten (rötlich) oder zweiten (schwarz) Matching terminieren.

In beiden Matchings kann jeweils der Schüler, der mit $s_2$ gematcht ist, sich durch Schule $s_{1}$ verbessern und da { $p_1$ , $s_1$ } bzw. { $p_2,s_1$ } zulässig sind, sind beide Matchings nicht mann-optimal, wobei Schüler als Männer interpretiert werden. Insbesondere wird in diesem Beispiel unabhängig von der Reihenfolge der Anträge kein mann-optimales Matching gefunden. $\Box$

Stabilität

Lemma

Es sei $I$ eine Instanz des School-Choice-Problems ( $SC$ ) und $M$ ein Matching in $I$ . Dann ist $M$ genau dann schwach-stabil, wenn $M$ in einer Instanz des School-Choice-Problems ohne Indifferenzen ( $SC-OI$ ) $I'$ , die durch das künstliche Erzeugen einer strikten Ordnung entstanden ist, stabil ist.

Beweis

Beweis:^man2013^kla2020 $M$ in $I$ schwach-stabil $\Rightarrow$ $M$ in $I'$ stabil: Seien $P$ die Menge der Schüler und $S$ die Menge der Schulen in $I$ und $M$ ein schwach-stabiles Matching in $I$ , das $P$ und $S$ enthält.

Menge der Schüler: Es sei $P_{M}(I)$ die Menge der $SC-OI$ Instanzen, die durch das künstliche Erzeugen einer strikten Ordnung aus den Präferenzlisten (Tiebreaking) der Schüler in $I$ entstehen. Diese werden wie folgt erzeugt: Wenn $t$ eine Indifferenz auf einer Liste eines Schülers $p \in P$ ist und $M(p) \in t$ gilt, dann werden die restlichen Schulen $s$ , die in der Indifferenz vorkommen und nicht der zugeordneten Schule $M(p)$ entsprechen, so angeordnet, dass die zugeordnete Schule für $p$ strikt mehr von $p$ präferiert wird, als die restlichen in $t$ vorkommenden Schulen. Formal geschrieben, bedeutet dies: $M(p) \succ_{p} v$ für jedes $v \in t \setminus M(p)$ . Damit präferiert Schüler $p$ seine zugeordnetete Schule $M(p)$ gegenüber jeder anderen in $I$ zu $M(p)$ indiferrenten Schule $v$ .

Menge der Schulen: Die Menge $S_{M}(I)$ sei analog für die Menge Schulen in $I$ definiert. In diesem Fall werde aus einer Indifferenz $t$ auf der Liste einer Schule $s \in S$ , die einen Schüler $p \in M(s)$ enthält, so erzeugt, dass $v \succ_{s} w$ für jedes $v \in t \setminus M(s)$ und $w \in t \cap M(s)$ gilt.

Es sei $I' \in P_{M}(I) \cap S_{M}(I)$ , d.h. eine durch Tiebreaking entstandene $SC-OI$ Instanz. Nun zeigen wir über Kontraposition, dass die Existenz einer blockierenden Kante in $I'$ zu einem Widerspruch der Annahme, dass $M$ schwach-stabil in $I$ ist, führt.

Sei $\{p,s \}$ ein blockierendes Paar für $M$ in $I'$ . Dann ist in $I'$ der Schüler $p$ entweder nicht zugewiesen oder es gilt $s \succ_{p} M(p)$ . Zudem gilt für Schule $s$ , dass entweder die Kapazität noch nicht erschöpft ist oder es gilt für mindestens ein $v \in M(s) : p \succ_{s} v$ . Daraus folgt, dass dies auch in $I$ wahr ist, da $I'$ durch das künstliche Erzeugen einer strikten Ordnung auf $I$ entsprechend der obig beschriebenen Konstruktion gebildet wurde. Dementsprechend blockiert das Paar $\{p,s\}$ auch das Matching $M$ in $I$ , was der Voraussetzung, dass M schwach-stabil in $I$ ist widerspricht.

$M$ in $I'$ stabil $\Rightarrow$ $M$ in $I$ schwach-stabil: Angenommen $M$ ist stabil in einer $SC-OI$ Instanz $I'$ , das über Tiebreaking in einer $SC$ Instanz $I$ entstanden ist. Sei $b$ ein $M$ -blockierendes Paar in $I$ , dann blockiert $b$ auch das $M$ in $I'$ , was zu einem Widerspruch der Annahme führt. $\Box$

Satz

Der $EGS-SC$ liefert ein schwach-stabiles Matching.

Beweis

Betrachte Zeile $12$ im Pseudocode. Eine Schule $s$ ersetzt den für sie schlechtesten, zugeordneten Schüler $\tilde{p}$ mit dem Schüler $p$ nur, falls dieser strikt besser für $s$ ist und die Kapazität von $s$ ausgeschöpft ist.

Anders ausgedrückt, $p$ ersetzt $\tilde{p}$ nur, wenn diese nicht in derselben Indifferenz vorkommen und $p \succ_{s} \tilde{p}$ gilt, was als Bedingung in dem Tiebreaking-Verfahren der Schulen im vorherigen Beweis auch genutzt wurde. Die Präferenzlisten der Schüler besitzen in unserer Problemstellung keine Indifferenzen, weshalb wir diese nicht berücksichtigen. Damit folgt in Verbindung mit dem vorherigen Satz, dass der $EGS-SC$ in einem schwach-stabilen Matching terminiert. $\Box$

Kardinalitätsmaximalität

Satz

Der $EGS-SC$ liefert im Allgemeinen kein kardinalitätsmaximales Matching.

Beweis

Gegeben sind zwei Schüler $p_1, p_2$ und zwei Schulen $s_1, s_2$ , deren Kapazität $1$ beträgt. Die Präferenzen sind der angegebenen Abbildung zu entnehmen.

Schüler $p_1$ macht seiner favorisierten Schule $s_1$ einen Antrag, den $s_1$ annimmt. Der Schüler $p_2$ macht derselben Schule $s_1$ einen Antrag. Da die Kapazität der Schule $s_1$ erschöpft ist, vergleicht die Schule $p_1$ mit $p_2$ . Es gilt $p_2 \succ_{s_1} p_1$ . Schule $s_1$ entscheidet sich für $p_2$ . Der Schüler $p_1$ ist keiner Schule mehr zugeordnet und und streicht $s_1$ von seiner Präferenzliste. Die Präferenzliste von Schüler $p_1$ ist leer, weshalb der $EGS-SC$ mit dem Matching $M=\{ \{p_2, s_1 \}\}$ terminiert.

Sei $M_{max}$ das durch die rötlichen Kanten dargestellte kardinalitätsmaximale Matching. Es gilt $|M| < |M_{max}|$ . Damit findet der $EGS-SC$ im Allgemeinen kein kardinalitätsmaximales Matching. $\Box$

Weitere Eigenschaften

Da Instanzen des Stable Marriage-Problems Spezialfälle des School-Choice-Problems sind, in der alle Schüler und Schulen vollständige und strikte Präferenzlisten besitzen und zusätzlich alle Schulen eine Kapazität von $1$ haben, kann man die in den Beweisen genutzten Instanzen für den Gale-Shapley-Algorithmus auch hier verwenden. Es werden damit folgende Eigenschaften festgestellt.

Korollar

Der $EGS-SC$ liefert im Allgemeinen kein schülerseitig pareto-effizientes Matching.

Der $EGS-SC$ liefert im Allgemeinen kein schülerseitig rangmaximales Matching.

Der $EGS-SC$ ist im Allgemeinen nicht strategiesicher.

[MEG2020]: Megow, N., Vorlesung 11: Stabile Matchings, Operations Research, Universität Bremen, 2020.↩
[KLO2017]: Kloosterman, A. und Troyan, P., Efficient and Essentially Stable Assignments, University of Virginia, 2017.↩
[IRV1994]: Irving, Robert W. Stable marriage and indifference. Discrete Applied Mathematics. 43 (3): 261–272.↩
[KLA2020]: Klause, K. J., Matching mit Präferenzen: Theoretische und Experimentelle Evaluation von Algorithmen zur Schulplatzvergabe, Universität Bremen, 2020.↩
[MAN2013]: Manlove, D.F., Algorithmics of Matching under Preferences. World Scientific, 2013.↩