Gale-Shapley verständlich erklärt

Eine Zuteilung kann fair aussehen und trotzdem zerbrechen, sobald zwei Beteiligte merken, dass sie einander lieber hätten als ihre Partner. Es gibt ein Verfahren, das genau das verhindert. Die Seite erklärt, wie es arbeitet, wem es nützt und was es kostet.

Zuletzt aktualisiert: 11. November 2026

Ein Wort unbekannt? Das Begriffsverzeichnis erklärt es in wenigen Sätzen.

Zwei, die einander lieber hätten

Stellen Sie sich vor, eine Hochschule teilt Praktikumsplätze zu. Jede Firma hat einen Platz, und jeder Studierende braucht einen. Alle haben eine Wunschliste: Die Studierenden reihen die Firmen, die Firmen reihen die Bewerber.

Die Verwaltung teilt zu: Lena kommt zur Firma Nord, Ben zur Firma Süd. Lena wäre aber lieber bei Süd, und Süd hätte lieber Lena als Ben. Beide finden das heraus und tun sich zusammen. Ben steht ohne Platz da, und Nord bleibt leer.

Zwei Beteiligte, die einander lieber hätten als ihre zugeteilten Partner, heißen blockierendes Paar. Gibt es keines, heißt die Zuteilung stabil: Niemand hat einen Grund, sich abzusetzen. Ein Verfahren dafür gibt es, wenn zwei getrennte Seiten einander zugeteilt werden, jeder höchstens einen Partner bekommt und jede Wunschliste eine klare Reihenfolge ohne Gleichstände hat.

So arbeitet das Verfahren

Das Verfahren heißt aufgeschobene Annahme (nach seinen Erfindern auch Gale-Shapley). Es läuft in Runden. Jeder Studierende ohne Platz fragt bei der Firma an, die auf seiner Liste am höchsten steht und die er noch nicht gefragt hat.

Die Firma sagt nur vorläufig zu und behält den besten Bewerber, den sie bisher hat. Kommt ein besserer, wechselt sie, und der bisherige ist wieder frei. Alle anderen Anfragen lehnt sie ab. Erst am Ende werden die Zusagen endgültig.

Wer abgelehnt oder ersetzt wurde, fragt die nächste Firma auf seiner Liste. Keiner fragt dieselbe Firma noch einmal, deshalb endet das Verfahren.

Warum ist das Ergebnis stabil? Nehmen wir an, Lena endet bei einer Firma, die sie weniger mag als Süd. Dann hat sie Süd vorher gefragt. Süd hat sie abgelehnt oder später ersetzt, weil jemand Besseres kam. Süd behält nur Besseres. Am Ende hat Süd also jemanden, den es mehr schätzt als Lena. Lena und Süd sind kein blockierendes Paar.

Wer fragt, hat den Vorteil

Das Verfahren ist nicht neutral. Wer fragt, bekommt die beste Firma, die in irgendeiner stabilen Zuteilung möglich ist. Die Firmen bekommen umgekehrt jeweils ihren schlechtesten Partner unter allen stabilen Zuteilungen. Der Grund: Eine Firma sagt nur ab, wenn sie schon jemanden hat, den sie lieber mag. Dieser Bessere hätte in keiner stabilen Zuteilung eine bessere Firma gefunden. Die Absage kostet den Fragenden also nichts, was er hätte haben können.

Ein kleines Beispiel: Lena mag Nord am liebsten, Ben mag Süd. Nord mag Ben am liebsten, Süd mag Lena. Fragen die Studierenden, bekommt jeder seine erste Wahl (Lena Nord, Ben Süd), die Firmen nur ihre zweite. Fragen die Firmen, ist es umgekehrt (Nord Ben, Süd Lena). Beide Zuteilungen sind stabil: Wer fragt, will nirgends mehr hin. Die Gefragten hätten gern jemand anderen, aber der will nicht wechseln. Nicht immer bekommt eine Seite lauter erste Wahlen; hier stoßen die Wünsche nur nicht zusammen.

Ein Rechenbild mit Lieferwagen

Wie oft gibt es mehrere stabile Zuteilungen? Das lässt sich nur an vielen Fällen zählen. Dazu dient ein vereinfachtes Rechenbild (Fachwort: Modell) mit erfundenen Daten. Es zuteilt Lieferwagen zu Aufträgen auf einer Karte, statt Studierende zu Firmen. Ein Lieferwagen kommt nur für Aufträge infrage, die nicht zu weit entfernt liegen; wie weit, heißt Reichweite. Beide Seiten reihen ihre möglichen Partner. Gerechnet wird auf 100 Karten mit je 20 Lieferwagen und 20 Aufträgen. Die Aussagen in diesem Teil beschreiben das Rechenbild, nicht die Wirklichkeit.

