Parametrisierte Algorithmik für Wahlsysteme (PAWS)

• Antragsteller: Professor Dr. Rolf Niedermeier (†)
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung von 2009 bis 2014
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 128081774

Wahlsysteme nehmen in der modernen Informationsgesellschaft eine immer wichtigere Rolle ein. Sie sind nicht nur zentrales Werkzeug der Demokratie sondern spielen beispielsweise auch bei der Koordination in Multiagentensystemen eine tragende Rolle. Es gibt eine Vielzahl von Wahlsystemen – mit jeweiligen Vor- und Nachteilen – verknüpft mit einer Vielzahl von damit einhergehenden Fragestellungen. Angefangen bei der Auswertung einer Wahl reichen diese bis zu Fragen nach der Manipulierbarkeit, der Wahlkontrolle und vielem mehr. Ab etwa Ende der achtziger Jahre des letzten Jahrhunderts wurde damit begonnen, Fragen der Berechnungskomplexität bei Wahlsystemen intensiv zu studieren. Seither gibt es eine große Anzahl insbesondere auch komplexitätstheoretischer Ergebnisse, die zeigen, dass viele interessante Wahlfragen zu NP-schweren Problemen führen. Aus diesem Grund wurden diverse heuristische oder auch approximative Algorithmen in diesem Kontext entwickelt. Das Projekt PAWS setzt sich das Ziel, diese Untersuchungen systematisch zu erweitern, ganz wesentlich (aber nicht ausschließlich) geprägt durch eine parametrisierte Komplexitätsanalyse und der damit verbundenen Entwicklung exakter Algorithmen. Jena gehört zu den führenden Forschungsgruppen der parametrisierten Algorithmik. Auf dieser Basis sollen NP-schwere Auswertungsprobleme bei Wahlsystemen mit vollständiger und unvollständiger Information und darüberhinaus Szenarien mit erweiterten Wahlzielen betrachtet werden. Das Hauptziel von PAWS ist die Entwicklung und zum Teil auch die experimentelle Überprüfung neuer Algorithmen zur effizienten Analyse und Handhabung von Wahlsystemen.

• DFG-Verfahren: Sachbeihilfen