Einleitung

Das Projekt Match-UP ist ein einsemestriges Bachelor- und Masterprojekt der Arbeitsgruppe CSLog im Fachbereich 3 der Universität Bremen. Im Rahmen des Projektes wurden verschiedene Matching-Probleme praktisch wie auch theoretisch behandelt. Den Fokus legten wir dabei auf das Problem der Schulplatzvergabe für weiterführende Schulen im Land Bremen. Im Projekt implementierten wir bekannte Algorithmen und entwickelten auch eigene, um diese anschließend zu vergleichen. Ebenfalls schrieben wir eine Webseite, welche die Grundlagen der Matching-Theorie vermitteln soll und weiterführend ausgewählte Matching-Algorithmen beschreibt.

Schulwahl in Bremen

Am Ende der Grundschulzeit wählen Bremer Schüler*innen gemeinsam mit ihren Eltern bis zu drei Schulen aus, mit absteigender Priorität, die sie gerne besuchen möchten. Andere Schulen Auch die Schulen bilden Präferenzlisten über die Schüler*innen und teilen sie in Gruppen ein: Die Gymnasien bevorzugen die Schüler*innen mit überdurchschnittlich guten Noten, die Oberschulen hingegen jene, welche eine nahegelegene Grundschule besucht haben.

Die Schulen bevorzugen zwar bestimmte Schüler*innen, für sie ist aber grundsätzlich jede/r akzeptabel, sie haben vollständige Präferenzlisten. Die Präferenzliste der Schüler*innen hingegen ist durch die Art des Verfahrens auf 3 Schulen verkürzt. Das Problem der Schulplatzvergabe wird außerdem dadurch kompliziert, dass es häufig auftritt, dass Schüler*innen in den Augen einer Schule gleich gut sind, weil sie die Kriterien der Schule gleichermaßen erfüllen.

Stellt man besondere Anforderungen an das resultierende Matching, z. B. ein kardinalitätsmaximales, schwach stabiles Matching zu finden, gehört das Problem der Schulplatzvergabe zur Klasse der NP-schweren Probleme.

Derzeit wird in Bremen der Boston-Mechanismus verwendet, ein Algorithmus welcher dafür bekannt ist, die Anzahl der erfüllten Erstwünsche zu maximieren, jedoch vergleichsweise viele Schüler*innen ohne Wunschschule zurücklässt. So erging es Max im gezeigten Video oder 151 Schüler*innen im Jahr 2019. Darüber berichtete auch der Weser Kurier.

Wir entwickelten und implementierten diverse Algorithmen, welche verschiedenste Matchings auf generierten Testwahlen produzieren und bewerteten diese anschließend. Dazu mussten wir jedoch auch erst einmal Kriterien aussuchen und ermitteln, die wir hierzu nutzen wollen, zum Beispiel:

  • Die Fairness der Lösung, also ob oder wie häufig es zum Beispiel Situationen gibt, bei der Schüler*innen eine nicht zugewiesene Schule bevorzugt, und auch anders herum diese Schule die Schüler*innen bevorzugt hätte ("Stabilität").
  • Die Anzahl der erfüllten Erst- und Zweitwünsche.
  • Die Möglichkeit bestimmter Platztäusche, sodass alle Beteiligten davon profitieren ("Pareto-Effizienz").
  • Die Möglichkeit der Manipulation des Verfahrens durch Verfälschen der eigenen Wahlen ("Strategiesicherheit").
Exemplarischer Vergleich vom Boston-Mechanismus und Gale-Shapley-Algorithmus

Die Grafik zeigt einen Vergleich vom Boston-Mechanismus und dem Gale-Shapley-Algorithmus. In blau wird das Ergebnis einer Zielfunktion gezeigt, welche wir maximieren möchten. Die roten und gelben Säulen zeigen jeweils Situationen, welche zu Konflikten aufgrund der Fairness führen könnten, daher galt es diese Säulen möglichst klein zu halten.

Matching-Theorie

Wir befassten uns zusätzlich zum praktischen Teil mit diversen Theoriefragen und lasen einige bestehende Arbeiten zu diesem Gebiet. Unter anderem wollten wir so erfahren:

  • Welche Algorithmen haben Andere bereits entwickelt? Was für Eigenschaften haben diese Algorithmen?
  • Wie viel weiß man bereits zur Komplexität einiger Probleme in der Matching-Theorie? Lassen sich diese Erkenntnisse auch auf die Schulplatzvergabe in Bremen übertragen?
  • Wie kann man trotz hoher Komplexität einiger Probleme, z. B. mit Approximationsalgorithmen, gute, wenn auch nicht zwingend optimale, Ergebnisse erzielen?
  • Wie bewerten Andere ihre Algorithmen?

Matching Webseite

Matchings treten in vielen Situationen unseres Alltags auf: Bei der Zuordnung von Studierenden zu Bachelor- und Masterprojekten, Schüler*innen zu weiterführenden Schulen, oder Werbekunden zu freien Werbeplätzen, um mal ein paar Beispiele zu nennen. Deswegen denken wir, dass Kenntnisse über diesen Themenbereich für viele Informatiker wichtig sein können.

Um Interessierten einen ersten Einblick in die Welt der Matchings zu ermöglichen, schrieben wir daher eine Webseite, über die wir einen Einstieg in die Thematik "Graphen- und Matchingtheorie" vermitteln möchten. Während des Erstellens legten wir viel Wert auf Interaktionsmöglichkeiten und einen nachvollziehbaren Aufbau der Seite. Wir beschlossen mit den Grundlagen einzusteigen und darauf aufbauend ein paar wichtige Eigenschaften zu erklären und zu beweisen. Im letzten Kapitel folgt eine genaue Beschreibung von ausgewählten Algorithmen, mit denen die Schulzuweisung durchgeführt werden könnte. Für Interaktivität sorgen kleine Aufgaben für die Leser.

Orga

Es wurde darauf verzichtet, feste Teams einzurichten, damit alle Bereiche des Projektes von den Ideen aller Teilnehmer profitieren konnten. Zwei Teilnehmer konzentrierten sich jedoch verstärkt auf das Erstellen der Website und das stetige Hinzufügen von Features, die für eine anschaulichere Gestaltung des Inhalts sorgten. Innerhalb der Gruppe hatten zwei Projektteilnehmer dazu die Rolle des Projektmanagers übernommen, um den Fortschritt des gesamten Projektes über alle Aufgabenbereiche hinaus zu gewährleisten.

Aufgrund der COVID-19 Pandemie fand ein Großteil des Projektes remote statt.