Drei Fälle wurden verglichen, je nachdem, woher die Wünsche kommen:

• Beide Seiten ordnen nach der Fahrzeit. Jedes Paar hat dann eine gemeinsame Note, den Weg. Bei mittlerer Reichweite gab es auf allen 100 Karten genau eine stabile Zuteilung. Wer fragt, ist gleichgültig.
• Jede Seite schätzt die Fahrzeit selbst und liegt mal einige Minuten daneben. Bei mittlerer Reichweite gab es auf 34 von 100 Karten mehrere stabile Zuteilungen. Nur dort entscheidet, wer fragt.
• Die Wünsche sind zufällig, ohne Bezug zum Weg. Wenn jeder Lieferwagen jeden Auftrag erreicht, gab es auf allen 100 Karten mehrere stabile Zuteilungen.

Warum gibt es bei gemeinsamer Note nur eine Lösung? Das Paar mit dem kürzesten Weg wollen beide am liebsten. Es muss in jeder stabilen Zuteilung vorkommen, sonst würde es sich absetzen. Dasselbe gilt dann für das kürzeste der übrigen Paare, und so weiter.

Bei zufälligen Wünschen und voller Erreichbarkeit bekam der Fragende im Mittel etwa seine dritte Wahl, die gefragte Seite etwa ihre sechste. Fragten die Aufträge, kehrte es sich um.

Was Stabilität kostet

Stabil heißt nicht billig. Die billigste Einteilung schaut nur auf die Summe der Fahrzeiten. Dafür darf sie ein Paar auseinanderhalten, das einander lieber hätte, wenn der Rest dadurch billiger wird. Bei mittlerer Reichweite und Wünschen nach dem Weg war sie deshalb auf allen 100 Karten nicht stabil.

Schätzt jede Seite den Weg selbst, kostete die stabile Zuteilung im Median (dem mittleren Wert aller Karten) knapp ein Viertel mehr Fahrzeit als die billigste Einteilung, die genauso viele Paare bildet. Mit gleich vielen Paaren wird verglichen, weil weniger Paare schon von selbst billiger wären. Zudem blieben im Mittel gut zwei Paare weniger übrig, denn ein früh gefundenes Wunschpaar kann zwei andere verhindern.

Bei zufälligen Wünschen und voller Erreichbarkeit kostete die stabile Zuteilung im Median mehr als doppelt so viel Fahrzeit wie die billigste. Bei sehr knapper Reichweite und Wünschen nach dem Weg kostete Stabilität dagegen im Median nichts. Die billigste Einteilung war dort auf 79 von 100 Karten selbst stabil: Es gibt wenig Auswahl und kaum Gelegenheit, einander vorzuziehen.

Häufige Missverständnisse

• „Stabil heißt gerecht oder am besten für alle.“ Nein. Stabil sagt nur, dass sich kein Paar absetzen will, nicht wie teuer die Zuteilung ist oder wer wie gut wegkommt.
• „Wer auf der fragenden Seite zuerst dran ist, gewinnt.“ Nein. Das Ergebnis hängt nicht von der Reihenfolge ab, denn jede Zusage ist nur vorläufig.
• „Eine stabile Zuteilung gibt es immer.“ Nicht in jeder Lage. Sollen sich Menschen innerhalb einer einzigen Gruppe zu Paaren finden, etwa Mitbewohner, kann sie fehlen. Mögen sich A, B und C im Kreis am liebsten (A mag B, B mag C, C mag A) und alle drei D am wenigsten, setzt sich bei jeder Aufteilung in zwei Paare eines ab.

Woran Sie das im Alltag erkennen

• Nach einer Zuteilung von Kita- oder Wohnheimplätzen tauschen zwei Beteiligte hinter dem Rücken der Verwaltung. Beide gewinnen dabei: ein blockierendes Paar.
• Eine Seite darf zuerst anfragen, etwa wenn sich Bewerber bei Firmen bewerben. Gibt es mehrere stabile Lösungen, bevorzugt das die anfragende Seite.

Wie ernst ist das Rechenbild zu nehmen?

Echte Zuteilungen haben Gleichstände, mehrere Plätze und Absprachen, die das Rechenbild nicht kennt. Die Zahlen zeigen daher nur die Richtung.

Was Sie mitnehmen

