Boston-Algorithmus

Der Boston-Algorithmus ist ein weit verbreiteter School-Choice-Algorithmus Für seine Verwendung spricht, dass er die Prioritäten der Schüler stark berücksichtigt und eine maximale Anzahl an Schülern ihrer ersten Wunschschule zuordnet. Er ist jedoch nicht unumstritten, weil er Schülern Anreize bietet, ihre Präferenzen nicht wahrheitsgemäß anzugeben. Aus diesem Grund wird der Algorithmus in der namensgebenden Stadt seit dem Jahr 2005 nicht mehr verwendet.

Ablauf des Algorithmus

Der folgende Pseudocode beschreibt, wie der Boston-Algorithmus bei der Verteilung von Schülern auf Schulen vorgeht.

Eingabe:

Menge der Schulen $S$
Menge der Schüler $P$
Kapazität $c_s$ für alle $s$ $\in$ $S$
Präferenzliste für alle $s$ $\in$ $S$ über $P$
Präferenzliste für alle $p$ $\in$ $P$ über Teilmenge von $S$

Ausgabe:

b-Matching $M$

$M \leftarrow \emptyset$
$\mathbf{for}~k = 1,..., n~~\mathbf{do}~$
    
$\mathbf{for~each}~{s \in S}~~\mathbf{do}~$
              
$O \leftarrow (o_1, o_2,..., o_l) $: Sortiere alle Schüler, die $s$ an $k$-ter Stelle ihrer Präferenzliste angegeben haben, absteigend nach der Präferenzliste von $s$.
       
$\mathbf{for}~i = 1,...,l~~\mathbf{do}$
          
$\mathbf{if}~c_s \neq 0~$
              
$M \leftarrow M \cup \{\{o_i,~s\}\}$
              
$c_s = c_s - 1$
$\mathbf{return}$ $M$

In Worten: Jeder Schüler kann $n$ Wunschschulen angeben, die er nach seiner Präferenz absteigend ordnet. Beginnend mit der höchsten Präferenz $k = 1$ , führe für jedes $k$ $\leq$ $n$ folgenden Schritt aus: Betrachte für jede Schule nur jene noch nicht zugeordneten Schüler, welche die Schule als $k$ -te Wahl angegeben haben. Ordne diese Schüler nach den Präferenzen der betrachteten Schule. Bei Indifferenzen entscheide dabei zufällig. Nimm in dieser Reihenfolge solange Schüler auf, bis entweder die Kapazität der Schule erschöpft oder die Liste der Schüler abgearbeitet ist.

Eigenschaften des Algorithmus

Stabilität

Satz

Der Boston-Algorithmus garantiert nicht, dass ein stabiles Matching gefunden wird.

Beweis

Strategiesicherheit

Satz

Der Boston-Algorithmus ist nicht strategiesicher.

Beweis

Betrachte das Folgende mit dem Boston-Algorithmus gefundene Matching (Finden des Matchings siehe Beweis zur Stabilität). Der Schüler $p_3$ erhält hier nur eine Zulassung für seine Drittwahl.

Vergleiche das folgende Matching, welches entstünde, wenn Schüler $p_3$ über seine Präferenzen lügen und $s_1$ an die erste Stelle seiner Präferenzliste setzen würde:

Der Schüler $p_3$ würde nun an Schule $s_1$ angenommen werden, weil diese $p_3$ vor dem einzigen anderen Schüler präferiert, der sie als Erstwahl angegeben hat, $p_1$ . Somit würde $p_3$ an seiner tatsächlichen Zweitwahl $s_1$ angenommen und würde damit seine Situation verbessern können. Demnach ist der Boston-Algorithmus nicht strategiesicher. $\Box$

Unter dem Boston-Algorithmus verliert ein Schüler seine hohe Priorität bei einer Schule an alle Schüler, die diese Schule mit einem höheren Prioritätsranking versehen haben. Es existiert also ein großer Anreiz für Schüler, ihre Erstwahl nicht zu verschwenden und Schulen zu präferieren, bei denen sie hohe Priorität besitzen.^abd2003 So sind unter dem Boston-Algorithmus all jene Schüler benachteiligt, die keine strategischen Überlegungen anstellen. Mit Verweis auf diese mangelnde Fairness wurde der Boston-Algorithmus in Großbritannien gesetzlich verboten.^koj2014

