Asymptotic Equivalence of Immediate and Deferred Acceptance

Stellen Sie sich vor, Sie sind der Bürgermeister einer geschäftigen Stadt, in der jedes Kind einen Platz in einer Schule benötigt, und es gibt genau so viele Plätze wie Schüler. Das Problem ist nicht nur, einen Platz zu finden, sondern den richtigen Platz. Jede Familie hat eine Liste von Schulen, die sie liebt – von „Meine Traumschule“ bis hin zu „Die, an die ich gehen würde, wenn ich müsste“. Die Stadt hat auch Regeln; vielleicht vergibt eine Schule Vorrang an Kinder, die in der Nähe wohnen oder Geschwister bereits dort haben. Die große Frage für die Verantwortlichen lautet: Wie bringen wir Kinder den Schulen zu, damit alle so zufrieden wie möglich sind?

Seit Jahrzehnten debattieren Experten über zwei Hauptmethoden, dies zu lösen. Die erste wird Deferred Acceptance (DA) genannt (aufgeschobene Annahme). Denken Sie an DA wie an einen langsamen, vorsichtigen Tanz. Schüler bewerben sich für ihre erste Wahl. Die Schulen halten sich die Favoriten fest, sagen aber nicht endgültig „Ja“, sondern nur „Vielleicht“. Wenn später ein besserer Schüler auftaucht, kann die Schule diesen gegen den aktuellen austauschen. Dieser Prozess wiederholt sich, bis alle untergebracht sind. Er ist berühmt dafür, fair und unmöglich zu manipulieren, kann aber etwas mühsam und ineffizient sein.

Die zweite Methode ist Immediate Acceptance (IA) (sofortige Annahme), auch bekannt als der „Boston-Mechanismus“. Dies ist eher wie ein hektisches Rennen. Schüler stellen sich in eine Schlange und bewerben sich für ihre erste Wahl. Die Schulen betrachten die Schlange, wählen ihre Favoriten baszną Priorität aus und sagen: „Du bist drin!“ Wenn man abgelehnt wird, rennt man sofort zu seiner zweiten Wahl. Der Haken dabei ist: Wenn man sich zu spät für seine Wunschschule bewirbt, könnte man seinen Platz an jemanden mit höherer Priorität verlieren, der früher angewandelt hat, selbst wenn man diese Schule wirklich sehr gerne besucht hätte. Aufgrund dessen wird IA oft als unfair oder leicht zu manipulieren kritisiert. Dennoch besitzt IA eine große Superkraft: Wenn alle die Wahrheit über ihre Wünsche sagen, garantiert IA ein Ergebnis, bei dem niemand glücklicher gemacht werden kann, ohne jemand anderen unglücklicher zu machen. Dies nennt man „Pareto-Effizienz“.

Hier stellt sich die Millionen-Dollar-Frage: Macht IAs Superkraft in der Realität wirklich einen großen Unterschied? Bringt IA Kinder tatsächlich zu Schulen, die sie viel lieber mögen, als die langsamere DA-Methode? Oder ist der Unterschied nur ein winziger, unsichtbarer Punkt? Dies ist das Rätsel, das Josué Ortega in seiner Arbeit untersucht.

---

Das große Schulrennen: Ein Märchen von zwei Mechanismen

Josué Ortega, ein Forscher der Queen's University Belfast, beschloss, diese Debatte durch ein massives Gedankenexperiment zu klären. Er betrachtete keine echten Städte mit ihrer chaotischen Geschichte und Politik. Stattdessen stellte er sich einen „zufälligen Markt“ vor – eine Welt, in der die Listen der Lieblingsschulen jedes Schülers völlig zufällig gezogen werden, so als würde man Namen aus einem Hut ziehen. In dieser Welt gibt es $n$ Schüler und $n$ Schulen.

Ortega wollte die „durchschnittliche Platzierung“ (average rank) messen. Stellen Sie sich vor, jeder Schüler erhielte eine Punktzahl basierend darauf, wie weit oben seine zugewiesene Schule auf seiner Liste steht. Wenn Sie Ihre Nummer 1 bekommen, ist Ihr Rang 1. Wenn Sie Ihre Nummer 100 bekommen, ist Ihr Rang 100. Das Ziel ist es, diese Zahl so niedrig wie möglich zu halten.

Schon lange kennen wir die Antwort für den langsamen, vorsichtigen Tanz (DA). Zurück in den 1970er Jahren fanden Mathematiker heraus, dass ein Schüler in einem zufälligen Markt im Durchschnitt eine Schule mit dem Rang etwa $\log n$ (Logarithmus von $n$) erhält. Wenn Sie 1.000 Schüler haben, ist der durchschnittliche Rang etwa 7. Wenn Sie 100.000 Schüler haben, ist er etwa 11. Er wächst, aber sehr langsam.

Aber was ist mit dem hektischen Rennen (IA)? Da IA anders funktioniert – wobei die Reihenfolge der Bewerbung entscheidend ist und Schüler nur deshalb abgelehnt werden können, weil sie „zu spät“ kamen – dachten Mathematiker, es könnte viel komplexer sein. Einige Informatiker hatten versucht, es zu lösen, konnten aber nur die Wahrscheinlichkeit für einen bestimmten Rang bestimmen, nicht aber den Durchschnittsrang für alle. Sie vermuteten, dass es ebenfalls logarithmisch sein könnte, aber niemand konnte es beweisen.

