Algorithmische Entscheidungstheorie: Komplexitätstheorie für sichere kollektive Entscheidungsprozesse

• Antragsteller: Professor Dr. Gábor Erdelyi
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung von 2013 bis 2015
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 248483686

Computational Social Choice ist ein junges, interdisziplinäres Forschungsgebiet an der Grenze zwischen Informatik und Social-Choice-Theorie. Sie vereint Wissenschaftler aus vielen verschiedenen Disziplinen mit dem Ziel, Entscheidungsverfahren bei großen Datenmengen in kombinatorischen und probabilistischen Umgebungen zu verbessern. Der Prozess, in dem unabhängige Agenten in der Anwesenheit von großen Datensätzen und unvollständigen Informationen kollektive Entscheidungen treffen, kann unter Umständen sehr komplex sein. In vielen Bereichen des Alltags, wie zum Beispiel in der Politik, in Bildverarbeitung, in kombinatorischen Auktionen, in Empfehlungssystemen, in sozialen Netzwerken oder in Multi-Agenten-Systemen ist es aber erforderlich, dass diese Entscheidungsprozesse schnellstmöglich durchgeführt werden.Gegenstand dieses Projektes ist die komplexitätstheoretische und empirische Analyse von verschiedenen Entscheidungsprozessen. Wir werden systematisch manipulative Aktionen, wie zum Beispiel Bestechung, Manipulation (in dem auf dem Fachgebiet bekannten Sinne des Wortes) und Kontrolle, in verschiedenen Wahlsystemen und in der gemeinsamen Urteilsfindung (engl. judgment aggregation) untersuchen. Unser Hauptziel wird es sein die rein theoretischen Annahmen von denen in Computational Social Choice ausgegangen wird durch solche zu ersetzen, die in der Praxis durchaus relevant sind. Wir werden uns in unserer Forschung auf die folgenden Schwerpunkte konzentrieren:1. Bestechung, Wahlkontrolle und Manipulation in Wahlen unter bestimmten Einschränkungen (wie zum Beispiel in probabilistischen Situationen, in sogenannten beinahe single-peaked Wahlen oder in k-peaked Wahlen),2. parametrisierte und average-case Komplexität von Entscheidungsproblemen,3. Komplexitätsanalyse von judgment aggregation Problemen und4. empirische Analyse der in den vorigen Projektteilen gewonnenen Ergebnissen und Methoden.

• DFG-Verfahren: Sachbeihilfen
• Beteiligte Person: Professor Dr. Jörg-Matthias Rothe