Structural and Algorithmic Aspects of Preference-based Problems in Social Choice

Im Fachgebiet „Computational Social Choice“ geht es um Entscheidungsprozesse: Wenn viele Personen gewisse Vorlieben haben, wie wählt man dann eine Lösung aus, die möglichst vielen Leuten möglichst gut passt? Wie verteilt man etwa Studierende gemäß ihrer Wünsche auf verschiedene Colleges? Oder wie kann ein Film-Streaming-Dienst passende Filmvorschläge aussuchen, basierend auf den Filmen, die eine bestimmte Person bisher gesehen hat? Das Problem bei diesen Aufgaben ist, dass es im schlimmsten Fall zeitlich nicht möglich ist, alle Varianten durchzuprobieren. Die Anzahl der Varianten steigt mit der Zahl der Personen (oder der vorzuschlagenden Filme) so rasch an, dass die Rechenzeit ins Astronomische steigen würde. Jiehua Chen entwickelt Strategien, dieses Problem zu lösen. Oft ist es gar nicht nötig, alle mathematisch möglichen Varianten auszuprobieren, weil man viele von vornherein ausschließen kann. Echte, realistische Daten haben eine gewisse Struktur – und wenn man Möglichkeiten findet, diese Struktur geschickt zu nutzen, kann man die Rechenzeit drastisch verkürzen. So lassen sich in überschaubarer Zeit sogar Aufgaben lösen, die in die Klasse der schwierigen „NP-Probleme“ fallen.