• Prüfen Sie jede Zuteilung mit einer Frage: Gibt es zwei, die einander lieber hätten als ihre Partner?
• Fragen Sie vor einem Auswahlverfahren, wer den ersten Schritt tun darf. Davon kann abhängen, wer sein Wunschergebnis bekommt.
• Stabilität und niedrige Kosten sind zwei verschiedene Ziele. Entscheiden Sie vorher, welches Vorrang hat.

Zu dieser Seite gehört ein Programm zum Ausprobieren im Browser, die Demo. Sie erreichen es über den ersten Knopf unten. Zum Verstehen brauchen Sie es nicht. Der zweite Knopf führt zum zweiten Teil für Fachleute.

Hinweis: Alle Demos rechnen mit synthetischen oder frei verfügbaren Beispieldaten und laufen auf einem externen Anbieter (Datenschutz). Bitte geben Sie darin keine vertraulichen oder personenbezogenen Daten ein. Die Ergebnisse gelten für die jeweilige Demo-Instanz und lassen sich nicht ungeprüft auf reale Fälle übertragen; für darauf gestützte Entscheidungen übernehme ich keine Gewähr.

Modell und Annahmen

Dieser Teil ist eigenständig lesbar. Er behandelt das Problem der stabilen Paarung zweier getrennter Seiten mit strikten Rangfolgen und das Verfahren der aufgeschobenen Annahme von Gale und Shapley (Quellen am Ende). Gemessen wird es auf erfundenen Karten mit Fahrzeugen und Aufträgen.

• Beteiligte und mögliche Paare: \(V\) ist die Menge der Fahrzeuge, \(O\) die der Aufträge, \(E \subseteq V \times O\) die Menge der möglichen Paare. Fahrzeuge und Aufträge sind Punkte auf einer Karte; die Fahrzeit \(c_{vo}\) ist die aufgerundete Entfernung in Minuten. Ein Paar ist möglich, wenn \(c_{vo}\) höchstens die Reichweite beträgt. Die Listen sind also unvollständig; ein mögliches Paar steht auf beiden Listen, ein unmögliches auf keiner.
• Vorlieben: Jedes Fahrzeug \(v\) hat eine strikte Rangfolge \(\succ_v\) über seine möglichen Aufträge, jeder Auftrag \(o\) eine Rangfolge \(\succ_o\) über seine möglichen Fahrzeuge. Drei Modelle: Nur Entfernung (beide Seiten ordnen nach \(c_{vo}\)); Entfernung mit Streuung (Voreinstellung): jede Seite ordnet nach \(c_{vo} + \varepsilon\), wobei \(\varepsilon\) je Seite und Paar eine unabhängige ganze Zahl zwischen \(-s\) und \(s\) Minuten ist; Zufall: unabhängig von den Kosten. Gleichstände werden nach dem Index gebrochen, die Listen sind also strikt.
• Zufallszahlen: Ein eigener ganzzahliger Generator liefert \(\varepsilon = \lfloor (2s+1)\,u / 2^{20} \rfloor - s\) mit gleichverteiltem ganzem \(u \in [0, 2^{20})\) je Seite, Fahrzeug und Auftrag. Das \(u\) hängt nicht von \(s\), der Reichweite oder der Kartengröße ab, sodass Reihen über \(s\) glatt verlaufen.
• Voreinstellung: 20 Fahrzeuge, 20 Aufträge, Reichweite 40, Entfernung mit Streuung \(s = 20\), Fahrzeuge schlagen vor. Bei Reichweite 150 ist auf den Karten alles erreichbar.
• Vergleichsmaßstab: Das Optimum der Ungarischen Methode hat die größtmögliche Paarzahl und unter diesen die geringsten Kosten. Zwei einfache Regeln dienen zum Vergleich: „Billigste Kante zuerst“ nimmt immer das billigste mögliche Paar, „Auftrag für Auftrag“ gibt den Aufträgen der Reihe nach das nächste freie Fahrzeug. Weil Kosten über verschiedene Paarzahlen nicht vergleichbar sind, misst der Preis der Stabilität die Mehrkosten gegenüber der billigsten Paarung mit derselben Paarzahl; die verlorenen Paare stehen getrennt.
• Messreihe: 100 feste Karten; Mittel und Median stehen zusammen. Je Karte werden alle stabilen Paarungen über Rotationen aufgezählt, und ein unabhängiger Prüfer sucht blockierende Paare mit einer Doppelschleife über alle möglichen Paare.

Die Formeln

Stabilität. Eine Paarung \(M \subseteq E\) ist gültig, wenn jedes Fahrzeug und jeder Auftrag höchstens einmal vorkommt. Ein Paar \((v,o) \in E \setminus M\) blockiert \(M\), wenn \(o \succ_v M(v)\) und \(v \succ_o M(o)\) gilt; wer in \(M\) allein ist, zieht jeden möglichen Partner vor. \(M\) heißt stabil, wenn es gültig ist und kein blockierendes Paar hat.

