Computational Foundations of Social Choice

• Applicants: Professor Dr. Felix Brandt; Professor Dr. Jörg-Matthias Rothe
• Subject Area: Theoretical Computer Science
• Term: from 2011 to 2016
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 209922626

• Final Report Year: 2018

Final Report Abstract

Inhaltlich sind die wichtigsten Ergebnisse („highlights“) dieses Projekts die folgenden: Wir initiierten eine systematische Untersuchung zur Komplexität von Problemen in Wahlen mit top-, bottom- und doubly-truncated ballots sowie von Possible-Winner-Varianten. - Wir zeigten, dass unter allen bisher untersuchten natürlichen Wahlsystemen mit effizienter Gewinnerbestimmung fallback voting die umfassendste Kontrollresistenz aufweist. Auch die Komplexität von Manipulation, Bestechung und Kontrolle in Bucklin-Wahlen wurde sehr umfassend geklärt. - Wir charakterisierten Strategiesicherheit in scoring allocation correspondences durch eine einfache Bedingung und initiierten eine umfassende Untersuchung weiterer ihrer Eigenschaften. - Wir führten den Begriff der Online-Manipulation und der Online-Kontrolle für sequenzielle Wahlen ein und zeigten die PSPACE-Vollständigkeit der entsprechenden Probleme im allgemeinen Fall sowie weitere Komplexitätsresultate für spezifische natürliche Wahlsysteme. - Wir bestimmten die Komplexität von Manipulation, Bestechung und Kontrolle für die Klasse der uniform premise-based quota rules in der judgment aggregation für verschiedene Präferenztypen. - Wir vervollständigten die Resultate zur Kontrollkomplexität für Borda- und Veto-Wahlen. - Wir schlugen statistische Methoden zur Kalibrierung von review scores vor, um subjektive Bewertungen wissenschaftlicher Arbeiten fairer und besser vergleichbar zu machen.

Publications

• Campaigns for Lazy Voters: Truncated Ballots, Tagungsband 11th International Conference on Autonomous Agents and Multiagent Systems (AAMAS’12), IFAAMAS, pp. 577–584. Valencia, Spain, Juni 2012
  D. Baumeister, P. Faliszewski, J. Lang und J. Rothe
  
• Theory of Computing Systems, vol. 53, no. 3, pp. 467–502, Oktober 2013
  Baumeister, Dorothea; Brandt, Felix; Fischer, Felix; Hoffmann, Jan & Rothe, Jörg
  
• Complexity of Manipulation, Bribery, and Campaign Management in Bucklin and Fallback Voting, Journal of Autonomous Agents and Multi-Agent Systems, vol. 29, no. 6, pp. 1091–1124, November 2015
  Faliszewski, Piotr; Reisch, Yannick; Rothe, Jörg & Schend, Lena
  
• Journal of Computer and System Sciences, vol. 80, no. 4, pp. 697–710, Juni 2014
  Hemaspaandra, Edith; Hemaspaandra, Lane A. & Rothe, Jörg
  
• A Statistical Approach to Calibrating the Scores of Biased Reviewers of Scientific Papers, Metrika, vol. 79, no. 1, pp. 37–57, Januar 2016
  Kuhlisch, Wiltrud; Roos, Magnus; Rothe, Jörg; Rudolph, Joachim; Scheuermann, Björn & Stoyan, Dietrich
  
• Complexity of Manipulation and Bribery in Judgment Aggregation for Uniform Premise-Based Quota Rules, Mathematical Social Sciences, vol. 76, pp. 19–30, Juli 2015
  Baumeister, Dorothea; Erdélyi, Gábor; Erdélyi, Olivia J. & Rothe, Jörg
  
• Control Complexity in Bucklin and Fallback Voting: A Theoretical Analysis, Journal of Computer and System Sciences, vol. 81, no. 4, pp. 632–660, Juni 2015
  Erdélyi, Gábor; Fellows, Michael R.; Rothe, Jörg & Schend, Lena
  
• Economics and Computation. An Introduction to Algorithmic Game Theory, Computational Social Choice, and Fair Division. Springer Texts in Business and Economics, Springer-Verlag, Berlin, Heidelberg, 2015, xiv+612 Seiten
  J. Rothe (ed.)
  
• Journal of Autonomous Agents and Multi-Agent Systems, vol. 31, no. 3, pp. 628–655, Mai 2017
  Baumeister, Dorothea; Bouveret, Sylvain; Lang, Jérôme; Nguyen, Nhan-Tam; Nguyen, Trung Thanh; Rothe, Jörg & Saffidine, Abdallah
  
• The Complexity of Online Voter Control in Sequential Elections, Journal of Autonomous Agents and Multi-Agent Systems, vol. 31, no. 5, pp. 1055–1076, September 2017
  Hemaspaandra, Edith; Hemaspaandra, Lane A. & Rothe, Jörg
  
• Solving Seven Open Problems of Offline and Online Control in Borda Elections, Tagungsband 31st AAAI Conference on Artificial Intelligence (AAAI’17), AAAI Press, pp. 3029–3035. San Francisco, USA, Februar 2017
  N. Neveling und J. Rothe
  
• Strategy-Proofness of Scoring Allocation Correspondences for Indivisible Goods, Social Choice and Welfare, vol. 50, no. 1, pp. 101–122, Januar 2018
  Nguyen, Nhan-Tam; Baumeister, Dorothea & Rothe, Jörg