Algorithmen für Faire Allokationen (AFFA)

• Antragsteller: Professor Dr. Robert Bredereck
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung von 2015 bis 2023
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 284041127

Der Fokus von AFFA liegt auf der Untersuchung der algorithmischen Komplexität wichtiger Berechnungsprobleme im Kontext fairer Allokationen.Die zweite Projektphase besteht wiederum aus drei Hauptteilen: Allokation exklusiver Ressourcen, Allokation von Repräsentanten und Allokation geteilter Ressourcen. Wir werden sowohl theoretische als auch praktische Aspekte bei der Algorithmenentwicklung miteinbeziehen.Auf der theoretischen Seite zielen wir auf die Erlangung allgemeinerer und realistischerer Modelle für verschiedene Allokationsszenarien. Dabei werden wir zum einen als Graphen repräsentierte soziale Netzwerke miteinbeziehen, wodurch bislang studierte Modelle verallgemeinert werden. Folglich werden wir uns mit der Anpassung und Modifikation bestehender Fairnesskonzepte etc. beschäftigen.Zum anderen werden wir neue Modelle hinsichtlich temporaler Aspekte entwickeln. Insbesondere planen wir dabei die Untersuchung der Allokation von Repräsentanten und werden dabei „inkrementelle“ Szenarien studieren -- die Lösung basiert hierbei auf inkrementellen, üblicher Weise kleinen Änderungen. Für diese Untersuchungsgebiete planen wir die Durchführung einer feingranularen Komplexitätsanalyse. Zweifelsohne werden wir auf einige berechnungsschwere Probleme stoßen, für welche wir Ansätze aus der multivariaten Algorithmik und der Approximationsalgorithmik sowie Lösungswerkszeuge (auch in Kombination) u.a. aus der mathematischen Programmierung verwenden wollen um die Worst-Case-Berechnungsschwere zu umschiffen.Auf der praktischen Seite wollen wir die entwickelten Algorithmen implementieren und in Experimenten testen. Dabei wollen wir nicht nur das Verständnis von diversen Allokationsmechanismen vertiefen sondern auch praktisch einsetzbare Software-Werkzeuge für weiterführende Untersuchungen liefern. Die von uns entwickelte Software wird frei verfügbar gemacht. Zusätzlich wollen wir ein vertieftes Verständnis des Themas der Allokation von Repräsentanten entwickeln indem wir speziell zugeschnittene Experimente unter Miteinbeziehung temporaler Aspekte durchführen. Die Ergebnisse dieser Untersuchungen benutzend planen wir zudem die Visualisierung der entsprechenden Dynamik. Dies wird uns neue Einsichten in das dynamische Verhalten von Multiwinner-Wahlmechanismen unter zeitabhängigen Gesichtspunkten ermöglichen.

• DFG-Verfahren: Sachbeihilfen
• Ehemaliger Antragsteller: Professor Dr. Rolf Niedermeier, bis 6/2022 (†)