Algorithmische Grundlagen der Social-Choice-Theorie

• Antragsteller: Professor Dr. Felix Brandt; Professor Dr. Jörg-Matthias Rothe
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung von 2011 bis 2016
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 209922626

Dieser Antrag behandelt zwei wichtige Teilbereiche der Computational-Social-Choice-Theorie: Turnierlösungen und Präferenzbündelung im Kontext partieller Information. Im ersten Teil untersuchen wir die Anwendbarkeit von Turnierlösungen auf verschiedenartige Matching-Probleme, die momentan ein wieder erstarktes Interesse in der Informatik erfahren. Diese Verbindung führt zu einer Vielzahl von herausfordernden algorithmischen Problemen sowie konzeptueller Fragestellungen wie beispielsweise der Erweiterung von Turnierlösungen auf Dominanzrelationen, die nicht notwendigerweise vollständig und asymmetrisch sind. Wir haben außerdem vor, Algorithmen zur Berechnung von Turnierlösungen in einem experimentellen Rahmen mit Hilfe realistischer Verteilungen von Turnieren zu evaluieren. Ein derartiger Ansatz ist auch zur Beantwortung anderer Fragen, die sich einer analytischen Untersuchung entziehen, sehr hilfreich. Dies gilt beispielsweise für eine bekannte Vermutung von Schwartz. Im zweiten Teil untersuchen wir Präferenzbündelung im Kontext partieller Information. In einem formalen Modell zur Beschreibung „abgeschnittener“ Wahlstimmen sollen die algorithmischen und komplexitätstheoretischen Eigenschaften vieler Varianten des Possible-Winner-Problems bestimmt werden. Außerdem werden Axiome der Sozialwahltheorie, die gut im Modell „abgeschnittener“ Wahlstimmen ausgedrückt werden können, hinsichtlich ihrer effizienten Lösbarkeit untersucht. Weiterhin interpretieren wir ein „erwünschteres“ Ergebnis in Manipulations-, Wahlkontroll-, Bestechungs- und Lobbying-Problemen allgemeiner als nur durch „Gewinnen statt Verlieren“ und untersuchen diese Probleme algorithmisch. Schließlich wollen wir Methoden zur Kalibrierung der Punktwerte von voreingenommenen Gutachtern in einem Peer-Review-Prozess entwickeln und empirisch sowohl mit echten Daten als auch in Simulationen testen.

• DFG-Verfahren: Sachbeihilfen