Das Geheimnis des „Coupon Collectors“

Ortegas Durchbruch war die Erkenntnis, dass beide Mechanismen, obwohl sie völlig unterschiedlich aussehen, insgeheim dasselbe Spiel spielen. Er nutzte ein klassisches Rätsel namens Coupon Collector Problem (das Problem des Sammlers), um es zu erklären.

Stellen Sie sich vor, Sie versuchen, eine vollständige Sammlung von $n$ verschiedenen Sammelkarten zu sammeln. Jedes Mal, wenn Sie eine Müslischachtel kaufen, erhalten Sie eine zufällige Karte. Wie viele Schachteln müssen Sie kaufen, um jede einzelne Karte mindestens einmal zu besitzen?
Die Antwort ist etwa $n \times \log n$. Sie verbringen viel Zeit mit dem Kauf von Schachteln, nur um die letzten wenigen seltenen Karten zu finden, die Ihnen noch fehlen.

Ortega zeigte, dass Deferred Acceptance exakt so ist. Schüler bewerben sich immer wieder für Schulen, bis jede Schule mindestens eine Bewerbung erhalten hat. Die Gesamtzahl der Bewerbungen aller Schüler ist in etwa dieselbe wie die Anzahl der Müslischachteln, die man kaufen müsste, um alle Sammelkarten zu sammeln. Da ein durchschnittlicher Schüler etwa $\log n$ Bewerbungen tätigt, ist auch sein endgültiger Schulrang etwa $\log n$.

Dann wandte Ortega seinen Blick auf die Immediate Acceptance. Auf den ersten Blick schien sie anders zu sein, da Schüler nicht einfach sofort weiter bewerben können; sie müssen warten, bis eine „Runde“ beendet ist, bevor sie es erneut versuchen können. Aber Ortega erkannte, dass es, wenn man den Prozess auf eine bestimmte Weise betrachtet, ebenfalls ein „Coupon Collector“ ist.

Er stellte sich eine leicht „amnesische“ Version des Spiels vor. Angenommen, ein Schüler wählt ständig zufällige Schulen aus, selbst wenn er diese Schule schon einmal probiert hat. Wenn er eine Schule wählt, die er bereits probiert hat, ignoriert er sie einfach (das ist ein „verschwendeter“ Versuch). Ortega bewies, dass selbst mit diesen verschwendeten Versuchen die Anzahl der tatsächlichen Bewerbungen, die nötig sind, um jede Schule zu füllen, immer noch etwa der gleichen Größenordnung wie das Coupon Collector Problem entspricht.

Die große Enthüllung

Hier kommt der entscheidende Punkt: Der Unterschied zwischen den beiden Methoden ist überraschend gering.

Ortega bewies mathematisch, dass, wenn der Markt riesig wird (wenn $n$ sehr groß wird), der durchschnittliche Rang der Schüler in dem Immediate Acceptance (IA)-System ebenfalls etwa $\log n$ beträgt.

Das bedeutet, dass IA, obwohl es „Pareto-effizient“ ist (was bedeutet, dass es theoretisch perfekt ist, wenn alle die Wahrheit sagen), den Schülern keinen massiven Vorteil in Bezug auf das Erreichen ihrer Wunschschulen gegenüber der langsameren DA-Methode bietet. Der „First-Order“-Verbesserungsvorteil – der große, spürbare Gewinn – existiert schlichtweg nicht.

Ortegas Arbeit schließt die Vorstellung explizit aus, dass IA ein Wundermittel ist, das die Ergebnisse der Schüler in großen, zufälligen Märkten drastisch verbessert. Während IA in spezifischen, winzigen Szenarien oder mit speziellen Prioritätsregeln etwas besser sein mag, zeigt die Arbeit, dass die beiden Mechanismen im allgemeinen Fall asymptotisch äquivalent sind. Beide führen dazu, dass Schüler in Schulen landen, die im Rang etwa logarithmisch zur Größe des Marktes stehen.

Warum das wichtig ist

Dieses Ergebnis ist für Fans des „Immediate Acceptance“-Systems ein wenig enttäuschend, aber für die Mathematik eine Erleichterung. Es zeigt uns, dass die „Pareto-Effizienz“ von IA ein wenig wie eine Fata Morgana ist, wenn es um das durchschnittliche Glück geht. Der Mechanismus, der oft als unfair und manipulierbar kritisiert wird, liefert tatsächlich kein signifikant besseres durchschnittliches Ergebnis als derjenung, der fair und schwer zu manipulieren ist.

Ortegas Arbeit dehnt dieses Ergebnis auch auf andere Variationen aus. Ob Schulen mehrere Plätze haben (Many-to-One Matching) oder ob Schüler erlauben sind, über volle Schulen hinwegzuspringen (eine Variation namens „IA mit Skips“), das Ergebnis bleibt gleich: Der durchschnittliche Rang bleibt bei etwa $\log n$.

Wenn Sie also das nächste Mal hören, dass jemand argumentiert, wir müssten den „Boston-Mechanismus“ verwenden, weil er effizienter ist, können Sie lächeln und sagen: „Nun, vielleicht ist er effizient, aber er führt die Kinder im Durchschnitt nicht wirklich in bessere Schulen als die andere Methode.“ Im großen Rennen der Schulwahl überqueren beide Läufer die Ziellinie fast zur exakt gleichen Zeit.