Das Gale-Shapley-Verfahren ist ein von David Gale und Lloyd Shapley (1962) entwickeltes Zuteilungsverfahren. Es ist das einzige Vergabeverfahren, welches sowohl stabil als auch strategiesicher ist. (Hier geht es zur Begriffserklärung: Stabilität und Strategiesicherheit)
In der Praxis wird dieses Verfahren v. a. in Lösungen wie KitaMatch eingesetzt.
Im Folgenden wird das Gale-Shapley-Verfahren ohne spezifische Anpassungen beschrieben. Grundsätzlich lässt sich sein Mechanismus relativ einfach auf komplexere Situationen — zum Beispiel Kitas mit unterschiedlichen Betreuungsplätzen bedingt durch Betreuungsumfänge und Alterskategorien anpassen.
Wir beschreiben, wie mit diesem Verfahren eine Zuteilung von Kindern auf die verfügbaren Kitaplätze basierend auf dem Kriterienkatalog bzw. den Prioritäten der Kitas und den Präferenzen der Eltern ermittelt wird.
Die Platzvergabe erfolgt grundsätzlich in vier einfachen Schritten, die nachfolgend graphisch dargestellt sind:
Zentrale Durchführung: Normalerweise wird das Gale-Shapley Verfahren zentral durchgeführt. Das heißt, die Prioritäten der Kitas und die Präferenzen bzw. Rankings der Bewerber werden zentral gesammelt und anschließend wird mittels des Gale-Shapley-Verfahrens die Zuteilung direkt ermittelt. Dies ist jedoch nicht immer optimal, weil Kitas beispielsweise zu keiner Zeit von den festgelegten Prioritäten abweichen können und damit die Trägerautonomie einschränkt wird.
Semizentrale Durchführung: Die koordinierte Vergabe von Kitaplätzen wird semizentral durchgeführt. In diesem Fall werden die Präferenzen bzw. Rankings der Bewerber zentral gesammelt, aber die Kitas nehmen dezentralisiert an der Vergabe teil, das heißt sie durchlaufen jeden Schritt der Vergabe einzeln. Dadurch ergibt sich die Möglichkeit, gegebenenfalls vom vorgegebenen Kriterienkatalog abzuweichen.
Zentrales Gale-Shapley-Verfahren
Schritt 1:
1 – Kitaangebote:
Kitas machen innerhalb der Matching-Software für jeden ihrer Plätze ein Angebot an einen Bewerber — und zwar der Reihe nach folgend beginnend mit den höchst priorisierten.
Alle weiteren Schritte (2, 3, 4, …):
2 – Bewerberannahmen:
Bewerber, die mindestens ein Angebot erhalten haben, nehmen das beste Angebot automatisch innerhalb der Matching-Software vorläufig an und geben den anderen Kitas, die ihnen in dieser Runde ebenfalls ein Angebot gemacht haben, eine definitive Absage.
1 – Kitaangebote:
Kitas, die mindestens eine Absage erhalten haben, machen ein neues Angebot pro Absage – außer sie haben keine Bewerber mehr, denen sie ein Angebot unterbreiten möchten. Kitas, bei denen kein einziges Angebot abgelehnt worden ist, machen kein weiteres Angebot.
2 – Bewerberannahmen:
Bewerber, die zusätzliche Angebote erhalten, können entweder ein neues Angebot vorläufig annehmen oder ihr derzeit gehaltenes Angebot beibehalten. Danach erteilen sie allen anderen Kitas, die ihnen in dieser Runde ein Angebot gemacht haben, eine definitive Absage.
3 – Ende:
Falls kein einziges neues Angebot gemacht wurde, ist eine finale Zuteilung erreicht. Bewerber haben einen Kitaplatz bei der Kita, deren Angebot sie zuletzt vorläufig gehalten haben — vorläufige Annahmen werden jetzt zu definitiven Annahmen. Bewerber, die kein Angebot halten, gehen leer aus.
Semizentrales Gale-Shapley-Verfahren
Schritt 1:
1 – Kitaangebote:
Gemäß ihrer vorsortierten Liste machen Kitas innerhalb der Matching-Software für jeden ihrer Plätze ein Angebot an einen Bewerber — und zwar der Reihe nach folgend generell beginnend mit den höchst priorisierten.
Dezentral: Aufgrund der semidezentralen Natur des Verfahrens haben Kitas jedoch die Flexibilität, bei Bedarf von dem Kriterienkatalog/Prioritäten abzuweichen.
Wichtig: Weicht eine Kita vom Kriterienkatalog ab, sollte dies begründet werden.
2 – Bewerberannahmen:
Bewerber nehmen automatisch innerhalb der Matching-Software ein Angebot vorläufig an und geben den anderen Kitas, die ihnen in dieser Runde ein Angebot gemacht haben, eine definitive Absage.
Zentralisiert: Dies geschieht automatisch über die hinterlegten Präferenzen.
Alle weiteren Schritte (2, 3, 4, …):
1 – Kitaangebote:
Kitas, die mindestens eine Absage erhalten haben, machen ein neues Angebot pro Absage Kitas, bei denen kein einziges Angebot abgelehnt worden ist, machen kein weiteres Angebot.
Dezentral: Auch in jedem dieser Schritte können Kitas bei Bedarf von dem Kriterienkatalog/den Prioritäten abweichen.
2 – Bewerberannahmen:
Bewerber, die zusätzlich Angebote erhalten, können entweder ein neues Angebot vorläufig annehmen oder ihr derzeit gehaltenes Angebot beibehalten. Dann erteilen sie allen anderen Kitas eine definitive Absage.
Zentralisiert: Dies geschieht automatisch über die hinterlegten Präferenzen.
3 – Ende:
Falls kein einziges neues Angebot gemacht wurde, ist eine finale Zuteilung erreicht: Bewerber haben einen Kitaplatz bei der Kita, deren Angebot sie halten. Bewerber, die kein Angebot halten, bleiben zunächst unversorgt.
Hier erfahren Sie mehr über die Grenzen des Gale Shapley-Verfahrens.
Begriffsklärung - Stabilität und Strategiesicherheit
An dieser Stelle werden grundlegende Begriffe eingeführt und erklärt, insbesondere wird auf die Begriffe der Stabilität und Strategiesicherheit eingegangen.
Das Gale-Shapley-Verfahren dient der Koordination von Präferenzen und Prioritäten von:
Bewerbern:
Eltern/Familien oder allgemein Erziehungsberechtigte, die Betreuungsplätze für ihre Kinder suchen, werden fortan als „Bewerber“ bezeichnet.
Kitas:
Kitaleitungen bzw. Trägervertretungen, welche Betreuungsplätze anbieten, werden von nun an als „Kitas“ bezeichnet.
Für das Funktionieren des Verfahrens werden deshalb drei Angaben der Beteiligten benötigt, eine aufseiten der Bewerber und zwei aufseiten der Kitas:
Für jede Kita eine Priorität über die Bewerber:
Prioritäten der Kitas bilden das Gegenstück zu den Rankings der Bewerber. Je höher die Priorität eines Bewerbers/Kindes für eine bestimmte Kita ist, das heißt die Punktzahl nach dem Kriterienkatalog, desto besser sind seine Chancen, in dieser Kita einen Platz zu bekommen. Wenn eine Kita zum Beispiel nur einen Platz für mehrere Bewerber hat, dann erhält das Kind mit der höchsten Priorität den Betreuungsplatz. Analog zu den Rankings der Bewerber kann grundsätzlich auch jede Kita ihre eigene Prioritätsreihenfolge haben.
Für jeden Bewerber ein Ranking über die Kitas:
Mit Rankings geben Bewerber Auskunft über ihre Präferenzen zu den jeweiligen Kitas. Mit der ersten Angabe benennt der Bewerber seine ,,Lieblingskita”, mit der zweiten die seiner Meinung nach zweitbeste Kita und so weiter.
Für jede Kita die Anzahl an verfügbaren Betreuungsplätzen:
“Betreuungsplätze” bezeichnet die Anzahl an neuen Bewerbern, die eine Kita während der Zuteilung aufnehmen kann.
Stabilität hat zwei Komponenten:
1
Kein Bewerber kann einer höher gerankten Kita zugeteilt werden: Falls “Bewerber A” eine Kita höher gerankt hat als die ihm zugeteilte Kita, dann ist diese Kita voll belegt und jeder dort zugeteilte Bewerber hat eine höhere Priorität als ,,Bewerber A”.
2
Keiner Kita können höher priorisierte Bewerber zugeteilt werden: Falls “Kita B” ein oder mehrere Bewerber nicht zugeteilt wurden, welche über höhere Prioritäten verfügen als mindestens einer der dort zugeteilten Bewerber, dann wurden diese Bewerber anderen – von ihnen höher gerankten – Kitas zugeteilt.
Die Strategiesicherheit der Bewerber hat zwei Komponenten:
1
Immunität gegen Verkürzen der Rankingliste: Ein Bewerber kann unter keinen Umständen eine bessere Kita zugeteilt bekommen, wenn er weniger Kitas auflistet.
2
Immunität gegen Ändern der Rankingliste: Ein Bewerber kann unter keinen Umständen eine bessere Kita zugeteilt bekommen, wenn er seine Reihenfolge der aufgelisteten Kitas ändert (“besser” wird nach der originalen/wahrheitsgemäßen Reihenfolge definiert).