Komplexität von Wahlproblemen: Gewinner-Bestimmung, Manipulation und Wahlkontrolle

• Antragsteller: Professor Dr. Jörg-Matthias Rothe
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung von 2007 bis 2010
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 50868308

Wahlsysteme sind Regeln zur Auswahl der Sieger von Abstimmungen aus einer Gruppe von Kandidaten (oder Alternativen). Sie spielen nicht nur in der Politik und Social-Choice-Theorie, sondern auch in der Informatik eine wichtige Rolle, u.a. in der Künstlichen Intelligenz (wo Präferenzaggregation durch Wahlen für Multi-Agenten-Systeme relevant ist), in der Komplexitätstheorie und der Algorithmik. Praktische Anwendungen der Theorie des Wählens in der Informatik betreffen z.B. elektronische Auktionen, E-Kommerz, Recommender-Systeme und die Verminderung von Spam in der Websuche. Umgekehrt sind Methoden der Informatik nützlich für die Social-Choice-Theorie, etwa bei empirischen Untersuchungen oder beim Entwurf von Algorithmen für die gerechte Aufteilung von Parlamentssitzen. Ziel dieses Projekts ist eine systematische Untersuchung der komplexitätstheoretischen und algorithmischen Aspekte vonWahlproblemen und anderen Problemen der Social-Choice-Theorie und ihrer praktischen Anwendungen in der Informatik. Insbesondere sollen die Gewinner-, Kontroll-, Manipulations- und Bestechungsprobleme für Wahlsysteme studiert werden. Die Schwerpunkte liegen dabei auf (a) der Anwendung des average-case Komplexitätsmodells neben dem worst-case Modell, (b) der Untersuchung von kürzlich eingeführten Methoden zur Hybridisierung von Wahlsystemen, wobei das neu entstehende hybride Wahlsystem die Vorteile der konstituierenden Wahlsysteme erbt, (c) der Approximierbarkeit und parametrisierten Komplexität von Wahlproblemen, (d) dem Beweis von Dichotomiesätzen für Familien von Wahlsystemen und (e) der empirischen Analyse praktisch benutzter Wahlverfahren (z.B. f¨ur Hochschulrankings).

• DFG-Verfahren: Sachbeihilfen