Aufgeschobene Annahme. Solange ein Vorschlagender \(p\) frei ist und noch Einträge übrig hat, fragt er den besten noch nicht gefragten Empfänger \(r\). Ist \(r\) frei oder zieht \(p\) seinem Halter vor, hält \(r\) vorläufig \(p\) und lässt den bisherigen Halter frei; sonst lehnt \(r\) ab. Jeder Vorschlagende fragt jeden Empfänger höchstens einmal. Daraus folgen höchstens \(|E|\) Vorschläge, bei vollständigen Listen der Größe \(n\) höchstens \(n^2 - n + 1\). Auf vollständigen Zufallslisten ist \(n H_n\) mit der harmonischen Zahl \(H_n = \sum_{i=1}^{n} 1/i\), also etwa \(n \ln n\), die bekannte Größenordnung für die Vorschlagenden (Obergrenze bzw. Asymptotik, nicht nachgelesen). Gemessen liegt der Mittelwert bei kleinem \(n\) darunter (Befunde). Vorschlagende sind die Fahrzeuge oder die Aufträge.

Sätze (Gale und Shapley, McVitie und Wilson, Roth; für diese Seite nicht nachgelesen und nicht einzeln den Aufsätzen zugeordnet):

• Das Ergebnis ist stabil.
• Es hängt nicht von der Reihenfolge der Vorschläge ab. Es ist für die Vorschlagenden die beste stabile Paarung (jeder hat den besten Partner, den er in irgendeiner stabilen Paarung bekommt) und für die Empfänger die schlechteste.
• Landklinikensatz: In allen stabilen Paarungen sind dieselben Agenten versorgt, die Paarzahl ist gleich.
• Jede stabile Paarung ist maximal (nicht erweiterbar), hat also mindestens \(\nu/2\) Paare, wobei \(\nu\) die Größe einer größtmöglichen Paarung ist.

Verband. Die stabilen Paarungen bilden einen distributiven Verband. Von der für die Fahrzeuge besten Paarung aus erhält man alle anderen über Rotationen: Für ein versorgtes Fahrzeug \(v\) sei \(s(v)\) der erste Auftrag unterhalb seines Partners auf seiner Liste, der \(v\) seinem jetzigen Halter vorzieht. Das Fahrzeug \(v\) zeigt auf den Halter von \(s(v)\). Ein Kreis solcher Zeiger heißt Rotation; sie schiebt jedes Fahrzeug des Kreises auf sein \(s(v)\), schlechter für die Fahrzeuge und besser für die Aufträge. Lässt die aktuelle Paarung \(s(v)\) unversorgt, endet die Kette dort in einer Sackgasse: Nach dem Landklinikensatz bleibt dieser Auftrag in jeder stabilen Paarung unversorgt. Die Aufzählung ist auf 2000 stabile Paarungen begrenzt, weil die Anzahl mit der Kartengröße stark wächst (Befunde).

Preis der Stabilität. Die Grenzkosten \(W_k\) der Ungarischen Methode sind die Mehrkosten des \(k\)-ten Paares, wenn man von der billigsten Paarung mit \(k-1\) Paaren zu der mit \(k\) Paaren übergeht. Damit sind \(\sum_{i \le k} W_i\) die Kosten der billigsten Paarung mit \(k\) Paaren. Hat eine stabile Paarung \(M\) genau \(k\) Paare, ist ihre Prämie (in den Befunden in Prozent):

\[(c(M)-\sum_{i\le k}W_i)/\sum_{i\le k}W_i\]

Reine Entfernung. Ordnen beide Seiten nach derselben Kostenmatrix \(c\) (mit Index-Tie-Break), gibt es eine gemeinsame Rangfolge aller Paare: Das billigste Paar ist in jeder stabilen Paarung enthalten, das zweitbilligste unter den übrigen und so fort. Die eindeutige stabile Paarung ist deshalb genau die der Regel „Billigste Kante zuerst“.

Herleitungen Schritt für Schritt

Die folgenden Herleitungen sind Rechnungen dieser Seite, Beweisskizzen für die genannten Aussagen, keine Messungen. Gleichstände bleiben hier außer Acht (die Demo bricht sie nach dem Index).

A. Das Ergebnis der aufgeschobenen Annahme ist stabil.