Die Manipulierbarkeit eines Algorithmus führt vor allem dann zu Ungerechtigkeit, wenn sich herausstellt, dass es in der Praxis sowohl Akteure gibt, die ihre Präferenzen wahrheitsgemäß angeben als auch solche, die dies nicht tun. Für den Boston-Algorithmus wurde dies in einer Studie von Abdulkadiroglu et al. untersucht. Die Analyse empirischer Daten der Stadt Boston aus dem Jahr 2001 ergab, dass sowohl strategisches als auch nicht-strategisches Verhalten von Familien unter dem Boston-Algorithmus existiert.^abd2006 Da die wahren Präferenzen der Schüler aus experimentellen Daten nicht erkannt werden können, bedient sich die Studie eines strategischen Fehlers, um zu zeigen, dass nicht-strategisches Verhalten existiert: Im Boston-Algorithmus ist es sehr ungünstig, zwei hoch-nachgefragte Schulen als Erst- und Zweitwahl zu nennen. Von den Datensätzen wiesen jedoch 19% diesen strategischen Fehler auf. Von diesen Schülern wurden 27% nicht zugeordnet. Um zu zeigen, dass strategisches Verhalten existiert, wurden "Ausreißer-Schulen" fokussiert: Bei sehr hoch-nachgefragten Schulen ist zu beobachten, dass diese von vielen Schülern als Erstwahl genannt werden, aber nur selten als Zweitwahl. Es konnte gezeigt werden, dass eine statistisch relevante Beziehung zwischen dem Ausmaß dieser Präferenzdiskontinuität und der Beliebtheit der Schule existiert.^abd2006

Bevorzugung höherer Rankings

Satz

Der Boston-Algorithmus bevorzugt höhere Rankings.

Beweis

Im Boston-Algorithmus werden Schüler nur dann von einer Schule abgewiesen, wenn die Kapazität der Schule erschöpft ist. Wenn die Kapazität im Schritt der Ablehnung des Schülers erschöpft ist, bedeutet dies, dass die Schule in vorherigen Schritten eine entsprechende Zahl an Schülern aufgenommen hat oder die Kapazität im aktuellen Schritt ausgeschöpft wird. In beiden Fällen gilt also für alle angenommenen Schüler, dass die Schule mindestens so hoch gerankt wurde wie vom abgelehnten Schüler. $\Box$

Insbesondere impliziert diese Aussage, dass der Boston-Algorithmus die Anzahl der erfüllten Erstwünsche maximiert.

Pareto-Effizienz

Satz

Ein Algorithmus, der höhere Rankings bevorzugt, ist schülerseitig pareto-effizient.

Beweis

Beweis:^koj2014 Sei $M$ ein Matching, das höhere Rankings bevorzugt. Wir nehmen an, dass $M$ nicht pareto-effizient ist und führen einen Widerspruch herbei. Da $M$ nicht pareto-effizient ist, existiert ein Matching $M'$ , bei dem sich kein Schüler gegenüber seiner Zuordnung in $M$ verschlechtert, aber mindestens ein Schüler verbessert. Aufgrund der Bevorzugung höherer Rankings kann es dabei keinen Schüler geben, der sich dadurch verbessern kann, dass er in $M'$ einen in $M$ unbesetzten Schulplatz erhält. Demnach existiert eine Abfolge von Schülern $p_1, ..., p_n$ mit $p_i$ $\in$ $P$ , sodass sich alle Schüler in dieser Menge verbessern können, indem sie untereinander ihre Plätze tauschen. Es gilt also, dass jeder Schüler $p_k$ den Matchingpartner $M$ ( $p_{k+1}$ ) seines Nachfolgers $p_{k+1}$ besser gerankt hat als seinen eigenen Matchingpartner (sonst würde er nicht tauschen wollen). Dies notieren wir folgendermaßen:

$\text{R}_{p_k}(M(p_{k+1})) < \text{R}_{p_k}(M(p_{k}))$ .

