Parameterized Algorithmics for Voting Systems

• Applicant: Professor Dr. Rolf Niedermeier (†)
• Subject Area: Theoretical Computer Science
• Term: from 2009 to 2014
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 128081774

• Final Report Year: 2016

Final Report Abstract

Die Etablierung der Methoden der parametrisierten und multivariaten Komplexitätsanalyse als sehr wirkungsvolles Hilfsmittel zum tieferen Verständnis der algorithmischen Komplexität von typischer Weise NP-schweren Wahlproblemen wurde durch PAWS erfolgreich vorangetrieben. Etliche der in den beiden Anträgen beschriebenen Zielsetzungen wurden erreicht. Die Jenaer bzw. nunmehr Berliner Arbeitsgruppe hat auf Basis der PAWS-Arbeiten eine gute internationale Sichtbarkeit im Kontext des weiten Gebiets „Computational Social Choice“ erzielt. Dies ist auch durch eine Vielzahl internationaler Publikationen und entsprechende Zitationen unserer Papiere dokumentiert. Abschließend seien schlaglichtartig einige Errungenschaften im Rahmen von PAWS aufgezählt: • Im Rahmen des Projekts wurden zahlreiche parametrisierte Algorithmen entwickelt, welche helfen wichtige Probleme effizient zu lösen. Unsere frei verfügbare Software zur Gewinnerbestimmung beim Kemeny-Wahlsystem erlaubt z.B. in der realen Welt auftretende Instanzen mit mehr als 100 Kandidaten innerhalb weniger Sekunden zu lösen. • Für zahlreiche Fragestellungen (z.B. die Auslotung der Möglichkeiten der Manipulation oder Bestechung einer Wahl) konnte geklärt werden, ob diese auch dann berechnungsschwer sind, wenn bestimmte Parameterwerte, z.B. die Anzahl der Wähler oder Kandidaten, klein sind. Diese Ergebnisse helfen alternative Wahlsysteme und Entscheidungsprotokolle miteinander zu vergleichen. In Bezug auf Bestechung scheint zum Beispiel das Copeland-Wahlsystem klare Vorteile gegenüber dem Borda-System zu haben, da eine optimale Bestechungsstrategie hier viel schwerer zu finden ist. Die Forschungsgemeinschaft steuert hier auf ein immer klarer werdendes Bild zu, auch wenn noch zahlreiche offene Fragen bestehen und viele Modelle weiter- bzw. neu entwickelt werden. • Im Rahmen des Projekts wurden auch ganz neue Modelle wie „Dissolution“ (inspiriert durch Gerrymandering) oder „Majoritywise Accepted Ballot“ (inspiriert durch Koalitionsbildung oder Vertragsausarbeitung) entwickelt. • Von uns wurden neue theoretische Konzepte wie z.B. die Distanz zu single-peaked Stimmabgaben oder die Charakterisierung der Single-crossing-Eigenschaft eingeführt, und diese haben zahlreiche Folgearbeiten motiviert. Abschließend lässt sich festhalten, dass eine Vielzahl der in den Projektanträgen aufgezählten Fragestellungen im Rahmen des Projekts fruchtbar und erfolgreich bearbeitet wurden.

Publications

• Parameterized computational complexity of Dodgson and Young elections. Information and Computation, 208(2):165–177, 2010
  N. Betzler, J. Guo, und R. Niedermeier
  
• Average parameterization and partial kernelization for computing medians. Journal of Computer and System Sciences, 77(4):774–789, 2011
  N. Betzler, J. Guo, C. Komusiewicz, und R. Niedermeier
  
• Unweighted coalitional manipulation under the Borda rule is NP-hard. In Proceedings of 22nd International Joint Conference of Artificial Intelligence, pages 55–60, 2011
  N. Betzler, R. Niedermeier, und G. J. Woeginger
  
• Studies in computational aspects of voting - a parameterized complexity perspective. In The Multivariate Algorithmic Revolution and Beyond, volume 7370 of LNCS, pages 318–363. Springer, 2012. Festschrift dedicated to Prof. Michael R. Fellows on the occasion of his 60th birthday
  
  
• Theoretical and empirical evaluation of data reduction for exact Kemeny rank aggregation. Autonomous Agents and Multi-Agent Systems, 28(5):721–748, 2014
  Betzler, Nadja; Bredereck, Robert & Niedermeier, Rolf
  
• A multivariate complexity analysis of lobbying in multiple referenda. Journal of Artificial Intelligence Research, 50:409–446, 2014
  Bredereck, R.; Chen, J.; Hartung, S.; Kratsch, S.; Niedermeier, R.; Suchy, O. & Woeginger, G. J.
  
• Prices matter for the parameterized complexity of shift bribery. In Proceedings of the 28th Conference on Artificial Intelligence (AAAI ’14), pages 552–558, 2014
  R. Bredereck, J. Chen, A. Nichterlein, P. Faliszewski, und R. Niedermeier
  
• How to put through your agenda in collective binary decisions. ACM Transactions on Economics and Computation, 4(1):5:1–5:28, 2015
  Alon, Noga; Bredereck, Robert; Chen, Jiehua; Kratsch, Stefan; Niedermeier, Rolf & Woeginger, Gerhard J.