• Schritt 1: Hat ein Empfänger \(r\) einmal einen Halter, bleibt er versorgt, und seine Halter werden bezüglich \(\succ_r\) immer besser: Er wechselt nur zu einem besseren Vorschlag.
• Schritt 2: Ein Vorschlagender \(p\) arbeitet seine Liste von oben nach unten ab. Endet er bei \(M(p)\), hat er jeden Empfänger \(r \succ_p M(p)\) schon gefragt; ist er am Ende unversorgt, hat er seine ganze Liste gefragt.
• Schritt 3: Angenommen, \((p,r)\) blockiert die Endpaarung \(M\), also \(r \succ_p M(p)\) und \(p \succ_r M(r)\). Nach Schritt 2 hat \(p\) den Empfänger \(r\) gefragt. Weil \(p\) danach weiterfragte, hat \(r\) ihn abgelehnt oder später durch einen besseren Vorschlag verdrängt. In beiden Fällen hält \(r\) von da an jemanden \(h \succ_r p\).
• Schritt 4: Nach Schritt 1 ist der Endpartner \(M(r)\) mindestens so gut wie \(h\), also \(M(r) \succ_r p\). Das widerspricht \(p \succ_r M(r)\). Also gibt es kein blockierendes Paar. Das Verfahren endet, weil es höchstens \(|E|\) Vorschläge gibt.

B. Bei gemeinsamer Wertung gibt es genau eine stabile Paarung.

• Schritt 1: Ordnen beide Seiten nach derselben Kostenmatrix, sei \((v,o)\) das Paar mit dem kleinsten \(c_{vo}\). Dann ist \(o\) die erste Wahl von \(v\) und \(v\) die erste Wahl von \(o\).
• Schritt 2: Liegt \((v,o)\) nicht in einer Paarung \(M\), ziehen beide einander ihren Partnern oder dem Alleinsein vor: \((v,o)\) blockiert \(M\). Jede stabile Paarung enthält also dieses Paar.
• Schritt 3: Streicht man \(v\) und \(o\), bleibt eine kleinere Aufgabe derselben Art, und eine stabile Paarung der großen Aufgabe ist darauf stabil, weil die Partner dieselben bleiben. Wiederholt man den Schluss, ist jede stabile Paarung durch die Regel „Billigste Kante zuerst“ festgelegt. Dass es mindestens eine gibt, folgt aus Herleitung A. Also gibt es genau eine.

C. Die Vorschlagszahl und die Straße.

• Schritt 1: Jeder Vorschlagende \(p\) fragt seine Liste von oben nach unten und fragt jeden Eintrag einmal. Sei \(\rho_p(r)\) der Rang des Empfängers \(r\) in der Liste von \(p\), der erste Eintrag hat den Rang 0. Der Vorschlagende fragt genau bis zu seinem Endpartner: \(\rho_p(M(p)) + 1\) Vorschläge; bleibt er unversorgt, so viele, wie seine Liste Einträge hat.
• Schritt 2: Die Vorschlagszahl ist die Summe dieser Werte über alle Vorschlagenden.
• Schritt 3 (Straße): Die Straße ist eine Testkarte, auf der alle Fahrzeuge und Aufträge auf einer Geraden liegen. Dort reihen alle Fahrzeuge die Aufträge gleich und alle Aufträge die Fahrzeuge gleich. Dann paart die stabile Paarung (nach B) das \(k\)-te Fahrzeug in der gemeinsamen Rangfolge, mit der alle Aufträge die Fahrzeuge ordnen, mit dem \(k\)-ten Auftrag in der gemeinsamen Rangfolge, mit der alle Fahrzeuge die Aufträge ordnen. Ein Vorschlagender mit diesem Partner hat den Rang \(k-1\) und braucht \(k\) Vorschläge. Die Summe über \(k = 1, \dots, n\) ist \(n(n+1)/2\). Das gilt für beide Vorschlagende.

Durchgerechnetes Beispiel mit vier mal vier

Rechnung dieser Seite, keine Messung der Demo. Das Beispiel stammt aus der Einleitung der Arbeit von Knuth, Motwani und Pittel zu stabilen Ehemännern; die Beteiligten sind hier umbenannt (Fahrzeuge \(P, Q, R, S\), Aufträge \(A, B, C, D\)). Die Rangfolgen, beste zuerst:

Beteiligter	Rangfolge
Fahrzeug \(P\)	A, B, D, C
Fahrzeug \(Q\)	C, A, D, B
Fahrzeug \(R\)	B, D, A, C
Fahrzeug \(S\)	B, A, C, D
Auftrag \(A\)	R, Q, S, P
Auftrag \(B\)	Q, P, R, S
Auftrag \(C\)	P, R, Q, S
Auftrag \(D\)	Q, P, S, R