Der Nachfolger von $p_n$ ist dabei $p_1$ . Da $M$ höhere Rankings bevorzugt, gilt außerdem, dass jeder Schüler $p_{k+1}$ seinen Matchingpartner mindestens genauso gut gerankt hat wie sein Vorgänger $p_{k}$ . Ansonsten wäre der Vorgänger angenommen worden, da dieser sich auch an der Schule beworben hat.

$\text{R}_{p_{k+1}}(M(p_{k+1})) \leq \text{R}_{p_k}(M(p_{k+1}))$

Durch Zusammensetzen der beiden Gleichungen ergibt sich der folgende Widerspruch:

$~~~~\text{R}_{p_{1}}(M(p_{1}))$

$\leq \text{R}_{p_n}(M(p_{1})) < \text{R}_{p_n}(M(p_{n}))$

$\leq \text{R}_{p_n-1}(M(p_{n})) < \text{R}_{p_n-1}(M(p_{n-1}))$

$...$

$\leq \text{R}_{p_1}(M(p_{2})) < \text{R}_{p_1}(M(p_{1}))$ . $\Box$

Es wurde somit gezeigt, dass der Boston-Algorithmus pareto-effizient ist. Allerdings ist Pareto-Effizienz per Definition davon abhängig, dass die Schüler ihre Präferenzen wahrheitsgemäß angeben. Da es aber, wie oben gesehen, wahrscheinlich ist, dass viele Schüler ihre Präferenzen manipulieren, ist es unwahrscheinlich, dass der Boston-Algorithmus in der Realität ein pareto-effizientes Matching findet.^abd2003

Rangmaximalität

Satz

Der Boston-Algorithmus garantiert keine schülerseitige Rangmaximalität, wenn Indifferenzen zwischen Schülern auf der Seite der Schulen bestehen.

Beweis

Satz

Der Boston-Algorithmus garantiert schülerseitige Rangmaximalität, wenn die Präferenzlisten der Schulen keine Indifferenzen beinhalten.

Beweisidee

In der Realität werden die Präferenzlisten der Schulen immer Indifferenzen beinhalten, auf Grund der generell hohen Zahl an Schülern im Verhältnis zur geringen Zahl an Prioritätenkategorien der Schulen (z.B. Notendurchschnitt, Geschwisterkinder auf der Schule).

Kardinalitätsmaximalität

Satz

Bei verkürzten Präferenzlisten auf Seiten der Schüler garantiert der Boston-Algorithmus nicht, dass ein kardinalitätsmaximales Matching gefunden wird.

Beweis

Gegeben sei die folgende Probleminstanz mit verkürzten Präferenzlisten der Schüler. Alle Schulen besitzen die Kapazität 1. Betrachte das mit dem Boston-Algorithmus gefundene Matching $M$ .

Der Boston-Algorithmus hat ein Matching $M$ der Kardinalität 2 gefunden, es gibt aber ein Matching $M'$ der Kardinalität 3 für diese Probleminstanz: $M'$ = $M$ $\cup$ $\{\{p_2, s_3\}, \{p_3, s_2\}\}$ $\setminus$ $\{\{p_2, s_2\}\}$ . $\Box$

Verständnisfragen

[ABD2003]: Abdulkadiroglu, Atila und Tayfun Sönmez: School Choice: A Mechanism Design Approach. American Economic Review, 93: 729-747, 2003.↩
[KOJ2014]: Kojima, Fuhito und M. Utku Ünver: The Boston school-choice mechanism: an axiomatic approach. Economic Theory, 55(3): 515-544, 2014.↩
[ABD2006]: Abdulkadiroglu, Atila, Parag Pathak, Alvin Roth und Tayfun Sönmez: Changing the Boston School Choice Mechanism: Strategy-proofness as Equal Access. NBER working paper series, Band 11965, 2006.↩

Boston-Algorithmus

Ablauf des Algorithmus

Eigenschaften des Algorithmus

Stabilität

Strategiesicherheit

Bevorzugung höherer Rankings

Pareto-Effizienz

Rangmaximalität

Kardinalitätsmaximalität

Frage 1:

Frage 2: