Das School-Choice-Problem


Bildquelle: Austrian National Library, Unsplash.

Problembeschreibung

Bei dem School-Choice-Problem geht es darum, Schüler Schulen zuzuteilen. Dabei sollen die Präferenzen der Schüler, welche Schule sie besuchen möchten, sowie die Präferenzen der Schulen bezüglich der Schüler Berücksichtigung finden. Zudem dürfen bei der Zuordnung die Platzkapazitäten der Schulen nicht überschritten werden. Das School-Choice-Problem ist ein Fall von Matching unter Präferenzen und insofern verwandt mit dem Stable-Matching-Problem.

Mathematisch modellieren wir dieses Problem mithilfe eines bipartiten Graphen GG = (PP ∪\cup SS, EE). Dabei bezeichnet PP die Menge der Schüler und SS die Menge der Schulen. Jede Schule s ∈ Ss~\in~S hat eine feste Kapazität csc_s ∈\in N\mathbb{N} an Schulplätzen. Die Kantenmenge EE stellt akzeptable Zuweisungen dar. Zwischen einem Knoten ss ∈\in SS und einem Knoten pp ∈\in PP existiert genau dann eine Kante {s,p}\{s,p\} ∈\in EE, wenn ss in der Präferenzliste von pp enthalten ist.

Die Präferenzen der Schüler und Schulen liegen in Form von geordneten Mengen vor. In vielen Zulassungsverfahren sind die Präferenzlisten der Schüler verkürzt, d.h. das Ranking, das die Schüler erstellen, umfasst nicht die Gesamtzahl der Schulen (z.B. Angabe von drei Wunschschulen). Die Präferenzlisten der Schulen ordnen die Schüler anhand der Prioritäten der jeweiligen Schule (z.B. ein bestimmter Notendurchschnitt oder Geschwisterkinder, welche dieselbe Schule besuchen). Da Schulen üblicherweise nur wenige Prioritäten haben, gehören viele Schüler derselben Prioritätsklasse an. Zwischen Schülern derselben Prioritätsklasse sind Schulen indifferent.

Die Lösung des School-Choice-Problems ist ein b-Matching MM ⊆\subseteq EE, sodass jeder Knoten p ∈ Pp~\in~P mit maximal einem Knoten s ∈ Ss~\in~S verbunden ist und jeder Knoten s ∈ Ss~\in~S mit maximal csc_s Knoten aus PP verbunden ist.

Die zur Lösung des School-Choice-Problems verwendeten School-Choice-Algorithmen bekommen also zusammenfassend die folgenden Eingaben und berechnen daraus die folgende Ausgabe.

Input:

  • bipartiter Graph GG = (PP ∪\cup SS, EE)
  • Kapazität csc_s für alle ss ∈\in S
  • vollständige Präferenzlisten der Schulen über die Schüler, wahrscheinlich mit Indifferenzen
  • verkürzte oder vollständige Präferenzlisten der Schüler über die Schulen ohne Indifferenzen

Output:

  • ein bb-Matching MM ⊆\subseteq EE

Beispiel:

Eigenschaften von School-Choice-Algorithmen

Für den Vergleich und die Analyse von School-Choice-Algorithmen ist eine Betrachtung der folgenden Eigenschaften besonders interessant.

Stabilität

School-Choice-Algorithmen können daraufhin untersucht werden, ob sie ein stabiles Matching garantieren, also in jedem Fall auf einem stabilen Matching terminieren.

Strategiesicherheit

Definition

Ein Algorithmus heißt strategiesicher, wenn für jedes Matching MM, auf dem der Algorithmus terminiert, das Folgende gilt: Für keinen Schüler pp ∈\in PP existiert eine von seiner wahren Präferenzliste ll abweichende Präferenzliste l′l', sodass für das unter Angabe von l′l' statt ll entstehende Matching M′M' gilt: M′M' (p)(p) ≻p\succ_p MM(p)(p).

Es könnte also kein Schüler einen Vorteil daraus ziehen, seine Präferenzen falsch darzustellen.

Pareto-Effizienz

Definition

Ein Matching MM heißt schülerseitig pareto-effizient, wenn kein anderes Matching M′M' existiert, sodass: M′(p)M'(p) ⪰p\succeq{_p} M(p)M(p) für jeden Schüler pp ∈\in PP und M′(p)M'(p) ≻p\succ{_p} M(p)M(p) für mindestens einen Schüler pp ∈\in PP gilt.

Ein Matching MM heißt schulseitig pareto-effizient, wenn kein anderes Matching M′M' existiert, sodass: M′(s)M'(s) ⪰s\succeq{_s} M(s)M(s) für jede Schule ss ∈\in SS und M′(s)M'(s) ≻s\succ{_s} M(s)M(s) für mindestens eine Schule ss ∈\in SS gilt.

Ein Matching MM heißt beidseitig pareto-effizient, wenn es sowohl schülerseitig als auch schulseitig pareto-effizient ist.

Dies bedeutet, dass es in einem pareto-effizienten Matching nicht möglich ist, einem Schüler eine bessere Wahl zuzuteilen ohne gleichzeitig einen anderen Schüler zu verschlechtern.

Ein School-Choice-Algorithmus heißt pareto-effizient, wenn er immer ein pareto-effizientes Matching auswählt.

Rangmaximalität

Definition

Ein Matching MM heißt schülerseitig rangmaximal, wenn es die Anzahl der erfüllten Wünsche an kk-ter Stelle der Präferenzlisten maximiert unter der Bedingung, dass auch alle ll-ten Wünsche maximiert sind, mit ll << kk und k=1,...,ik = 1,...,i, wobei ii die Länge der Präferenzliste der Schüler angibt.

Das Matching erfüllt also die maximale Anzahl an Erstwünschen und, davon abhängig, die maximale Anzahl an Zweitwünschen usw.

Ein School-Choice-Algorithmus heißt rangmaximal, wenn er immer in einem rangmaximalen Matching resultiert.

Kardinalitätsmaximalität

Definition

Ein Matching MM heißt kardinalitätsmaximal, wenn kein Matching M′M' existiert, sodass gilt: ∣M′∣>∣M∣|M'| > |M|. Es gibt also keine Möglichkeit eine vom Matching MM abweichende Kantenmenge zu finden, die mehr Schüler einer ihrer Wunschschulen zuordnet.