Die Fahrzeuge schlagen vor, in der Reihenfolge \(P, Q, R, S\):

Vorschlag	Ausgang
\(P\) fragt \(A\)	\(A\) ist frei und hält \(P\).
\(Q\) fragt \(C\)	\(C\) ist frei und hält \(Q\).
\(R\) fragt \(B\)	\(B\) ist frei und hält \(R\).
\(S\) fragt \(B\)	\(B\) zieht \(R\) dem \(S\) vor: Absage.
\(S\) fragt \(A\)	\(A\) zieht \(S\) dem \(P\) vor: \(A\) hält \(S\), \(P\) wird frei.
\(P\) fragt \(B\)	\(B\) zieht \(P\) dem \(R\) vor: \(B\) hält \(P\), \(R\) wird frei.
\(R\) fragt \(D\)	\(D\) ist frei und hält \(R\).

Nach sieben Vorschlägen steht die Paarung \((A,S), (B,P), (C,Q), (D,R)\). Probe der Vorschlagszahl nach Herleitung C: \(P\) bekommt \(B\) (Rang 1), \(Q\) bekommt \(C\) (Rang 0), \(R\) bekommt \(D\) (Rang 1), \(S\) bekommt \(A\) (Rang 1). Die Summe von Rang plus 1 ist sieben. Schlagen die Aufträge vor, entsteht die Paarung \((A,R), (B,P), (C,Q), (D,S)\): Nur \(A\), \(D\), \(R\), \(S\) wechseln den Partner, \(A\) und \(D\) stehen besser, \(R\) und \(S\) schlechter. Laut der Quelle sind dies die einzigen beiden stabilen Paarungen. Zum Vergleich blockiert \((S,A)\) die Paarung \((A,P), (B,Q), (C,R), (D,S)\): \(S\) zieht \(A\) seinem Partner \(D\) vor, und \(A\) zieht \(S\) ihrem Partner \(P\) vor.

Befunde

Alle Zahlen stammen aus der Messreihe auf 100 festen erfundenen Karten mit 20 Fahrzeugen und 20 Aufträgen, Reichweite 40 und Fahrzeugen als Vorschlagenden, wo nichts anderes steht. Aufwand zählt Vorschläge, keine Sekunden. Ränge zählen ab 0 für die erste Wahl. „Mehrere stabile Paarungen“ meint mehr als eine.

