Muss man Vorlieben unterschiedlicher Menschen unter einen Hut bringen, sind die Methoden der "Computational Social Choice" (COMSOC) gefragt. Damit lassen sich etwa Lösungen ermitteln, die einer möglichst großen Anzahl an Teilnehmern, die eine Reihung ihrer Präferenzen angeben, möglichst gut passen.

Die Ermittlung von sogenannten "stabilen Zuweisungen", bei denen es also keine einander zugewiesenen Teilnehmer gibt, die lieber ein anderes Paar bilden wollen, wird in Dating-Apps oder in der Job- oder Studienplatzvermittlung genutzt.

Die Grundlagen dafür haben die US-Wissenschafter David Gale und Lloyd Shapley bereits in den 1960er-Jahren gelegt. Sie konnten mathematisch beweisen, dass stabile Zuweisungen in Matching-Märkten immer existieren, und zeigen, wie man diese berechnet.

Shapley erhielt 2012 gemeinsam mit dem ebenfalls in diesem Fachgebiet tätigen Alvin Roth den Ökonomie-Nobelpreis. Doch damit sind längst nicht alle mathematischen Fragen in diesem Bereich gelöst: Viele Probleme benötigen etwa einen sehr großen Lösungsraum.

Es gibt also nicht nur eine, sondern viele verschiedene stabile Zuweisungen, die vielleicht die Anforderungen, die man an das Match-Making stellt, unterschiedlich gut erfüllen.

Weiterentwicklung

Hier hakt Jiehua Chen mit ihrer Arbeit in der Algorithms and Complexity Group am Institute of Logic and Computation der TU Wien ein. Die in Shenzhen in China aufgewachsene Wissenschafterin studierte Informatik und promovierte an der TU Berlin. 2019 wechselte sie nach Wien. Im Rahmen eines vom Wissenschaftsfonds WWTF geförderten Projekts beschäftigt sie sich mit der Weiterentwicklung des COMSOC-Gebiets.

Dazu gehören zusätzliche Anforderungen, die man an die Lösung für eine stabile Zuweisung stellen kann und die die Berechnung sehr komplex machen. "Zum Beispiel kann es bei der Schulwahl oder Studienplatzvergabe Diversitätskriterien geben", veranschaulicht Chen die Problematik.

"In den USA wurden im Zuge der Bürgerrechtsbewegung der 1970er-Jahre unter dem Schlagwort ‚affirmative action‘ Maßnahmen entwickelt, die ein bestimmtes Maß an Vielfalt in Bezug auf Ethnizität, Religion, Geschlecht oder sozialer Herkunft in Schulen sicherstellen sollten. Etwa in Brooklyn in New York werden seit vergangenem Jahr solche Kriterien berücksichtigt." Chen arbeitet an einem Algorithmus, der eine derartige Zuordnung erledigen könnte.

Schulauswahl

Das Problem dabei: Eine solche stabile – und diverse – Zuweisung wäre wohl von keinem Computer in einer sinnvollen Rechenzeit bewältigbar.

"Um zu überprüfen, ob eine Zuweisung stabil ist und die Diversitätskriterien erfüllt, muss man nicht nur alle möglichen Schüler-Schule-Paare miteinbeziehen, sondern auch alle möglichen Kombinationen der zugewiesenen Schüler der Schule. Das macht die Sache sehr komplex", betont die Informatikerin.

Ihr Lösungsansatz liegt darin, gewisse individuelle Strukturen des Problems auszunützen, die die Berechnung einfacher machen. "Bei der Schulauswahl kann man beobachten, dass die Anzahl der Schulen und die Anzahl der Diversitätskriterien nicht ganz so groß sind wie die Anzahl der Schüler. Dadurch bleibt die Anzahl der unterschiedlichen und zulässigen Zuweisungen jeder Schule überschaubar", sagt Chen.

"Das hilft dabei, im Lösungsraum Strukturen zu finden, sodass man mithilfe eines sogenannten ganzzahligen linearen Ungleichungssystems mit beweisbar leistbarem Zeitaufwand herausfinden kann, ob eine diverse und stabile Zuweisung existiert und wie sie gegebenenfalls aussieht."

Daraus folgt: Mit den Mitteln der Mathematik könnte man der Segregation entgegenwirken und Diversität an den Schulen sicherstellen. (Alois Pumhösel, 17.4.2020)