Frage	Befund
Reine Entfernung: wie viele stabile Paarungen?	Auf allen 100 Karten genau eine, gleich der Paarung der Regel „Billigste Kante zuerst“. Sie hat im Mittel 16,7 Paare, das Optimum 19,5; Prämie im Median 3,4 % (Mittel 4,0 %).
Reine Entfernung: ist das Optimum stabil?	Auf allen 100 Karten nicht: im Mittel 13,2 blockierende Paare (Median 12). Die Regel „Auftrag für Auftrag“ hat im Mittel 11,1 (Median 10,5).
Streuung 20 (Voreinstellung): mehrere stabile Paarungen?	Auf 34 von 100 Karten, im Mittel 1,6 stabile Paarungen, höchstens 8. Nur auf diesen Karten ändert die Wahl der Vorschlagenden das Ergebnis. Prämie im Median 24,3 % (Mittel 25,8 %), im Mittel 2,25 Paare weniger als das Optimum. Bei Reichweite 150: 47 von 100 Karten, höchstens 12 stabile Paarungen, Prämie im Median 26,0 %.
Zufallsvorlieben: mehrere stabile Paarungen?	Reichweite 150: auf allen 100 Karten, im Mittel 6,35 (Median 6, höchstens 22), Prämie im Median 162 % (Mittel 168 %). Reichweite 40: auf 40 von 100 Karten, Prämie im Median 64,6 %.
Wer vorschlägt, gewinnt?	Zufall, Reichweite 150: Der Vorschlagende bekommt im Mittel Rang 2,2, der Empfänger 4,9. Schlagen die Aufträge vor, sind es 5,2 (Fahrzeuge) und 2,0 (Aufträge). Die Gesamtkosten unterscheiden sich wenig: 1 079 Minuten (Fahrzeuge schlagen vor) gegen 1 068 (Aufträge schlagen vor).
Kurze Reichweite?	Reichweite 10, nur Entfernung: Das Optimum ist auf 79 von 100 Karten selbst stabil, die Prämie liegt im Median bei 0 % (Mittel 0,07 %).
Ungleich große Seiten?	10 Fahrzeuge, 20 Aufträge (Reichweite 150, Streuung 20): Schlagen die Fahrzeuge vor, sind es im Mittel 14,5 Vorschläge (Median 14), schlagen die Aufträge vor 120,8 (Median 120). Die unversorgten Aufträge gehen ihre Listen ganz durch. Die Paarzahl 10 ist in jeder stabilen Paarung gleich.
Wie wirkt die Streuung?	Streuung 0 bis 60 Minuten, Reichweite 40, 40 Karten je Wert: Die Prämie im Median steigt streng von 3,9 % auf 48,1 %, die verlorenen Paare sinken von 2,65 auf 1,85. Bei Streuung 0 gibt es nie mehr als eine stabile Paarung.
Wie viele stabile Paarungen bei wachsender Karte?	Zufallsvorlieben, alles erreichbar, \(n = m\) gleich 4 / 8 / 12 / 20 / 40, 40 Karten je Größe: im Mittel 1,57 / 2,52 / 3,27 / 5,8 / 14,47 stabile Paarungen (höchstens 30 bei \(n = 40\)). Der Anteil der Karten, auf denen die beiden Extrempaarungen verschieden sind, wächst von 42 % auf 100 %. Mit Streuung 20 sind es nur 1,02 bis 2,4. Die Mittel sind so gerundet wie in der Demo; die exakten Mittel über 40 Karten sind Brüche mit dem Nenner 40 und liegen, außer bei 5,8 und 2,4, jeweils eine halbe Einheit der letzten Stelle höher (Rechnung dieser Seite).
Wie wächst der Aufwand?	Vollständige Zufallslisten, Mittel über 5 Karten: 18 / 52 / 159 / 359 / 1 025 / 2 031 Vorschläge bei \(n\) gleich 10 / 20 / 40 / 80 / 160 / 320. Das Verhältnis zu \(n H_n\) beträgt bei \(n = 10\) nur etwa drei Fünftel, bei \(n = 40\) gut neun Zehntel und bei \(n = 320\) etwa eins (Rechnung dieser Seite aus den Mittelwerten, mit Rauschen wegen nur 5 Karten). Bei konstantem mittlerem Grad wächst er fast linear (19 bis 940, Steigung etwa 1,1 in doppelt logarithmischer Auftragung, bei nur 5 Karten je Größe ungenau). Entfernungslisten (vollständig) wachsen schneller (4 372 bei \(n = 320\)). Die Straße (Karte mit gleich geordneten Listen, Herleitung C) braucht genau \(n(n+1)/2\) Vorschläge (55 / 210 / 820 bei \(n\) gleich 10 / 20 / 40); die Schranke \(n^2 - n + 1\) wird dort nicht erreicht.
Lohnt sich Lügen?	Erschöpfend auf 5 × 5-Karten (20 Karten, alle geordneten Teillisten, Zufallsvorlieben): Kein Fahrzeug (Vorschlagender) kann gewinnen (0 von 100), 32 von 100 Aufträgen (Empfänger) können, genau die mit verschiedenen Extrempaarungen. Kürzen auf einen einzigen Eintrag, den auftragsoptimalen Partner, sichert diesen Partner in 32 von 32 Fällen. Bei Streuung 20 gibt es auf 5 × 5 nichts zu gewinnen.

Grenzen und was die Messung zeigt

• Was sie belegt: Richtung und Größenordnung auf erfundenen Karten mit 20 Fahrzeugen und 20 Aufträgen, als Mittel und Median über 100 feste Karten. Die Sätze sind keine Messung. Ein vom Verfahren getrennter Prüfer sucht blockierende Paare mit einer Doppelschleife, und an kleinen Karten (höchstens 5 Fahrzeuge und Aufträge, 120 Karten) stimmt die Aufzählung über Rotationen mit dem Durchprobieren aller Paarungen überein.
• Was sie nicht belegt: echte Wünsche. Streuung und Zufall sind Annahmen der Demo. Die Eindeutigkeit bei reiner Entfernung folgt aus Herleitung B und gilt für jede gemeinsame Wertung; gemessen ist sie auf den 100 Karten und zusätzlich in sechs Einstellungen mit je 30 Karten (180 Karten, 30 davon gehören auch zur Messreihe). Frühere Vorversuche mit anderen gemeinsamen Kriterien (Zusatzattribut, Gewichte, Profit, Geschwindigkeit) fanden dasselbe, sind aber nicht Teil der Messreihe.
• Streuung: Der Anteil der Karten mit mehreren stabilen Paarungen wächst bei Reichweite 40 von null auf gut ein Drittel, ist aber nicht streng monoton: Bei Streuung 40 liegt er etwas unter dem bei Streuung 30, ebenso die mittlere Anzahl stabiler Paarungen (Nachrechnung dieser Seite aus der Reihe mit 40 Karten je Wert, nicht in der Befundtabelle). Aussagen wie „je größer die Streuung, desto mehr stabile Paarungen“ gelten deshalb nur im Trend.
• Optimum und Prämie: Die Prämie hängt am Maßstab der billigsten Paarung mit gleicher Paarzahl. Das Optimum ist bei kurzer Reichweite oft selbst stabil; die Aussage „das Optimum ist instabil“ gilt pro Einstellung, nicht allgemein.
• Aufwand: \(n H_n\) ist nur für vollständige Zufallslisten die Größenordnung (Obergrenze bzw. Asymptotik); die Mittel über 5 Karten liegen bei kleinem \(n\) deutlich darunter; bei konstantem mittlerem Grad ist der Aufwand fast linear, bei Entfernungslisten größer. Die Straße gilt in der Demo nur bis \(n = 40\), danach überlappen sich Fahrzeuge und Aufträge auf der Geraden.
• Lügen: Der Befund stammt von 5 × 5-Karten mit Zufallsvorlieben; für größere Karten ist er gemessen nicht belegt. Dass Vorschlagende nicht gewinnen können, ist ein Satz (Dubins und Freedman, Roth), keine Messung.
• Annahmen des Modells: zwei getrennte Seiten, ein Partner je Agent, strikte Listen, alles vorab bekannt. Bei Gleichständen gibt es schwache und starke Stabilität; Herleitung B setzt strikte Rangfolgen voraus, und andere Gleichstandsregeln als der Index-Tie-Break sind nicht gemessen. In der Reihe zur Anzahl stabiler Paarungen wurde die Grenze von 2000 nicht erreicht.

Erweiterungen und Verweise

Jede Annahme des Modells ist der Ansatzpunkt einer anderen Demo der Matching-Reihe:

• Billigste Kante zuerst: Die Regel, die bei gemeinsamer Wertung die stabile Paarung liefert, erklärt die Seite zum Greedy-Matching.
• Kosten statt Vorlieben: Die hungarian-demo (Ungarische Methode) liefert das billigste Optimum, mit dem hier die Prämie gemessen wird.
• Eine einzige Gruppe statt zwei Seiten: In den stabilen Mitbewohnern muss keine stabile Paarung existieren.
• Mehrere Plätze je Agent: Die Krankenhaus-Zulassung behandelt Kapazitäten (many-to-one).
• Jeder besitzt schon etwas: Top Trading Cycles tauscht Güter ohne Geld, statt Vorlieben zu paaren.
• Kompatibilität statt Präferenz: Der Nierentausch arbeitet mit Kompatibilitätsgraphen und kurzen Zyklen.
• Alles vorab bekannt: Im Online-Matching kommen die Aufträge nacheinander.

Quellen

• Gale, D., Shapley, L. S. (1962): College admissions and the stability of marriage. American Mathematical Monthly 69(1), 9–15 (aufgeschobene Annahme, Stabilität, Optimalität für die Vorschlagenden; daraus folgt die Unabhängigkeit von der Reihenfolge der Vorschläge).
• McVitie, D. G., Wilson, L. B. (1971): The stable marriage problem. Communications of the ACM 14(7), 486–490 (rekursive Formulierung des Verfahrens, Aufzählung aller stabilen Paarungen).
• Roth, A. E. (1982): The economics of matching: stability and incentives. Mathematics of Operations Research 7(4), 617–628 (Anreize der Empfänger).
• Dubins, L. E., Freedman, D. A. (1981): Machiavelli and the Gale-Shapley algorithm. American Mathematical Monthly 88(7), 485–494 (Vorschlagende können durch falsche Angaben nichts gewinnen).
• Knuth, D. E., Motwani, R., Pittel, B.: Stable husbands (Vorabdruck arXiv math/9201303; Beispiel mit zwei stabilen Paarungen).
• Quelltext, Tests und Messungen der Demo: github.com/sebastian-hanisch/gale-shapley-demo.

Die Namen Gale und Shapley, McVitie und Wilson, Roth sowie Dubins und Freedman stehen in der Dokumentation der Demo; Jahrgänge, Zeitschriften und Seitenzahlen sind aus dem Gedächtnis, nicht im Original geprüft. Das Beispiel der Arbeit von Knuth, Motwani und Pittel wurde mit dem Code der Demo nachgerechnet; die Arbeit selbst ist für diese Seite nicht erneut nachgeschlagen. Herleitungen und das Beispiel mit vier Fahrzeugen sind Rechnungen dieser Seite und keine Messungen der Demo.